新鲜亚麻 Amazon OA社招 2021

Mark6 发表于 2021-2-25 15:46
前两天面的，跟楼主的题目一样。没大看懂楼主的diff用来存什么的。不是尽可能选大的数字吗，怎么还需要le ...

1. 左右两个指针不是在找最终结果，是在找A，B 的分界点。因为按照题目的要求，只要从weight最大到小把item 加入A， 当A 的总weight大于剩下另一半的item的weight总和（就是会分到B组里的所有item），这个时候A 就是符合要求的结果。
2. diff 初始化是weight最大的item（left指向的，也就是第一个放进A 里的item）的weight， right初始化指向的是wieght最小的item（会被放进B中的item，这个时候还没有放入).  
3. right, left  移动的判断标准就是：
    当arr[right] < diff,  说明A多出来的重量- arr[right] 还是 > 0, arr[right] 加入B组，diff = diff - arr[right]， right++ 。
    反之 arr[right] >= diff,   就说明A 剩下的重量比arr[right]小，需要加入新的item来增加重量， left--, diff = diff + arr[left]。注意这里left 必须 右移，再加入A （因为diff的初始化让left指向的item已经加入了A）。
   code是过了所有给出的test cases的。不知道表达的清楚不，已经尽力了  >_<~

补充内容 (2021-2-27 01:44):
前面的code和这里的解释都被我把right和left搞反了（左右不分的人~>_<~）， 这里补充更正下：
right 指向的是weight大的一边的item，是放进A组。 left一边是weight小的，即将会被放进B组的item。

补充内容 (2021-2-27 01:45):
应该是判断 arr[left] <diff， 然后left++ 或者 right—。

补充内容 (2021-2-27 02:24):
请翻到后面的回帖，我更正了code和解释。

匿名者 发表于 2021-2-26 03:09
1. 左右两个指针不是在找最终结果，是在找A，B 的分界点。因为按照题目的要求，只要从weight最大到小把it ...

我准备周末把OA做掉，正在研究这道题，谢谢你的思路，问一下你VO安排在啥时候了，知道是什么组吗

匿名者 发表于 2021-2-26 03:09
1. 左右两个指针不是在找最终结果，是在找A，B 的分界点。因为按照题目的要求，只要从weight最大到小把it ...

能不能麻烦楼主把思路再讲一下，这里的left right确实很晕。
你看“反之 arr[right] >= diff,   就说明A 剩下的重量比arr[right]小，需要加入新的item来增加重量， left--, diff = diff + arr[left]。注意这里left 必须 右移，”
left--然后你讲右移。。。不是很get呀。。。
谢谢楼主了!

Mark6 发表于 2021-2-25 15:46
前两天面的，跟楼主的题目一样。没大看懂楼主的diff用来存什么的。不是尽可能选大的数字吗，怎么还需要le ...

能不能分享一下你的解法呀，是用DP吗

yiliaobailiao 发表于 2021-2-25 12:33
left, right看着有点乱啊。。。

感谢提醒，是的。左右不分，搞反了，不好意思。

感谢大家的提醒，之前我的code和解释，因为我的左右不分完全错乱了， 抱歉>_<。评论不能修改，我统一在这里更正一下，用low，high来表示双指针：

1. solution(int[] arr){
   
2.         sort(arr);
   
3.         low = 0;
   
4.         high = arr.length - 1;
   
5.         diff = arr[high];
   
6.         while(low < high){
   
7.             if(arr[low] < diff){
   
8.                 diff = diff - arr[low];
   
9.                 low++;
   
10.             }else{
    
11.                 high—-;
    
12.                 diff = diff + arr[high];
    
13.             }
    
14.         }
    
15.         for(int i : high to arr.length - 1){
    
16.             A.add(arr[i];
    
17.         }
    
18.         return A;
    
19.     }

复制代码

1. low, high两个指针不是在找最终结果，是在找A，B 的分界点。因为按照题目的要求，只要从weight最大到小把item 加入A， 当A 的总weight大于剩下另一半的item的weight总和（就是会分到B组里的所有item），这个时候A 就是符合要求的结果。
2. diff 初始化是weight最大的item（high指向的，也就是第一个放进A 里的item）的weight， low初始化指向的是weight最小的item（会被放进B中的item，这个时候还没有放入).  
3. Low, high指针  移动的判断标准就是：
    当arr[low] < diff,  说明A多出来的重量 - arr[low] 还是 > 0, arr[low] 加入B组，diff = diff - arr[low]， low++ 。
    反之 arr[low] >= diff,   就说明A 多出的重量(diff) 不大于 arr[low]，需要从high的一边加入新的item来增加重量， high—, diff = diff + arr[high]。注意这里high 必须先 左移，再加入A （因为diff的初始化让high指向的item已经加入了A）。
4. 当low, high 相遇，说明找到A，B 的分割点。从分割点把item加入A， 然后返回A就可以了。

厚脸皮再求一次大米~~ >_<
[/i]

leeyoda 发表于 2021-2-26 12:46
能不能麻烦楼主把思路再讲一下，这里的left right确实很晕。
你看“反之 arr[right] >= diff,  &#1 ...

感谢提醒，是我搞混了。我把更正更新到了后面的回帖里了。

eyaolan 发表于 2021-2-27 02:25
感谢提醒，是我搞混了。我把更正更新到了后面的回帖里了。

恩，我猜到你大概是typo，但{20,15,20,20,50}这个case结果还是不对，正确答案应该是{15,50}，你这个思路和码跑出来还是{20,50}，我打算研究一下背包怎么写，研究好了就做OA啦

leeyoda 发表于 2021-2-27 02:53
恩，我猜到你大概是typo，但{20,15,20,20,50}这个case结果还是不对，正确答案应该是{15,50}，你这个思路 ...

你的例子的正确答案就是：{20,50}
题目中有一句： If more than one subset A exists, return the one with the maximal total weight.

eyaolan 发表于 2021-2-27 05:05
你的例子的正确答案就是：{20,50}
题目中有一句： If more than one subset A exists, return the one w ...

到时候看看能不能遇上这个题目吧，可能是test case变了，我个人的理解就是，如果选A有20，B就不能有20，双方都有就不能满足intersection为null了，当然你也可以对interaction有不同的理解