Facebook电面

想问一下边界条件sum = 0是指什么？

woshixuyoudan 发表于 2016-2-19 23:27
想问一下边界条件sum = 0是指什么？

我理解的是这样  比如数组 1,2,3 如果你要找的那个target = 0
然后你用acc来记录累积的和 这样acc-target就一直存在于哈希表里 就会返回true  但是这样是不对的

45分钟两个题目很难啊

1. (taili, tailj) * * * * * * * * *
   
2. * * * * * * * * * * * * * * * *
   
3. * * * * * * * * * * * * * * * *
   
4. * * * * * * * * *(headi, headj)
   
5. 
   
6. return subMatrixSum(cumMatrix, 0, 0, 0, 0);
   
7. 
   
8. boolean subMatrixSum(int[][] cum, int headi, int headj, int taili, int tailj, int target) {
   
9.         if (headi < taili || headj < tailj) {
   
10.                 return false;
    
11.         }
    
12.         int sum = subsum(cum, headi, headj, taili, tailj);
    
13.         if (sum == target) {
    
14.                 return true;
    
15.         } else if (sum > target) {
    
16.                 return subMatrixSum(cum, headi, headj, taili + 1, tailj, target) || sumMatrixSum(cum, headi, headj, taili, tailj + 1, target);
    
17.         } else {
    
18.                 return sumMatrixSum(cum, headi + 1, headj, taili, tailj) || sumMatrixSum(cum, headi, headj + 1, taili, tailj, target);
    
19.         }
    
20. }
    

复制代码

重排一下前面的代码

1. return subMatrixSum(cumMatrix, 0, 0, 0, 0);
   
2. 
   
3. Map<String, Boolean> dp = new HashMap<String, Boolean>();
   
4. boolean subMatrixSum(int[][] cum, int headi, int headj, int taili, int tailj, int target) {
   
5.         String key = headi + ":" + headj + ":" + taili + ":" + tailj;
   
6.         if (map.containsKey(key)) {
   
7.                 return map.get(key);
   
8.         } else {
   
9.                 boolean res = false;
   
10.                 if (headi < taili || headj < tailj) {
    
11.                         res = false;
    
12.                 } else {
    
13.                         int sum = subsum(cum, headi, headj, taili, tailj);
    
14.                         if (sum == target) {
    
15.                                 res = true;
    
16.                         } else if (sum > target) {
    
17.                                 res = subMatrixSum(cum, headi, headj, taili + 1, tailj, target) || sumMatrixSum(cum, headi, headj, taili, tailj + 1, target);
    
18.                         } else {
    
19.                                 res = sumMatrixSum(cum, headi + 1, headj, taili, tailj) || sumMatrixSum(cum, headi, headj + 1, taili, tailj, target);
    
20.                         }
    
21.                 }
    
22.                 map.put(key, res);
    
23.                 return res;
    
24.         }
    
25. }
    

复制代码

可以用DP优化一下，但是感觉复杂度还是O(n^4)

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

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

lintcode的subarray sum和submatrix sum吧

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

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

appleiiiii 发表于 2017-2-25 06:06
preprocess sum(i, j) which is the sum of all numbers from (0, 0) to (i, j), and use hashmap to store ...

你这个算出来的结果不是一个矩形把

这三哥也太狠了，实习生写这个题