奇安信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 北京
111
点赞 回复 分享
发布于 2022-09-16 01:40 北京
 老兄,你这个蚂蚁的复杂度有点高啊?已经n的阶乘复杂度了,假如有个数据points数量为10000,这不是直接爆炸了,有没有复杂度更低的解法啊?
点赞 回复 分享
发布于 2022-09-16 14:09 江苏

相关推荐

2024-12-29 11:08
湖南工业大学 Java
程序员牛肉:简历没什么大问题了。 而且不要再换项目了。三月份就开暑期实习了,现在都一月份了。实在来不及重新开一下项目了。把一个项目写完或许很快,但是把一个项目搞懂吃透并不简单。所以不要换项目了,把你简历上面的两个项目好好挖一挖吧。 具体 体现在:你能不能流利的说出你的项目的每一个功能点代码实现?你能不能说出在这块除了A技术之外,还有其他技术能够实现嘛?如果有其他技术能够实现,那你这块为什么选择了你当前用的这个技术?
投递牛客等公司10个岗位
点赞 评论 收藏
分享
评论
3
10
分享

创作者周榜

更多
牛客网
牛客企业服务