12月初收到OA 就是坛子里面的原题
大家看一下,我记得看到了原图
1.k-nearest牛排店 max-heap
2.飞机里程 brute force
马上昂赛,攒个人品,求过
12月初收到OA 就是坛子里面的原题
大家看一下,我记得看到了原图
1.k-nearest牛排店 max-heap
2.飞机里程 brute force
马上昂赛,攒个人品,求过
狗家的题目吗
亚麻
求问第二题不n2用two pointer怎么做?我的方法two pointers解决不了duplicate里程数的case
谁把题目贴下?
是这个帖子里的题目吗
是的是的 第二题 飞机里程那个
我的two pointer解如果input有duplicate就没法都输出来…
我私信你代码了
谢谢老师 您用的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]]
*/
}
你这是如果有重复的情况下出问题对吧, 不能马上 r-- 或 l++ 吧
对重复情况有问题 我也觉得是r或l那里的逻辑问题 但不知道如何workaround 需要再加判断条件才能挪指针么
可以probe 一下next,如果相等的话,就把相等的全部放到result中。
然后把接下来是相等的全部skip。
也就是算sum的时候,相等的算一个element。但是算result的时候,算多个。
类似two sum 的一段代码参考
while (i > 0 && nums[i - 1] == nums[i]) {
i++;
}
主要是 while (nums[i - 1] == nums[i]) 的逻辑
老师麻烦您能不能具体说一下怎么在这个代码上修改,我试了半天还是过不了,请老师教我一下,麻烦了
可以把代碼也發給我一下嗎?
ssyeung14@outlook.com
thank you.
确实复杂了,重复问题解决了吗?
解决了吧,passed that test case.
Any better version?
代码可以简化一点
请问可以发给我一份飞机历程的题目么? 或者如果您知道这个题目是是leetcode上那一道题目的类似能劳烦告知一下么