奇安信9.15笔试,第一题商品的怎么做吖,求教!
商品题我用的是回溯,过了37.5%
蚂蚁题也是回溯,全通过了
#奇安信##奇安信笔试##奇安信23秋招笔试好难呀#
蚂蚁题也是回溯,全通过了
所以商品那题用回溯是会超时不能过吗,有没有大佬提供一下解题思路😭
蚂蚁代码
class Solution {
int result=Integer.MAX_VALUE;
public int getMinLen (int[][] points) {
boolean[] flag=new boolean[points.length];
getResult(points,flag,0,0,0,0);
return result;
}
public void getResult(int[][] points,boolean[] flag,int num,int count,int x,int y){
if (num==points.length){
result=Math.min(result,count);
}
for (int i = 0; i < points.length; i++) {
if (flag[i]==true){
continue;
}
int[] temp=points[i];
int cA=temp[0]-x;
int cB=temp[1]-y;
int add=Math.abs(cA)+Math.abs(cB);
num++;
flag[i]=true;
count+=add;
getResult(points,flag,num,count,x+cA,y+cB);
count-=add;
flag[i]=false;
num--;
}
}
} 