【笔经】【老虎】

选择题
1.知道树的中序和后序 求前序
忘得差不多了,反正不难,就是分值大,5分一道
编程题
1.汽车载客trips = {{2,1,4}{4,2,6}},capacity = 5 输出 = 2
trips[i][0]是乘客数量,trips[i][1]是上车地点,trips[i][2]是下车地点。capacity是车的最大容量,求最少需要多少车?
按照上车时间从小到大排序。创建一个优先队列,按照最早的下车时间进队的,看上车的人数是不是超过capacity,超过就count++。AC!
public int minCarCount (int[][] trips, int capacity){
        Arrays.sort(trips, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
        });
        int count = 1;
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
            return o1[2] - o2[2];
        }
        });
        int sum = 0;
        for (int i = 0; i < trips.length; i++) {
            boolean flag = true;
            while(q.size() > 0 && flag){
                int[] t = q.peek();
                if(trips[i][1] >= t[2]){
                    int[] temp = q.poll();
                    sum -= temp[0];
                }
                else  flag = false;
            }
            q.add(trips[i]);
            sum += trips[i][0];
            if(sum > capacity){
                count++;
            }
        }
        return count;
    }


2.打怪,level = 1,level表示初始层级,x = 2,x表示需要做的任务数,  tasks={{0,1},{1,2},{1,3}} 只有level>=tasks[i][0],level才能+=tasks[i][1],求level最大是多少?
没做完。感觉也是用贪心来做。
全部评论
楼主,感觉代码不太对啊,是不是我理解错了,当测试用例为trips = {{2,1,5},{4,2,6},{2,3,7},{1,4,8}};capacity = 5;时 前4站一直上人,没有人下车,但是人数最多时(第四站)只有9人,2辆车就够了,但是如果按照代码当判断sum > capacity时就count++,那么从第二站(累计6人)之后每次都count++,得到答案为4.所以是不是我理解错了题意?
2 回复 分享
发布于 2020-08-12 21:57

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

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