Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2024-01-28 23:30:16
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:
作者: Murasakisalt (紫咲盐子-哈佛毕业生)   2023-01-28 23:30:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com