Google on campus

22691482 发表于 2014-11-4 11:20
请看14楼，这不是最优解。

这个思路是对的。
和你说的思路不一样。
直接sample 一个random number  between 0 to （max - badNum.length）。
然后开始查。

22691482 发表于 2014-11-4 11:28
怎么确定maxPick里面是存的Player1还是Player2的信息？

maxPick存的都是player1能得到的最大值。
比如maxPick【i】【j】 就是表示如果我们只有arr 的从i 到 j 的segment。 player1 能得到的最大的值。

averillzheng 发表于 2014-11-4 11:30
这个思路是对的。
和你说的思路不一样。
直接sample 一个random number  between 0 to （max - badNum. ...

噢噢噢噢  我在14楼回复里面也提到了这个思路，， 是中间的某部。

averillzheng 发表于 2014-11-4 11:35
maxPick存的都是player1能得到的最大值。
比如maxPick【i】【j】 就是表示如果我们只有arr 的从i 到 j  ...

你好，

在19楼， 你提到：
“player1 已经取了arr【i】 或者arr【j】。.
这样player1 就变成了player2. 而原来的player2 就变成了player1.”

如果maxPick存的都是Player1的信息，怎么变到Player2？

random那道题我去年Google oncampus面过，主要是考虑等概率

csgtc 发表于 2014-11-4 13:29
random那道题我去年Google oncampus面过，主要是考虑等概率

所以鸡精还是叼

22691482 发表于 2014-11-4 11:20
思路是这样。。问题是怎么写出可以跑的代码。。

没考虑太多cases，不一定对。不过倒是提醒我了，对付游戏minimax是比较常用的思路。为了感谢lz分享面经，我贴一下我的代码，要是有没考虑到的，欢迎大家指正。

1. #include <iostream>
   
2. #include <assert.h>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int coinGame(int array[], int n) {
   
7.         assert(n > 0);
   
8.         if (n == 1)
   
9.                 return array[0];
   
10.         int start = 0;
    
11.         int end = n - 1;
    
12.         int sum = 0;
    
13.         for (; start < end; start++, end--) {
    
14.                 if (end - start == 1)
    
15.                         sum += max(array[start], array[end]);
    
16.                 else if (end - start == 2) {
    
17.                         sum += max(array[start], array[end]) + array[start+1];
    
18.                         break;
    
19.                 }
    
20.                 else {
    
21.                         sum += (min(array[start] - array[start+1], array[start]-array[end]),
    
22.                                 min(array[end] - array[end-1], array[end]-array[start]))
    
23.                                 ? array[start] : array[end];
    
24.                 }
    
25.         }
    
26.         return sum;
    
27. }
    
28. 
    
29. int main() {
    
30.         int test1[] = {50, 100, 1, 49};
    
31.         cout << coinGame(test1, 4) << endl;
    
32. }

复制代码

补充内容 (2014-11-4 14:48):
我这里assume的永远玩家先手

王可雪 发表于 2014-11-4 14:47
没考虑太多cases，不一定对。不过倒是提醒我了，对付游戏minimax是比较常用的思路。为了感谢lz分享面经， ...

厉害厉害，，我当时想的是我在写minmax作业的时候实现起来很麻烦，面试现场写出来会有很多bug，就没现场写了。。

王可雪 发表于 2014-11-4 14:47
没考虑太多cases，不一定对。不过倒是提醒我了，对付游戏minimax是比较常用的思路。为了感谢lz分享面经， ...

上面的代码有点错误。

1. #include <iostream>
   
2. #include <assert.h>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int coinGame(int array[], int n) {
   
7.         assert(n > 0);
   
8.         if (n == 1)
   
9.                 return array[0];
   
10.         int start = 0;
    
11.         int end = n - 1;
    
12.         int sum = 0;
    
13.         for (; start < end;) {
    
14.                 if (end - start == 1) {
    
15.                         sum += max(array[start], array[end]);
    
16.                         break;
    
17.                 }
    
18.                 else if (end - start == 2) {
    
19.                         sum += max(array[start], array[end]) + array[start+1];
    
20.                         break;
    
21.                 }
    
22.                 else {
    
23.                         //cout << array[end] - array[end-1] << endl;
    
24.                         sum += (min(array[start] - array[start+1], array[start]-array[end]) >
    
25.                                 min(array[end] - array[end-1], array[end]-array[start]))
    
26.                                 ? array[start++] : array[end--];
    
27.                         //cout << end << endl;
    
28.                         min(array[start] - array[start+1], array[start]-array[end]) >
    
29.                         min(array[end] - array[end-1], array[end]-array[start]) ? start++ : end--;
    
30.                         //cout << end << endl;               
    
31.                 }
    
32.         }
    
33.         return sum;
    
34. }
    
35. 
    
36. int main() {
    
37.         int test1[] = {50, 100, 1000, 49};
    
38.         int test2[] = {50, 100, 1, 49};
    
39.         cout << coinGame(test1, 4) << endl;
    
40.         cout << coinGame(test2, 4) << endl;
    
41. 
    
42. }

复制代码

22691482 发表于 2014-11-4 14:49
厉害厉害，，我当时想的是我在写minmax作业的时候实现起来很麻烦，面试现场写出来会有很多bug，就没现场 ...

那你用什么写的？