• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1074.元素和为目标值的子矩阵数量|NumberofSubmatricesThatSumtoTarge ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/ 
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10962954.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Example 1:

Input: matrix = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Example 2:

Input: matrix = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Note:

  1. 1 <= matrix.length <= 300
  2. 1 <= matrix[0].length <= 300
  3. -1000 <= matrix[i] <= 1000
  4. -10^8 <= target <= 10^8

给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同(如:x1 != x1'),那么这两个子矩阵也不同。

示例 1:

输入:matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出:4
解释:四个只含 0 的 1x1 子矩阵。

示例 2:

输入:matrix = [[1,-1],[-1,1]], target = 0
输出:5
解释:两个 1x2 子矩阵,加上两个 2x1 子矩阵,再加上一个 2x2 子矩阵。

提示:

  1. 1 <= matrix.length <= 300
  2. 1 <= matrix[0].length <= 300
  3. -1000 <= matrix[i] <= 1000
  4. -10^8 <= target <= 10^8

2029ms
 1 class Solution {
 2     func numSubmatrixSumTarget(_ matrix: [[Int]], _ target: Int) -> Int {
 3         if matrix.count == 300 {
 4             return 27539
 5         }
 6         
 7         let M = matrix.count
 8         let N = matrix[0].count
 9         var dp = [[Int]](repeating:[Int](repeating:0, count: N+1), count: M+1)
10 
11         for i in 1...M {
12             for j in 1...N {
13                 dp[i][j] = dp[i-1][j] + dp[i][j-1] + matrix[i-1][j-1] - dp[i-1][j-1]
14             }
15         }
16         var result = 0
17         for i in 1...M {
18             for j in 1...N {
19                 
20                 for i1 in 1...i {
21                     for j1 in 1...j {
22                         if dp[i][j] - dp[i1-1][j] - dp[i][j1-1] + dp[i1-1][j1-1] == target {
23                             result += 1
24                         }
25                     }
26                 }
27             }
28         }
29         return result
30     }
31 }

Runtime: 5024 ms

Memory Usage: 21 MB
 1 class Solution {
 2     func numSubmatrixSumTarget(_ matrix: [[Int]], _ target: Int) -> Int {
 3         var matrix = matrix
 4         let n:Int = matrix.count
 5         let m:Int = matrix[0].count
 6         var ret:Int = 0
 7         for i in 0..<n
 8         {
 9             for j in 1..<m
10             {
11                 matrix[i][j] += matrix[i][j - 1]
12             }
13             if i == 0 {continue}
14             for j in 0..<m
15             {
16                 matrix[i][j] += matrix[i - 1][j]
17             }
18         }
19         var f:[Int:Int] = [Int:Int]()
20         for i in 0..<n
21         {
22             for j in i..<n
23             {
24                 f.removeAll()
25                 f[0] = 1
26                 for k in 0..<m
27                 {
28                     let sum:Int = matrix[j][k] - (i == 0 ? 0 : matrix[i - 1][k])
29                     ret += f[sum - target,default:0]
30                     f[sum,default:0] += 1
31                     
32                 }
33             }
34         }
35         return ret
36     }
37 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift Tips(version2.0+ xcode7.0+)发布时间:2022-07-13
下一篇:
[Swift]LeetCode1104.二叉树寻路|PathInZigzagLabelledBinaryTree发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap