新鲜Google Onsite~~

二维数组，正着一遍算，反着一遍算
3 1 5 4
这四个数，用个二维数组，先正着来一遍，第一围算出来是
｛0，0｝｛3，0｝｛4，0｝｛16，0｝-》最大值是64，
反过来
｛0，63｝｛3， 21｝｛4， 20｝｛16，4｝-》4*20最大
O(n)复杂度

wzhwawhxm 发表于 2015-9-14 22:17
二维数组，正着一遍算，反着一遍算
3 1 5 4
这四个数，用个二维数组，先正着来一遍，第一围算出来是

LZ 能在讲解一下吗 看不太懂...

iverson1122 发表于 2015-9-8 10:00
是的，这是最直白的想法，之后在小哥的提示下改成了二维dp的方法。

LZ 能讲解一下DP recurrence 吗 谢谢?

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

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

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

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

第一题 int(Log X) 是什么题目？ 没看懂？

楼主第二题只有正数吗？如果有负数岂不是要存最大值和最小值，那组合起来情况很多啊

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

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

say543 发表于 2015-9-16 12:04
dp1: 代表第i个element之前的最大值(i excluded)

dp2: 代表第i个element之后的最大值(i included)

这道题后面我想了下，这方法不对，感觉还是得用recursion。。。

第三轮第二题写了下：

1. public boolean hasTgtCom(int[] nums, int tgt){
   
2.         return hasTgtComHelper(nums, tgt, nums.length - 1);
   
3.     }
   
4. 
   
5.     private boolean hasTgtComHelper(int[] nums, int tgt, int index){
   
6.         if (index == -1) return tgt == 0;
   
7.         int base = 0, tmpNum = 0;
   
8.         for (int i = index; i >= 0 ; i--) {
   
9.             base = (base == 0 ? 1 : base * 10);
   
10.             if(nums[i] == 0 && i != index) continue;
    
11.             tmpNum += nums[i] * base;
    
12.             int remains = tgt - tmpNum;
    
13.             if (remains < 0) continue;
    
14.             if (hasTgtComHelper(nums, remains, i - 1)) return true;
    
15.         }
    
16.         return false;
    
17.     }

复制代码