新鲜亚麻 Amazon OA社招 2021

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢大家的提醒，之前我的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]

喵喵～ 发表于 2021-2-21 14:04
可以详细说一下双指针的思路吗？谢谢！

大概思路是这样的：

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

复制代码

[/i]

补充内容 (2021-2-27 01:33):
不好意思，我这个左右不分，在while里把left和right搞混了，后面的解释也估计和混乱。应该是判断 arr[left] <diff， 然后left++ 或者 right--。

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

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和解释。

感觉按顺序取的话 不对呀。。
比如 1,3,10,4,4,1

排序 从大到小 得到结果是 10,4,4
但最优解是10,3

wznfls 发表于 2021-2-19 12:03
感觉按顺序取的话 不对呀。。
比如 1,3,10,4,4,1

这题不能用贪心做，本质上是个背包问题

可以详细说一下双指针的思路吗？谢谢！

wznfls 发表于 2021-2-19 12:03
感觉按顺序取的话 不对呀。。
比如 1,3,10,4,4,1

输入： 1,3,10,4,4,1
结果应该是： 4，10
题目中有一句： If more than one subset A exists, return the one with the maximal total weight.

匿名者 发表于 2021-2-22 13:12
输入： 1,3,10,4,4,1
结果应该是： 4，10
题目中有一句： If more than one subset A exists, return t ...

主要还是这个intersection的理解吧。到底是不是相同值的元素，必须放在一边。还是每一个item只能用一次。

匿名者 发表于 2021-2-22 13:06
大概思路是这样的：
[mw_shl_code=bash,true]solution(int[] arr){
        sort(arr);

left, right看着有点乱啊。。。

匿名者 发表于 2021-2-22 13:06
大概思路是这样的：
[mw_shl_code=bash,true]solution(int[] arr){
        sort(arr);

前两天面的，跟楼主的题目一样。没大看懂楼主的diff用来存什么的。不是尽可能选大的数字吗，怎么还需要left指针，找小的呢。。

yiliaobailiao 发表于 2021-2-25 12:21
主要还是这个intersection的理解吧。到底是不是相同值的元素，必须放在一边。还是每一个item只能用一次。

每个item只能用一次， 一个item不会同时存在A 和 B里，就没有intersection了。