Google Onsite

Interval的查找是如何二分的？先merge interval再找么？

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

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

pengdu 发表于 2019-1-19 10:10
有道理！f表示要抽第i张牌时的最大值，f[0]是最后的解。
f = sum - min(f, f, f)
需要O(n)的时间和空间复 ...

我想明白了~忽略我之前那个信息哈哈~

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

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

pengdu 发表于 2019-1-19 10:10
有道理！f表示要抽第i张牌时的最大值，f[0]是最后的解。
f = sum - min(f, f, f)
需要O(n)的时间和空间复 ...

请问一下，这样的话是不是需要保持两个dp的数组，分别表示自己抽和对手抽的值？

wawjchinawct 发表于 2019/02/02 16:47:04


请问一下，这样的话是不是需要保持两个dp的数组，分别表示自己抽和对手抽的值？

一个就好，自己抽和别人抽的策略是一样的。

请问 抽卡片我这样写对不对呢？
请大家赐教~

1. Map<Integer, Integer> map;
   
2. public int pickCards(int[] cards) {
   
3.         map = new HashMap<>();
   
4.         return dfs(cards, 0);
   
5. }
   
6. 
   
7. private int dfs(int[] cards, int start) {
   
8.         if (start >= cards.length) return 0;
   
9.         if (map.containsKey(start)) return map.get(start);
   
10.        
    
11.         int res = 0;
    
12.         for (int num = 1; num <= 3; num++) {
    
13.                 int nnum = num;
    
14.                 int curRes = 0;
    
15.         while (nnum > 0 && start + nnum - 1 < cards.length) {
    
16.         curRes += cards[start + nnum - 1];
    
17. }
    
18. int another = dfs(cards, start + num);
    
19. res = Math.max(curRes, res);
    
20. }
    
21. map.put(start, res);
    
22. return res;
    
23. }
    

复制代码