奇安信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 浙江
回溯提交的版本只能a12%,那个43的例子过不了,现在优化了43例子能过但是不知道实际能a多少
1 回复 分享
发布于 2022-09-15 22:16 广东
蚂蚁贴个代码被
1 回复 分享
发布于 2022-09-15 21:15 北京
 老兄,你这个蚂蚁的复杂度有点高啊?已经n的阶乘复杂度了,假如有个数据points数量为10000,这不是直接爆炸了,有没有复杂度更低的解法啊?
点赞 回复 分享
发布于 2022-09-16 14:09 江苏
111
点赞 回复 分享
发布于 2022-09-16 01:40 北京
商品我是回溯,a了50
点赞 回复 分享
发布于 2022-09-15 21:36 北京
我第一道题回溯怎么优化都是37.5,感觉回溯复杂度是不是太高了,然后第二题就没想回溯
点赞 回复 分享
发布于 2022-09-15 21:28 江西

相关推荐

一共一个小时,面试难度以及自己的回答算是最近的面试压力比较大的,实习问了30分钟,中间穿插八股。1.redis数据结构2.redis持久化机制3.mysql索引底层4.聚簇索引与非聚簇索引5.索引优化6.索引失效7.mysql执行一条sql8.那么多索引mysql怎么选(不会)9.tcp与udp区别10.tcp为什么可靠11.消息队列作用12.kafka怎么保证消息有序性13.mcp是什么?14.skills是什么?15.jvm内存分配与回收过程(我讲了从创建对象到判断垃圾对象到垃圾回收我全说了一遍,是这个吗?)16.fullgc触发机制17.tcp的拥塞控制流程(不会了)18.分布式事务解决方案,说了2pc,3pc,tcc。算法是反转双向链表,没有按格式输出,但是面试官没让继续写了,面完以为挂了,结果晚上秒过,看看复试什么情况吧。今天百度打电话准备发offer了,业务跟在手子的差不多,很垂,并且说不分日常暑期,只看表现,会有转正机会,但是考虑再三还是拒绝了,百度实习薪资确实有点低,title也不如之前了,但是面试的二位业务老师我很喜欢,对我的评价也不错,希望之后能有机会共事。从三月份到现在一共面了六家,面试次数总共是8场,情况如下:脉脉二面(无答复,默认挂)百度二面已oc美团一面过,下周一二面shein一面过直接HR面游族一面过直接HR面腾讯一面过等待约二面滴滴明天一面面试通过率还是蛮高的,但是大部分都是日常,感觉对我现在的加成不大,大概率不会去,不知道暑期会是什么情况呢唉,希望能有面试吧,继续加油。字节被无hc直接取消了,现在还没人捞,有没有字节HR救救我
不管什么都不想跳动了:本人美团百度快手都待过,建议肯定是直接留快手多一点产出后转正or直接冲字节腾讯暑期吧。一是快手从福利到基建都吊打另外两家。美团现在这个业务比较惨,本来毛利就很低,亏损严重,今年很可能要优化人力降低成本,去了别说日常,就算暑期后面都很可能被优化。百度其实实习生权限挺高的,可以接触到一些含金量高的项目,但是现在的风评不如之前了,薪资也不高。二是转正概率和薪资是跟产出挂钩的,你都在手子已经积累产出了,去其他家日常实习产出都是从0开始,肯定不可能有你在手子转正可能性大啊,现在日常压根没必要去,而且我有两个师弟都是在快手日常转正的,不用太担心,安心留在手子一边多做一点产出然后一边冲字节腾讯暑期,字节腾讯今年实习岗位非常多的,不如好好把握这个,加油。
查看18道真题和解析
点赞 评论 收藏
分享
03-03 23:12
已编辑
北京邮电大学 Java
书海为家:我来给一点点小建议,因为毕竟还在学校不像工作几年的老鸟有丰富的项目经验,面试官在面试在校生的时候更关注咱们同学的做事逻辑和思路,所以最好在简历中描述下自己做过项目的完整过程,比如需求怎么来的,你对需求的解读,你想到的解决办法,遇到困难如何找人求助,最终项目做成了什么程度,你从中收获了哪些技能,你有什么感悟。
你的简历改到第几版了
点赞 评论 收藏
分享
评论
3
10
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务