Keshawn_lu's Blog

Leetcode 5454. 统计全 1 子矩形

动态规划 数组
字数统计: 862阅读时长: 3 min
2020/07/05 Share

题目简介：

给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

示例 3：

1
2
输入：mat = [[1,1,1,1,1,1]]
输出：21

示例 4：

1
2
输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
输出：5

提示：

  • 1 <= rows <= 150
  • 1 <= columns <= 150
  • 0 <= mat[i][j] <= 1

思路：

周赛做自闭的一道题，结束后看了题解以后搞懂了，还是智商问题…

首先动态规划，计算每个点前面连续的1的个数(行，包括自己)，即dp[i][j] = dp[i][j - 1] + 1，点为0的点不用计算，直接为0即可。

然后开始循环遍历，每次计算以mat[i][j]为右下角的矩阵个数，并累加到sum中。

然后关键的地方来了，如何计算矩阵个数呢？

我们定义一个min_len来保存以mat[i][j]所在列元素的dp[i][j]，即dp[i ... 0][j]。也就是每次保存构成矩阵的最小长度。

举个例子吧，如下图的矩阵，我们现在计算以mat[3][2]为右下角所构成的矩阵。

1
2
3
4
[0,0,1]
[0,1,1]
[1,1,1]
[1,1,1]

首先是第四行，dp[3][2] = 3，所以最小长度为3，所以sum += 3，这里计算的矩阵是只有第四行元素构成的矩阵，如下所示：

1
[1,1,1],   [1,1],   [1]

向上遍历，第三行时，dp[2][2] = 3，最小长度依然为3，sum += 3，这里计算的矩阵是第三、四行元素构成的矩阵，如下所示：

1
2
[1]    [1,1]    [1,1,1]
[1],   [1,1],   [1,1,1]

继续向上遍历，第二行时，dp[1][2] = 2，此时的最小长度变为2，sum += 2，这里计算的矩阵是第二、三、四行元素构成的矩阵，如下所示：

1
2
3
[1]    [1][1]
[1]    [1][1]
[1],   [1][1]

继续向上遍历，第一行时，dp[0][2] = 1，此时的最小长度变为1，sum += 1，这里计算的矩阵是第一、二、三、四行元素构成的矩阵，如下所示：

1
2
3
4
[1]
[1]
[1]
[1]

该点遍历结束。

循环结束后返回sum即可。

tip:

  • 先初始化dp[i][0]，处理边界问题。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {

        vector<vector<int>> dp(mat.size(), vector<int>(mat[0].size(), 0));

        int sum = 0;

        for(int i = 0; i < mat.size(); i++){

            dp[i][0] = mat[i][0];
        }

        for(int i = 0; i < mat.size(); i++){

            for(int j = 0; j < mat[i].size(); j++){
                
                if(mat[i][j] == 0){

                    dp[i][j] = 0;
                    continue;
                }
                int min_len = INT_MAX;

                if(j != 0)
                    dp[i][j] = dp[i][j - 1] + 1;    //有多少连续的1

                for(int k = i; k >= 0; k--){

                    min_len = min(min_len, dp[k][j]);
                    sum += min_len;
                }
            }
        }

        return sum;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网