[LintCode] Submatrix Sum

TesterHome 發布于2019-08-14 15:22 / 2321人閱讀

摘要：原理是這樣的先對矩陣的每個點到左頂點之間的子矩陣求和，存在新矩陣上。注意，代表的是到的子矩陣求和。說明從到行，從到列的子矩陣求和為，即相當于兩個平行放置的矩形，若左邊的值為，左邊與右邊之和也是，那么右邊的值一定為。

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;
    }
}

云服務器 GPU云服務器 Submatrix LintCode LintCode134_LRU sum

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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