热带雨林在职OA

Job Hunting Interview
, , , ,
1

12月初收到OA 就是坛子里面的原题

大家看一下，我记得看到了原图
1.k-nearest牛排店 max-heap
2.飞机里程 brute force

马上昂赛，攒个人品，求过

2

狗家的题目吗

3

亚麻

1 Like
4

求问第二题不n2用two pointer怎么做？我的方法two pointers解决不了duplicate里程数的case

5

谁把题目贴下？

6

是这个帖子里的题目吗

7

是的是的 第二题 飞机里程那个

8

我的two pointer解如果input有duplicate就没法都输出来…

9

我私信你代码了 :innocent:

10

谢谢老师:slightly_smiling_face: 您用的n2暴力解，我用two pointer优化了一下，但有些case过不了，麻烦老师给看下是不是逻辑问题。代码贴上了

https://drive.google.com/open?id=1PUOWoGSmoH1xAZIOuCKgi2RRb4fn-t88

import java.util.*;

public List<List<Integer>> PrimeMaxProfit(int maxTravelDist, List<List<Integer>> forwardRouteList, List<List<Integer>> returnRouteList) {
     List<List<Integer>> res = new ArrayList<>();
     int forLen = forwardRouteList.size(), retLen = returnRouteList.size() ;
     if (maxTravelDist == 0 || forLen == 0 || retLen == 0) {
         return res;
     }

     Collections.sort(forwardRouteList, (a, b) -> (a.get(1) - b.get(1)));
     Collections.sort(returnRouteList, (a, b) -> (a.get(1) - b.get(1)));

     int l = 0, r = retLen - 1, diff = Integer.MAX_VALUE, sum;
     while (l < forLen && r >= 0) {
         sum = forwardRouteList.get(l).get(1) + returnRouteList.get(r).get(1);

         if (maxTravelDist - sum >= 0 && maxTravelDist - sum <= diff) {
             if (maxTravelDist - sum < diff) {
                 diff = maxTravelDist - sum;
                 res = new ArrayList<>();
             }
             res.add(Arrays.asList(forwardRouteList.get(l).get(0), returnRouteList.get(r).get(0)));
         }

         if (sum >= maxTravelDist) {
             r--;
         } else {
             l++;
         }
     }

     return res;
 }

public static void main(String[] args) {
    List<List<Integer>> forward = new ArrayList<>();
    List<List<Integer>> returnL = new ArrayList<>();

    forward.add(Arrays.asList(1, 5000));
    forward.add(Arrays.asList(3, 4000));
    forward.add(Arrays.asList(2, 3000));
    forward.add(Arrays.asList(4, 1000));
    forward.add(Arrays.asList(5, 4000));

    returnL.add(Arrays.asList(1, 2000));
    returnL.add(Arrays.asList(3, 5000));
    returnL.add(Arrays.asList(2, 5000));
    returnL.add(Arrays.asList(4, 6000));


    List<List<Integer>> res = new AmazonOA().PrimeMaxProfit(9000, forward, returnL);
    System.out.println(res);
    /*Output
    [[4, 1000], [2, 3000], [3, 4000], [5, 4000], [1, 5000]]
    [[1, 2000], [3, 5000], [2, 5000], [4, 6000]]
    [[2, 4], [3, 2], [3, 3]] -> wrong! should be [[2, 4], [3, 2], [3, 3], [5, 3], [5, 2]]
    */
}
11

你这是如果有重复的情况下出问题对吧， 不能马上 r-- 或 l++ 吧

12

对重复情况有问题 我也觉得是r或l那里的逻辑问题 但不知道如何workaround 需要再加判断条件才能挪指针么

13

可以probe 一下next，如果相等的话，就把相等的全部放到result中。
然后把接下来是相等的全部skip。
也就是算sum的时候，相等的算一个element。但是算result的时候，算多个。
类似two sum 的一段代码参考

while (i > 0 && nums[i - 1] == nums[i]) {
	i++;
}

主要是 while (nums[i - 1] == nums[i]) 的逻辑

14

老师麻烦您能不能具体说一下怎么在这个代码上修改，我试了半天还是过不了，请老师教我一下，麻烦了

1 Like
15

可以把代碼也發給我一下嗎？
ssyeung14@outlook.com
thank you.

16

Can anyone help to check if this two pointer version looks ok?
我自己感覺寫得好Complicated。

image
image.png1758×1544 287 KB

17

确实复杂了，重复问题解决了吗？

18

解决了吧，passed that test case.
Any better version?

19

代码可以简化一点

20

请问可以发给我一份飞机历程的题目么? 或者如果您知道这个题目是是leetcode上那一道题目的类似能劳烦告知一下么