奇安信9.15笔试,第一题商品的怎么做吖,求教!

商品题我用的是回溯,过了37.5%
蚂蚁题也是回溯,全通过了
所以商品那题用回溯是会超时不能过吗,有没有大佬提供一下解题思路😭

蚂蚁代码
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--;
        }
    }
}


#奇安信##奇安信笔试##奇安信23秋招笔试好难呀#
全部评论
回溯复杂度2^n,可以看看我n^2的dp做法哦 https://www.luogu.com.cn/paste/5cgfn3o5
5
送花
回复
分享
发布于 2022-09-15 22:05 浙江
蚂蚁贴个代码被
1
送花
回复
分享
发布于 2022-09-15 21:15 北京
滴滴
校招火热招聘中
官网直投
回溯提交的版本只能a12%,那个43的例子过不了,现在优化了43例子能过但是不知道实际能a多少
1
送花
回复
分享
发布于 2022-09-15 22:16 广东
我第一道题回溯怎么优化都是37.5,感觉回溯复杂度是不是太高了,然后第二题就没想回溯
点赞
送花
回复
分享
发布于 2022-09-15 21:28 江西
商品我是回溯,a了50
点赞
送花
回复
分享
发布于 2022-09-15 21:36 北京
 老兄,你这个蚂蚁的复杂度有点高啊?已经n的阶乘复杂度了,假如有个数据points数量为10000,这不是直接爆炸了,有没有复杂度更低的解法啊?
点赞
送花
回复
分享
发布于 2022-09-16 14:09 江苏

相关推荐

点赞 评论 收藏
转发
3 10 评论
分享
牛客网
牛客企业服务