google 电面 跪经

b01501085 发表于 2017-12-5 12:29
請問樓主第一題是怎麼去random的呢？

我是用了java自带的random number generator，然后值的上线就是total population。每一次generate一个random number，然后每一个国家的population作为一个range，累加（用hash map 实现）。最后看这个random number在哪一个range就是哪一个国家 （这一步可以用二分优化）。

是不会还需要递归来做呢？

补充内容 (2017-12-6 11:18):
第二轮的题是不是需要自顶向下的dp需要用递归来做？

Elina_huang 发表于 2017-12-6 11:17
是不会还需要递归来做呢？

补充内容 (2017-12-6 11:18):

可以使用递归可以不用。我一开始想的最好写的是用的递归做dp，但是后来的memoization优化的版本是不用递归用循环的。
这个dp我的知识范围内只能从上到下做。

yunjiezhang 发表于 2017-12-6 12:35
可以使用递归可以不用。我一开始想的最好写的是用的递归做dp，但是后来的memoization优化的版本是不用递 ...

你的memorization优化是怎么做的呢？可以详细说说嘛？

Elina_huang 发表于 2017-12-6 22:37
你的memorization优化是怎么做的呢？可以详细说说嘛？

上面有个回复详细讲了一下，你先看一下那个吧。没看懂的话再回复我吧，我再想想别的讲法。

yunjiezhang 发表于 2017-12-5 10:27
啊 没错。。诶。。我这脑子老出错。。
谢谢指出来

請問一下, 最後一輪需要odd/even相加嘛?
想法是能reach 到n 不是一定是odd (第一次丟嗎?)  還是我想錯了?

除了reach n 的一定是odd, 其他才都需要記錄 odd/even?

反過來觀察
odd: 1,2,4
even:1,3,4
考慮 n=6

top-down,
第一次丟 6  =  dp[5][0] + dp[4][0] + dp[2][0]
dp[5][0] = dp[4][1] + dp[2][1] + dp[1][1]
dp[4][0] = dp[3][1] + dp[1][1] + dp[0][1]
dp[2][0] = dp[1][1] + dp[-1][1] + dp[-2][1]

if i <= 0, dp[i][x] = 1

reliveinfire 发表于 2017-12-7 11:44
請問一下, 最後一輪需要odd/even相加嘛?
想法是能reach 到n 不是一定是odd (第一次丟嗎?)  還是我想錯了 ...

诶。。你提出来了我也有点懵了。。所以觉得崩嘛。。最后算法都没想清楚代码也没写完。
貌似第n层出发的是算第一次下落。如果这样的话可能只要考虑 odd 情况，那你说的应该有道理。
如果你面试碰到的话建议你问问面试官问清楚啦，我这样半吊子的也不太好揣测面试官想要的代码算法是什么样的。。不好意思啦

yunjiezhang 发表于 2017-12-7 11:49
诶。。你提出来了我也有点懵了。。所以觉得崩嘛。。最后算法都没想清楚代码也没写完。
貌似第n层出发的 ...

我也不太确定, 不过照这想法 你原本提出的作法好像是正确的.

所以想提出来讨论讨论.

马克一下 谢谢楼主！

写了个dp的，思路是从n开始往下跳，没test case不知道是不是对。。。

class Solution {
    public int jumpGround(int n, int[] sticky) {
        HashSet<Integer> set = new HashSet();
        for (int num : sticky)
            set.add(num);
        int[][] dp = new int[n+4][2];
        if (!set.contains(n)) dp[n][0] = 1;
        for (int i = n - 1; i > 0; i--) {
            if (set.contains(i)) continue;
            dp[i][0] = dp[i+1][1] + dp[i+3][1] + dp[i+4][1];
            dp[i][1] = dp[i+1][0] + dp[i+2][0] + dp[i+4][0];
        }
        int ans = 3 * (dp[1][0] + dp[1][1]);
        ans += 2 * (dp[2][0] + dp[2][1]);
        ans += (dp[3][0] + 2 * dp[3][1]);
        ans += (dp[4][0] + dp[4][1]);
        return ans;
    }
}