[LintCode] Submatrix Sum

TesterHome 发布于2019-08-14 15:22 / 2249人阅读

摘要：原理是这样的先对矩阵的每个点到左顶点之间的子矩阵求和，存在新矩阵上。注意，代表的是到的子矩阵求和。说明从到行，从到列的子矩阵求和为，即相当于两个平行放置的矩形，若左边的值为，左边与右边之和也是，那么右边的值一定为。

Problem

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

Example

Given matrix

[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]

return [(1,1), (2,2)]

Challenge

O(n3) time.

Note

原理是这样的：
先对矩阵matrix的每个点到左顶点之间的子矩阵求和，存在新矩阵sum上。注意，sum[i+1][j+1]代表的是matrix[0][0]到matrix[i][j]的子矩阵求和。如下所示：

Given matrix[m][n]
------------------
[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]
Get sum[m+1][n+1]
-----------------
0  0  0  0
0  1  6  13
0  4  16 15
0  8  12 20

然后，我们进行这样的操作，从0开始，确定两行i1、i2，再将第k列的sum[i1][k]和sum[i2][k]相减，就得到matrix[i1][0]到matrix[i2][k-1]的子矩阵（i2-i1行，k列）求和diff，存入map。还是在这两行，假设计算到第j列，得到了相等的和diff。说明从i1到i2行，从k到j列的子矩阵求和为0，即相当于两个平行放置的矩形，若左边的值为diff，左边与右边之和也是diff，那么右边的值一定为0。下面是map中存放操作的例子：

diff-j chart
------------
diff    j

1       1       i1 = 0, i2 = 1
6       2
13      3
4       1       i1 = 0, i2 = 2
16      2
15      3
8       1       i1 = 0, i2 = 3
12      2
20      3
3       1       i1 = 1, i2 = 2
10      2
2       3
------------------------------
(above res has no same pair in same region)
7       1       i1 = 1, i2 = 3
6       2       
7       3       diff-j pair exists in map

res[0][0] = i1 = 1, res[0][1] = map.get(diff) = 1,
res[1][0] = i2 - 1 = 3 - 1 = 2, res[1][1] = j = 2,

so res = [(1, 1), (2, 2)]

Solution

public class Solution {
    public int[][] submatrixSum(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] sum = new int[m+1][n+1];
        int[][] res = new int[2][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i+1][j+1] = matrix[i][j] + sum[i][j+1] + sum[i+1][j] - sum[i][j];
            }
        }
        for (int i1 = 0; i1 < m; i1++) {
            for (int i2 = i1+1; i2 <= m; i2++) {
                Map map = new HashMap();
                for (int j = 0; j <= n; j++) {
                    int diff = sum[i2][j] - sum[i1][j];
                    if (map.containsKey(diff)) {
                        res[0][0] = i1; res[0][1] = map.get(diff);
                        res[1][0] = i2-1; res[1][1] = j-1;
                        return res;
                    }
                    else map.put(diff, j);
                }
            }
        }
        return res;
    }
}

服务器托管私有云 Submatrix LintCode LintCode134_LRU sum

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65710.html

Lintcode Coins in a line II

摘要：两个参赛者轮流从左边依次拿走或个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。请判定第一个玩家是输还是赢样例给定数组返回给定数组返回复杂度思路考虑先手玩家在状态，表示在在第的硬币的时候，这一位玩家能拿到的最高价值。 LintCode Coins in a line II 有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币，直...

2shou 2019-08-14 15:03 评论0 收藏0
LintCode Coins in a line III

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 评论0 收藏0
[LintCode] Subarray Sum

摘要：用记录数组每一位之前的包含当前位所有元素之和。若有重复的出现，说明之前的对应的元素的下一位到当前对应的第个元素之间所有元素和为，即为所求的子序列。 Problem Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of t...

shaonbean 2019-08-14 15:24 评论0 收藏0
[LintCode] Minimum Size Subarray Sum

摘要：做一个窗口，满足的左界到右界的距离最小值为所求。循环的约束条件要注意，不要遗漏不能超过的长度，但可以等于，因为存在所有元素之和为的极端情况。在时，先更新窗口为当前循环后的最小值，减去最左元素，指针后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...

hyuan 2019-08-14 15:16 评论0 收藏0
[LintCode/LeetCode] Gas Station

摘要：看到这个题目，怎样可以不把它当成一个环路来分析，以及减少多余的空间呢例如，我们引入单次剩余油量，剩余油量和，总剩余油量和，以及可行起点四个参数。大体上说，只要，一定有解。所以跳过这个耗油量很大的油站，然后将下一个油站作为起点继续判断即可。 Problem There are N gas stations along a circular route, where the amount ...

hedge_hog 2019-08-14 15:21 评论0 收藏0