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);
}
} 