Google SDE coding 面经 (新题，求idea)

Input:
- num_states：int
- delegates: int[]
- votes_president_A: int[]
- votes_president_B: int[]
- votes_Undecided: int[]

output: the minimum number of people vote A will lead A wi

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

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

number number people vote A
}
Any idea about this questions? I get stuck during the interview....

选举那道题我的解法：

1. public int solution(
   
2.         int num_states,
   
3.         int[] delegates,
   
4.         int[] votes_president_A,
   
5.         int[] votes_president_B,
   
6.         int[] votes_Undecided)
   
7. {
   
8.         // return minumber number people vote A
   
9.         var target = delegates.Sum();
   
10.         var dp = new int[target+1];
    
11.         Array.Fill(dp, int.MaxValue);
    
12.         dp[0] = 0;
    
13.         var votes = new int[num_states];
    
14.         for (var i = 0; i < num_states; ++i) {
    
15.                 // total number of votes
    
16.                 var total = votes_president_A[i] + votes_president_B[i] + votes_Undecided[i];
    
17.                 // votes required to win for A
    
18.                 votes[i] = total / 2 + 1 - votes_president_A[i];
    
19.         }
    
20.        
    
21.         // dp[j] = min(dp[j-delegates[i]] + votes[i], dp[j])   0 <= i < num_states
    
22.         for (var i = 0; i < num_states; ++i) {
    
23.                 for (var j = target; j >= 0; --j) {
    
24.                         if (j >= delegates[i] &&
    
25.                                 dp[j - delegates[i]] != int.MaxValue &&
    
26.                                 dp[j - delegates[i]] + votes[i] < dp[j]) {
    
27.                                 dp[j] = dp[j - delegates[i]] + votes[i];
    
28.                         }
    
29.                 }
    
30.         }
    
31.        
    
32.         // Find the minimum votes for delegates larger than half
    
33.         var result = int.MaxValue;
    
34.         for (var i = target/2+1; i <= target; ++i) {
    
35.                 result = Math.Min(result, dp[i]);
    
36.         }
    
37.        
    
38.         return result == int.MaxValue ? -1 : result;
    
39. }

复制代码

1.     public int solution(int num_states, int[] delegates, int[] votes_president_A, int[] votes_president_B, int[] votes_Undecided){
   
2.         // sanity check first, null / length ...
   
3. 
   
4.         int sum = 0;
   
5.         int canGet = 0;
   
6.         int alreadyGot = 0;
   
7.         List<int[]> canWin = new ArrayList<>();
   
8.         for (int i = 0; i < num_states; i ++) {
   
9.             sum += delegates[i];
   
10.             if (votes_president_A[i] + votes_Undecided[i] <= votes_president_B[i]) {
    
11.                 continue;
    
12.             }
    
13.             canGet += delegates[i];
    
14.             if (votes_president_B[i] + votes_Undecided[i] < votes_president_A[i]) {
    
15.                 alreadyGot += delegates[i];
    
16.                 continue;
    
17.             }
    
18. 
    
19.             int needed = (votes_Undecided[i] + votes_president_A[i] +
    
20.                     votes_president_B[i]) / 2 - votes_president_A[i] + 1;
    
21.             canWin.add(new int[]{delegates[i], needed});
    
22.         }
    
23. 
    
24.         int totalNeed = sum / 2 + 1 - alreadyGot;
    
25.         if (totalNeed <= alreadyGot) return 0;
    
26.         if (totalNeed > canGet) return -1;
    
27.         int[][] dp = new int[2][canGet - alreadyGot + 1];
    
28.         dp[0][0] = 0;
    
29.         for (int i = 1; i < dp[0].length; i ++) {
    
30.             dp[0][i] = Integer.MAX_VALUE;
    
31.         }
    
32.         int res = Integer.MAX_VALUE;
    
33.         for (int i = 1; i <= canWin.size(); i ++) {
    
34.             for (int j = 0; j < dp[0].length; j ++) {
    
35.                 int pre = j - canWin.get(i - 1)[0] >= 0 ? dp[i % 2][j - canWin.get(i - 1)[0]] : Integer.MAX_VALUE;
    
36.                 // dp[i][j] == min(dp[i - 1][j], dp[i][j - 当前票数])
    
37.                 dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j],
    
38.                         pre == Integer.MAX_VALUE ? Integer.MAX_VALUE : pre + canWin.get(i - 1)[1]);
    
39.                 if (j >= totalNeed ) res = Math.min(res, dp[i % 2][j]);
    
40.             }
    
41.         }
    
42.         return res;
    
43.     }

复制代码

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

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

这就是一个01背包问题。。。用dp求解

没看懂题目啊。 有人能帮忙解释下吗

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

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

标准01背包问题。

匿名者 发表于 2020-12-21 08:01
我理解的是这样的

input1:

大佬， 这个delegate什么意思？

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

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

果然还是考的dp啊

lyronly 发表于 2020-12-26 11:51
每个
state 1:  5 0 0 20
转换为

求教这个不会同一个州的选票用了两次吗？