首页 > 4.1携程Java笔试
头像
LgglePiggle
编辑于 2021-04-05 20:01
+ 关注

4.1携程Java笔试

第一题写一个sql语法分析,分析出sql中的表名,临时表不算,按最简单的sql输出了一下,11%
第二题商旅问题感觉是最优子集问题,前两天leetcode有类似的,穷举ac了,第二题默认输出-1都有27%的用例通过
第二题暴力ac
 public class Main {
    static ArrayList<List<Integer>> plans = new ArrayList<>();
    public static void main(String[] args) {
        int res = -1;
        Scanner sc = new Scanner(System.in);
        //权益数
        int n = Integer.parseInt(sc.nextLine());
        String packagesIn = sc.nextLine();
        String[] s = packagesIn.split(" ");
        ArrayList<List<Integer>> packageList = new ArrayList<>();
        //填充权益包
        for(String string:s){
            String[] vArray = string.split(",");
            ArrayList<Integer> vList = new ArrayList<>();
            for(String v:vArray){
                vList.add(Integer.parseInt(v));
            }
            packageList.add(vList);
        }
        int packageNum = s.length;
        int[] price = new int[packageNum];
        String priceIn = sc.nextLine();
        String[] ps = priceIn.split(" ");
        for(int i=0;i<packageNum;i++){
            price[i] = Integer.parseInt(ps[i]);
        }
        String valuesIn = sc.nextLine();
        String[] vs = valuesIn.split(" ");
        int[] values = new int[vs.length];
        for(int i=0;i<vs.length;i++){
            values[i] = Integer.parseInt(vs[i]);
        }
        //先穷举吧
        dfs(false,0,packageList,new ArrayList<Integer>(),values);
        if(plans.size()>0){
            for (List<Integer> plan : plans) {
                int jiage = 0;
                for (int p : plan) {
                    jiage += price[p];
                }
                if (res == -1) {
                    res = jiage;
                } else {
                    res = Math.min(res, jiage);
                }
            }
        }
        //先测测有多少-1用例嘿嘿
        System.out.println(res);
    }
    public static void dfs(boolean choosePre,int cur,List<List<Integer>> packageList,List<Integer> curChoose,int[] values){
        if(cur == packageList.size()){
            boolean allFind = !(curChoose.size()==0);
            for(int value:values){
                boolean find = false;
                for(int i=0;i<curChoose.size();i++){
                    int pIndex = curChoose.get(i);
                    List<Integer> quanyiList = packageList.get(pIndex);
                    for(int quanyi:quanyiList){
                        if(quanyi==value){
                            find=true;
                            break;
                        }
                    }
                    if(find){
                        break;
                    }else if(i==curChoose.size()-1){
                        allFind=false;
                    }
                }
            }
            //全部符合,加入计划
            if(allFind){
                plans.add(new ArrayList<Integer>(curChoose));
            }
            return;
        }
        dfs(false, cur + 1, packageList,curChoose,values);
        curChoose.add(cur);
        dfs(true,cur + 1, packageList,curChoose,values);
        curChoose.remove(curChoose.size()-1);
    }
} 

全部评论

(13) 回帖
加载中...
话题 回帖