資訊專欄INFORMATION COLUMN
摘要：原理是這樣的先對(duì)矩陣的每個(gè)點(diǎn)到左頂點(diǎn)之間的子矩陣求和，存在新矩陣上。注意，代表的是到的子矩陣求和。說(shuō)明從到行，從到列的子矩陣求和為，即相當(dāng)于兩個(gè)平行放置的矩形，若左邊的值為，左邊與右邊之和也是，那么右邊的值一定為。
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.
ExampleGiven matrix
[ [1 ,5 ,7], [3 ,7 ,-8], [4 ,-8 ,9], ]
return [(1,1), (2,2)]
ChallengeO(n3) time.
Note原理是這樣的：
先對(duì)矩陣matrix的每個(gè)點(diǎn)到左頂點(diǎn)之間的子矩陣求和，存在新矩陣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
然后，我們進(jìn)行這樣的操作，從0開始，確定兩行i1、i2，再將第k列的sum[i1][k]和sum[i2][k]相減，就得到matrix[i1][0]到matrix[i2][k-1]的子矩陣（i2-i1行，k列）求和diff，存入map。還是在這兩行，假設(shè)計(jì)算到第j列，得到了相等的和diff。說(shuō)明從i1到i2行，從k到j(luò)列的子矩陣求和為0，即相當(dāng)于兩個(gè)平行放置的矩形，若左邊的值為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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65710.html
摘要：兩個(gè)參賽者輪流從左邊依次拿走或個(gè)硬幣，直到?jīng)]有硬幣為止。計(jì)算兩個(gè)人分別拿到的硬幣總價(jià)值，價(jià)值高的人獲勝。請(qǐng)判定第一個(gè)玩家是輸還是贏樣例給定數(shù)組返回給定數(shù)組返回復(fù)雜度思路考慮先手玩家在狀態(tài)，表示在在第的硬幣的時(shí)候，這一位玩家能拿到的最高價(jià)值。 LintCode Coins in a line II 有 n 個(gè)不同價(jià)值的硬幣排成一條線。兩個(gè)參賽者輪流從左邊依次拿走 1 或 2 個(gè)硬幣，直...
摘要：復(fù)雜度思路參考的思路，對(duì)于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價(jià)值。對(duì)于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個(gè)的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個(gè)值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...
摘要：用記錄數(shù)組每一位之前的包含當(dāng)前位所有元素之和。若有重復(fù)的出現(xiàn)，說(shuō)明之前的對(duì)應(yīng)的元素的下一位到當(dāng)前對(duì)應(yīng)的第個(gè)元素之間所有元素和為，即為所求的子序列。 Problem Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of t...
摘要：做一個(gè)窗口，滿足的左界到右界的距離最小值為所求。循環(huán)的約束條件要注意，不要遺漏不能超過(guò)的長(zhǎng)度，但可以等于，因?yàn)榇嬖谒性刂蜑榈臉O端情況。在時(shí)，先更新窗口為當(dāng)前循環(huán)后的最小值，減去最左元素，指針后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...
摘要：看到這個(gè)題目，怎樣可以不把它當(dāng)成一個(gè)環(huán)路來(lái)分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點(diǎn)四個(gè)參數(shù)。大體上說(shuō)，只要，一定有解。所以跳過(guò)這個(gè)耗油量很大的油站，然后將下一個(gè)油站作為起點(diǎn)繼續(xù)判斷即可。 Problem There are N gas stations along a circular route, where the amount ...
閱讀 2090·2023-04-25 22:50
閱讀 2884·2021-09-29 09:35
閱讀 3465·2021-07-29 10:20
閱讀 3244·2019-08-29 13:57
閱讀 3416·2019-08-29 13:50
閱讀 3098·2019-08-26 12:10
閱讀 3625·2019-08-23 18:41
閱讀 2694·2019-08-23 18:01
