微软苏州4面挂经

那么多人把 subset sum 的变种当成背包说明题刷的还是不够啊

1. int solve(const vector<int>a, int k) {
   
2.     int lo = 0;
   
3.     int hi = 0;
   
4.     for (int t : a) {
   
5.         if (t < 0) lo += t; else hi += t;
   
6.     }
   
7.     auto dp = make_unique<int[]>(hi-lo+1);
   
8.     dp [-lo] = 1;
   
9.     for (int t : a) {
   
10.         if (t > 0)      for (int x=hi-lo; x>=t;       x--) dp[x]+=dp[x-t];
    
11.         else if (t < 0) for (int x=0;     x<=hi-lo+t; x++) dp[x]+=dp[x-t];
    
12.     }
    
13.     return dp[k-lo];
    
14. }
    
15. 
    
16. // [1,2,1,2],3 ==> 4
    
17. // [4,-3,2], 3 ==> 1
    
18. // [-2,2],   0 ==> 2
    

复制代码

telegramatic 发表于 2020-6-2 09:20
第一题二叉树左视图用递归的话需要一个全局变量，维护目前为止探测过的最深深度，然后正常的前序遍历就行了 ...

妙了 zszszszs

usr_opta 发表于 2020-9-4 15:37
那么多人把 subset sum 的变种当成背包说明题刷的还是不够啊
[mw_shl_code=cpp,true]int solve(const vect ...

你这个解法如果k是负数就不对了

shashduqhasd 发表于 2020-10-14 06:40
你这个解法如果k是负数就不对了

求测试输入

usr_opta 发表于 2020-10-14 08:30
求测试输入

哦不对，你的应该是对的。不过我觉得直接把数组所有的数全弄成正数，写DP的时候会更方便吧