谷歌店面面经

发面经，攒人品。

开始就聊了快20分钟。之后给了道题：
给一堆硬币list，里面

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

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

说DP是优化解。

接着刷题刷题刷题~~~

感觉象个01背包问题， 写了一下， 不知道对不对， 请指正：

1. public static double divideMoney(List<Integer> list){
   
2.             if(list==null || list.size()==0) return 0.0;
   
3. 
   
4.             int sum=0;
   
5.             for(int n : list) sum+=n;
   
6.             
   
7.             return helperBack(list, sum/2)*1.0/Math.pow(2, list.size());
   
8.         }
   
9.         public static int helperBack(List<Integer> list, int target){
   
10.                 int[] dp=new int[target+1];
    
11.                 dp[0]=1;
    
12.                
    
13.                 for(int i=0; i<list.size(); i++){
    
14.                         for(int j=target; j>=1; j--){
    
15.                                 if(j>=list.get(i)) dp[j]+=dp[j-list.get(i)];
    
16.                         }
    
17.                 }
    
18.                 System.out.println("Tie: "+dp[target]);
    
19.                 return dp[target];
    
20.         }

复制代码

不知到这样可不可行。 硬币LIST的长度为N, 那么就设置dp数组的长度为1<<N.  下面是我的代码，方法比较笨，列举了每一种可能，没想到如何剪纸。

int total=0;
for(int I=0;i<list.length;I++){
   total+=list[I];
        for(int j=0;j<(1<<I);j++){
             dp[j*2]=dp[j];
             dp[j*2+1]=dp[j*2]+list[I];
        }
}
if(total%2==1)
    return 0;
int count=0;
for(int I=0;i<(1<<list.length);i++){
     if(dp[I]==total/2)
         count++;
}
return count/(1<<list.length);

想了下可以dp解，dp[i][j]就是前i个硬币A比B多j块钱的组合数。dp[I][j] = dp[i-1][j+coin[I]] + dp[i-1][j-coin[i]]

Josh 发表于 2016-9-9 00:26
想了下可以dp解，dp[j]就是前i个硬币A比B多j块钱的组合数。dp[j] = dp[j+coin] + dp[j-coin]

你这样的话 这个dp数组太大了吧。。 第二维的长度是所有币值的总和？

经典问题：subset sum
wikipedia

xiayewang 发表于 2016-9-9 01:32
不知到这样可不可行。 硬币LIST的长度为N, 那么就设置dp数组的长度为1

你这个不是指数复杂度么？DFS就是指数复杂度啊。。
并没有提升时间复杂度。。用DP的意义就没有了

phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么？DFS就是指数复杂度啊。。
并没有提升时间复杂度。。用DP的意义就没有了

恩 是的 谢谢大神指正！

phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么？DFS就是指数复杂度啊。。
并没有提升时间复杂度。。用DP的意义就没有了

这个题要是面值没特点的话，怎么着也得指数复杂度吧？

phantom 发表于 2016-9-9 01:36
你这个不是指数复杂度么？DFS就是指数复杂度啊。。
并没有提升时间复杂度。。用DP的意义就没有了

你能写个通用的dp解法大家参考参考吗？面值为任意正序列。

ytsr 发表于 2016-9-9 02:08
这个题要是面值没特点的话，怎么着也得指数复杂度吧？

https://en.wikipedia.org/wiki/Pa ... olynomial_algorithm

其实有点像背包的。
S ： 面值数组
sum = sum(S)
DP [sum / 2][ S.size() ]
递推公式：
DP[k][i] : 表示用前i个数字，构造出sum = k的数量
DP[k][i] = DP[k][i-1]          不放入第 i 个数
               DP[k-S[i]][i-1]    放入第 i 个数

复杂度 O(KN)
问题就是如果有某一个面值特别大。。时间复杂度很高