Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2024/01/28 23:30)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串626/719 (看更多)

1074. Number of Submatrices That Sum to Target https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description 給你一個二維陣列表示的矩陣和一個 target，找出這個矩陣的所有子矩陣全部元素相加為0的有幾個。 https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg

思路： 1.遍歷所有的矩陣座標，以該座標為起點往右下角窮舉所有產生的子矩陣並檢查和是否等於 target，舉例來說以 (0,0) 為起點的話求的子矩陣順序會是 [0] [0,1] [0,1,0] [0 1] [0,1 1,1] [0,1,0 1,1,1] [0 1 0] [0,1 1,1 0,1] [0,1,0 1,1,1 0,1,0] 可以看出就是在找：第i列到第j行的和 + 第i-1列到第j行的和 + 第i-2列到第j行的和 + .... + 第0列到第j行的和判斷所有算出來的和是不是和target相等即可。 Java Code： ------------------------------------- class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int[] dp = new int[n]; for (int r = i; r < m; r++) { int sum = 0; for (int c = j; c < n; c++) { sum += matrix[r][c]; dp[c] = dp[c] + sum; if (dp[c] == target) { res++; } } } } } return res; } } ------------------------------------- -- https://i.imgur.com/AhrL1pB.jpg