❌

阅读视图

发现新文章，点击刷新页面。

[Python3/Java/C++/Go/TypeScript] 一题一解：求最小边界和最大边界（清晰题解）

✇LeetCode 每日一题题解
lcbin

方法一：求最小边界和最大边界

我们可以遍历 grid，找到所有 1 的最小边界，记为 $(x_1, y_1)$，最大边界，记为 $(x_2, y_2)$，那么最小矩形的面积就是 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$。

###python

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        x1 = y1 = inf
        x2 = y2 = -inf
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    x1 = min(x1, i)
                    y1 = min(y1, j)
                    x2 = max(x2, i)
                    y2 = max(y2, j)
        return (x2 - x1 + 1) * (y2 - y1 + 1)

###java

class Solution {
    public int minimumArea(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int x1 = m, y1 = n;
        int x2 = 0, y2 = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    x1 = Math.min(x1, i);
                    y1 = Math.min(y1, j);
                    x2 = Math.max(x2, i);
                    y2 = Math.max(y2, j);
                }
            }
        }
        return (x2 - x1 + 1) * (y2 - y1 + 1);
    }
}

###cpp

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int x1 = m, y1 = n;
        int x2 = 0, y2 = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    x1 = min(x1, i);
                    y1 = min(y1, j);
                    x2 = max(x2, i);
                    y2 = max(y2, j);
                }
            }
        }
        return (x2 - x1 + 1) * (y2 - y1 + 1);
    }
};

###go

func minimumArea(grid [][]int) int {
x1, y1 := len(grid), len(grid[0])
x2, y2 := 0, 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
x1, y1 = min(x1, i), min(y1, j)
x2, y2 = max(x2, i), max(y2, j)
}
}
}
return (x2 - x1 + 1) * (y2 - y1 + 1)
}

###ts

function minimumArea(grid: number[][]): number {
    const [m, n] = [grid.length, grid[0].length];
    let [x1, y1] = [m, n];
    let [x2, y2] = [0, 0];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1) {
                x1 = Math.min(x1, i);
                y1 = Math.min(y1, j);
                x2 = Math.max(x2, i);
                y2 = Math.max(y2, j);
            }
        }
    }
    return (x2 - x1 + 1) * (y2 - y1 + 1);
}

时间复杂度 $O(m \times n)$，其中 $m$ 和 $n$ 分别是 grid 的行数和列数。空间复杂度 $O(1)$。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

每日一题-包含所有 1 的最小矩形面积 I🟡

✇LeetCode 每日一题题解

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

 

示例 1：

输入： grid = [[0,1,0],[1,0,1]]

输出： 6

解释：

这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]

输出： 1

解释：

这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

 

提示：

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] 是 0 或 1。
  • 输入保证 grid 中至少有一个 1 。

枚举

✇LeetCode 每日一题题解
tsreaper

解法：枚举

经典题。求包含所有点的，边与坐标轴平行的矩形的最小面积。

矩形的上（下）边界即为所有点中纵坐标最大（小）的，矩形的左（右）边界即为所有点中横坐标最大（小）的。枚举所有点计算边界即可。复杂度 $\mathcal{O}(nm)$。

参考代码（c++）

###cpp

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int U = n, D = -1, L = m, R = -1;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j]) {
            U = min(U, i); D = max(D, i);
            L = min(L, j); R = max(R, j);
        }
        return (D - U + 1) * (R - L + 1);
    }
};

寻找矩形的左右上下边界（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

遍历 $\textit{grid}$：

  • 找到最左最右的 $1$ 的列号，分别记作 $\textit{left},\textit{right}$，则矩形底边长至少为 $\textit{right}-\textit{left}+1$。
  • 找到最上最下的 $1$ 的行号，分别记作 $\textit{top},\textit{bottom}$，则矩形高至少为 $\textit{bottom} - \textit{top} + 1$。

矩形面积至少为

$$
(\textit{right} - \textit{left} + 1) \cdot (\textit{bottom} - \textit{top} + 1)
$$

###py

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        left = top = inf
        right = bottom = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x:
                    left = min(left, j)
                    right = max(right, j)
                    top = min(top, i)
                    bottom = i
        return (right - left + 1) * (bottom - top + 1)

###java

class Solution {
    public int minimumArea(int[][] grid) {
        int left = Integer.MAX_VALUE;
        int right = 0;
        int top = Integer.MAX_VALUE;
        int bottom = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    left = Math.min(left, j);
                    right = Math.max(right, j);
                    top = Math.min(top, i);
                    bottom = i;
                }
            }
        }
        return (right - left + 1) * (bottom - top + 1);
    }
}

###cpp

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int left = INT_MAX, right = 0;
        int top = INT_MAX, bottom = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j]) {
                    left = min(left, j);
                    right = max(right, j);
                    top = min(top, i);
                    bottom = i;
                }
            }
        }
        return (right - left + 1) * (bottom - top + 1);
    }
};

###c

#define MIN(a, b) ((b) < (a) ? (b) : (a))
#define MAX(a, b) ((b) > (a) ? (b) : (a))

int minimumArea(int** grid, int gridSize, int* gridColSize) {
    int left = INT_MAX, right = 0;
    int top = INT_MAX, bottom = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j]) {
                left = MIN(left, j);
                right = MAX(right, j);
                top = MIN(top, i);
                bottom = i;
            }
        }
    }
    return (right - left + 1) * (bottom - top + 1);
}

###go

func minimumArea(grid [][]int) int {
left, right := math.MaxInt, 0
top, bottom := math.MaxInt, 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
left = min(left, j)
right = max(right, j)
top = min(top, i)
bottom = i
}
}
}
return (right - left + 1) * (bottom - top + 1)
}

###js

var minimumArea = function(grid) {
    let left = Infinity, right = 0;
    let top = Infinity, bottom = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j]) {
                left = Math.min(left, j);
                right = Math.max(right, j);
                top = Math.min(top, i);
                bottom = i;
            }
        }
    }
    return (right - left + 1) * (bottom - top + 1);
};

###rust

impl Solution {
    pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
        let mut left = usize::MAX;
        let mut right = 0;
        let mut top = usize::MAX;
        let mut bottom = 0;
        for (i, row) in grid.into_iter().enumerate() {
            for (j, x) in row.into_iter().enumerate() {
                if x != 0 {
                    left = left.min(j);
                    right = right.max(j);
                    top = top.min(i);
                    bottom = i;
                }
            }
        }
        ((right - left + 1) * (bottom - top + 1)) as _
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{grid}$ 的行数和列数。
  • 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

每日一题-统计全 1 子矩形🟡

✇LeetCode 每日一题题解

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

 

示例 1：

输入：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：

输入：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 。

 

提示：

  • 1 <= m, n <= 150
  • mat[i][j] 仅包含 0 或 1

【图解】两种方法：枚举上下边界 / 单调栈（Python/Java/C++/Go）

✇LeetCode 每日一题题解
endlesscheng

方法一：枚举子矩形的上下边界

枚举子矩形的上下边界，统计每一列的 $1$ 的个数，把原问题「压缩」为一维数组上的问题。

lc1504.jpg

在示例 2 中，假设现在枚举到子矩形的上边界为 $0$ 行，下边界为 $1$ 行，即 $\textit{mat}$ 的前两行。子矩形的高 $h=2$。

统计每一列的 $1$ 的个数，得到一个一维数组 $a=[0,2,2,1]$。我们要找的子矩形，就是 $a$ 的子数组。由于全 $1$ 子矩形的每一列都是 $1$，所以子数组的每一项都得是子矩形的高 $h=2$。问题变成：

  • 统计 $a$ 的全 $h$ 子数组的数目。

做法同 2348. 全 0 子数组的数目。

代码实现时，外层循环枚举上边界，内层循环枚举下边界。当下边界 $\textit{bottom}$ 加一时，只需把每个 $a[j]$ 都增加相应的 $\textit{mat}[\textit{bottom}][j]$，无需整个重新统计。

###py

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        ans = 0
        for top in range(m):  # 枚举上边界
            a = [0] * n
            for bottom in range(top, m):  # 枚举下边界
                h = bottom - top + 1  # 高
                # 2348. 全 h 子数组的数目
                last = -1
                for j in range(n):
                    a[j] += mat[bottom][j]  # 把 bottom 这一行的值加到 a 中
                    if a[j] != h:
                        last = j  # 记录上一个非 h 元素的位置
                    else:
                        ans += j - last
        return ans

###java

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int ans = 0;
        for (int top = 0; top < m; top++) { // 枚举上边界
            int[] a = new int[n];
            for (int bottom = top; bottom < m; bottom++) { // 枚举下边界
                int h = bottom - top + 1; // 高
                // 2348. 全 h 子数组的数目
                int last = -1;
                for (int j = 0; j < n; j++) {
                    a[j] += mat[bottom][j]; // 把 bottom 这一行的值加到 a 中
                    if (a[j] != h) {
                        last = j; // 记录上一个非 h 元素的位置
                    } else {
                        ans += j - last;
                    }
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int ans = 0;
        for (int top = 0; top < m; top++) { // 枚举上边界
            vector<int> a(n);
            for (int bottom = top; bottom < m; bottom++) { // 枚举下边界
                int h = bottom - top + 1; // 高
                // 2348. 全 h 子数组的数目
                int last = -1;
                for (int j = 0; j < n; j++) {
                    a[j] += mat[bottom][j]; // 把 bottom 这一行的值加到 a 中
                    if (a[j] != h) {
                        last = j; // 记录上一个非 h 元素的位置
                    } else {
                        ans += j - last;
                    }
                }
            }
        }
        return ans;
    }
};

###go

func numSubmat(mat [][]int) (ans int) {
    m, n := len(mat), len(mat[0])
    for top := range m { // 枚举上边界
        a := make([]int, n)
        for bottom := top; bottom < m; bottom++ { // 枚举下边界
            h := bottom - top + 1 // 高
            // 2348. 全 h 子数组的数目
            last := -1
            for j := range n {
                a[j] += mat[bottom][j] // 把 bottom 这一行的值加到 a 中
                if a[j] != h {
                    last = j // 记录上一个非 h 元素的位置
                } else {
                    ans += j - last
                }
            }
        }
    }
    return
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(m^2n)$，其中 $m$ 和 $n$ 分别为 $\textit{mat}$ 的行数和列数。
  • 空间复杂度：$\mathcal{O}(n)$。

方法二：单调栈

前置题目：85. 最大矩形，接着 我的题解 继续讲。

枚举子矩形的右下角（枚举底边，枚举右边界），有多少个对应的子矩形？

lc1504-c.png

举个例子。

lc1504.jpg

在示例 2 中，当我们枚举到最后一行时，柱子高度为 $\textit{heights}=[1,3,3,0]$。然后枚举子矩形的右边界：

  • 右边界为 $j=0$，子矩形只有 $1$ 个。
  • 右边界为 $j=1$，子矩形分成两类：
    • 左边界 $<1$。在右边界为 $j=0$ 时我们算出这有 $1$ 个，现在将其右边界扩展到 $j=1$，得到 $1$ 个新的子矩形。
    • 左边界 $\ge 1$。左边界只能是 $1$，矩形高度有 $1,2,3$ 共 $3$ 种，有 $1\times 3=3$ 个子矩形。
  • 右边界为 $j=2$，子矩形分成两类：
    • 左边界 $<1$。在右边界为 $j=0$ 时我们算出这有 $1$ 个，现在将其右边界扩展到 $j=2$，得到 $1$ 个新的子矩形。
    • 左边界 $\ge 1$。左边界可以是 $1,2$ 共 $2$ 种，矩形高度有 $1,2,3$ 共 $3$ 种，有 $2\times 3=6$ 个子矩形。
  • 右边界为 $j=3$，高度为 $0$，没有子矩形。

一般地，用 单调栈 计算小于 $\textit{heights}[j]$ 的左边最近柱子的位置 $\textit{left}$，把子矩形分成两类：

  • 左边界 $\le \textit{left}$。假设在右边界为 $j=\textit{left}$ 时我们算出这有 $f$ 个，现在将其右边界扩展到 $j$，得到 $f$ 个新的子矩形。
  • 左边界 $> \textit{left}$。矩形左边界可以是 $\textit{left}+1,\textit{left}+2,\ldots,j$，共 $j-\textit{left}$ 种；矩形高度可以是 $1,2,\ldots,\textit{heights}[j]$，共 $\textit{heights}[j]$ 种。所以有 $(j-\textit{left})\cdot \textit{heights}[j]$ 个子矩形。
  • 二者相加，就是右边界在 $j$ 的子矩形个数。加到答案中。

###py

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        heights = [0] * len(mat[0])
        ans = 0
        for row in mat:
            for j, x in enumerate(row):
                if x == 0:
                    heights[j] = 0
                else:
                    heights[j] += 1

            # (j, f, heights[j])
            st = [(-1, 0, -1)]  # 哨兵，方便处理 left=-1 的情况
            for j, h in enumerate(heights):
                while st[-1][2] >= h:
                    st.pop()
                left, f, _ = st[-1]
                # 计算底边为 row，右边界为 j 的子矩形个数
                # 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
                # 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
                f += (j - left) * h
                ans += f
                st.append((j, f, h))
        return ans

###java

class Solution {
    public int numSubmat(int[][] mat) {
        int n = mat[0].length;
        int[] heights = new int[n];
        int ans = 0;

        int[][] st = new int[n + 1][3]; // (j, f, heights[j])
        for (int[] row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    heights[j] = 0;
                } else {
                    heights[j]++;
                }
            }

            st[0][0] = st[0][2] = -1; // 哨兵，方便处理 left=-1 的情况
            int top = 0;
            for (int j = 0; j < n; j++) {
                int h = heights[j];
                while (st[top][2] >= h) {
                    top--; // 出栈
                }
                int left = st[top][0];
                int f = st[top][1];
                // 计算底边为 row，右边界为 j 的子矩形个数
                // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
                // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
                f += (j - left) * h;
                ans += f;
                top++;
                st[top][0] = j; // 入栈
                st[top][1] = f;
                st[top][2] = h;
            }
        }

        return ans;
    }
}

###cpp

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat[0].size();
        vector<int> heights(n);
        int ans = 0;

        for (auto& row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    heights[j] = 0;
                } else {
                    heights[j]++;
                }
            }

            stack<tuple<int, int, int>> st; // (j, f, heights[j])
            st.emplace(-1, 0, -1); // 哨兵，方便处理 left=-1 的情况
            for (int j = 0; j < n; j++) {
                int h = heights[j];
                while (get<2>(st.top()) >= h) {
                    st.pop();
                }
                auto [left, f, _] = st.top();
                // 计算底边为 row，右边界为 j 的子矩形个数
                // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
                // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
                f += (j - left) * h;
                ans += f;
                st.emplace(j, f, h);
            }
        }

        return ans;
    }
};

###go

func numSubmat(mat [][]int) (ans int) {
    heights := make([]int, len(mat[0]))
    for _, row := range mat {
        for j, x := range row {
            if x == 0 {
                heights[j] = 0
            } else {
                heights[j]++
            }
        }

        type tuple struct{ j, f, h int }
        st := []tuple{{-1, 0, -1}} // 哨兵，方便处理 left=-1 的情况
        for j, h := range heights {
            for st[len(st)-1].h >= h {
                st = st[:len(st)-1]
            }
            p := st[len(st)-1]
            left, f := p.j, p.f
            // 计算底边为 row，右边界为 j 的子矩形个数
            // 左边界 <= left 的矩形，每个矩形的右边界都可以扩展到 j，一共有 f 个
            // 左边界 >  left 的矩形，左边界有 j-left 种，高度有 h 种，一共有 (j-left)*h 个
            f += (j - left) * h
            ans += f
            st = append(st, tuple{j, f, h})
        }
    }
    return
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{mat}$ 的行数和列数。
  • 空间复杂度：$\mathcal{O}(n)$。

相似题目

见下面单调栈题单的「二、矩形」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

(多图预警！！！) 边统计边压缩，给你超详细的解答

✇LeetCode 每日一题题解
quantum-10

image.png

写在文首

看了很多题解，大家大致的思路基本一致，时间复杂度为O(n·n·m)，但大多题解没有把过程表述的很完整，作为一个刷题的小白，我想在这写写小白也能看懂的思路，和做这道题的一些细节和收获

解题思路

题目要求既要考虑1x2, 2x1的情况, 也要考虑2x2的情况：
(1)先考虑1xn的情况，即在一行中(横向)可以找出多少个矩形**(这步我称之为"统计")**，代码如下：
统计行中的矩形数目 int now = 0; for (int k = 0; k < col; k++){ if (mat[j][k] == 0) now = 0; else now = k == 0 ? mat[j][0] : now + 1; ans += now; }

  1. 当有连续三个1的时候，用now分别递增为1,2,3(第一个1可以形成一个矩形，第二个1和第一个1可以形成1个矩形加上其自身一共是两个，第三个1分别可以和前面连续的1形成两个长度分别为3,2的矩形，加上自身一共三个),并加到ans中
  2. 这一步也可以记录连续的个数,使用等差数列求和公式计算连续1处可以形成的矩形数目，具体代码不展示
  3. 当遍历到mat[j][k] == 0时，即1不连续了，置now为0，以便后面遇到连续1时进行统计

(2)压缩：

  1. 理论上，纵向的矩形也可以像横向那样进行统计，但是我们注意到我们不仅要求横向和纵向的矩形，还要求诸如2x2之类的
  2. 在(1)中我们得到所有大小为1的矩形和横向的各种大小的矩形的情况，所以后面我们只需要求纵向的大小大于1的矩形的情况即可
  3. 所以在这我们选择向下"压缩"题目所给二维数组，以便继续统计，这里"压缩"的思路理解好下次遇到类似的题能想出来就行，来看图吧

起始的二维数组
image.png

对其使用“按位与”进行压缩
image.png

第二次统计的结果
image.png

思考：这里我们可以发现第二次的统计是2xn的，既包含了2X1的情况也包含了2x2的情况，接下来的步骤继续如上循环"压缩"即可

代码

###java

class Solution {
    public int numSubmat(int[][] mat) {
        int row = mat.length, col = mat[0].length, ans = 0;

        for (int i = 0; i < row; i++){
            //统计
            for (int j = i; j < row; j++){
                int now = 0;
                for (int k = 0; k < col; k++){
                    if (mat[j][k] == 0) now = 0;
                    else now = k == 0 ? mat[j][0] : now + 1;
                    ans += now;
                }
            }
            //压缩
            for (int j = row - 1; j > i; j--){
                for (int k = 0; k < col; k++){
                    mat[j][k] = mat[j][k] & mat[j - 1][k];
                }
            }
        }
        return ans;
    }
}

希望这篇题解能让你看懂，喜欢的留下你宝贵的会心一赞吧，刷题之路，我们绝不言败！ヾ(◍°∇°◍)ﾉﾞ

5454. 统计全 1 子矩形

✇LeetCode 每日一题题解
linmiaomiao

解题思路

矩阵里每个点(i.j)统计他这行左边到他这个位置最多有几个连续的1，存为left[i][j]。然后对于每个点(i.j)，我们固定子矩形的右下角为(i.j)，利用left从该行i向上寻找子矩阵左上角为第k行的矩阵个数。每次将子矩阵个数加到答案中即可。
时间复杂度O(nnm)，空间复杂度O(nm)。

代码

###cpp

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int> > left(n,vector<int>(m));
        int now = 0;
        for(int i=0;i<n;i++){
            now = 0;
            for(int j=0;j<m;j++){
                if(mat[i][j] == 1) now ++;
                else now = 0;
                left[i][j] = now;
            }
        }
        int ans = 0,minx;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                minx = 0x3f3f3f3f;
                for(int k=i;k>=0;k--){
                    minx = min(left[k][j],minx);
                    ans += minx;
                }
            }
        }
        return ans;
    }
};

每日一题-统计全为 1 的正方形子矩阵🟡

✇LeetCode 每日一题题解

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

 

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

 

提示：

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

【图解】动态规划，简洁写法（Python/Java/C++/Go）

✇LeetCode 每日一题题解
endlesscheng

思路启发：学习 二维前缀和 对于想出本题的转移方程有帮助。

lc1277-c.png

整理上图中的结论。定义 $f_{i,j}$ 为右下角在 $(i,j)$ 的全 $1$ 正方形的最大边长。我们有

$$
f_{i,j} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i-1,j-1},f_{i-1,j},f_{i,j-1}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$

然而，当 $i=0$ 或者 $j=0$ 时，上式会产生负数下标 $-1$。

为避免出现负数下标，可以在 $f$ 矩阵的最上边添加一行 $0$，最左边添加一列 $0$，对应下标出界的状态（正方形的最大边长为 $0$）。

由于修改了 $f$，状态转移方程中的 $f$ 的下标要加一，即

$$
f_{i+1,j+1} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i,j},f_{i,j+1},f_{i+1,j}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$

注意 $\textit{matrix}$ 的下标是不用变的，因为我们只是在 $f$ 矩阵的上边和左边插入了 $0$，所以只有 $f$ 的下标受此影响需要加一。

初始值 $f_{0,j} = f_{i,0} = 0$。

根据图中的结论（个数等于最大边长），答案为整个 $f$ 矩阵的元素和。

优化前

###py

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                if x:
                    f[i + 1][j + 1] = min(f[i][j], f[i][j + 1], f[i + 1][j]) + 1
        return sum(map(sum, f))

###java

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] f = new int[m + 1][n + 1];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] > 0) {
                    f[i + 1][j + 1] = Math.min(Math.min(f[i][j], f[i][j + 1]), f[i + 1][j]) + 1;
                    ans += f[i + 1][j + 1];
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector f(m + 1, vector<int>(n + 1));
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]) {
                    f[i + 1][j + 1] = min({f[i][j], f[i][j + 1], f[i + 1][j]}) + 1;
                    ans += f[i + 1][j + 1];
                }
            }
        }
        return ans;
    }
};

###go

func countSquares(matrix [][]int) (ans int) {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i, row := range matrix {
for j, x := range row {
if x > 0 {
f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1
ans += f[i+1][j+1]
}
}
}
return
}

优化

直接把 $\textit{matrix}$ 当作 $f$，原地修改。

###py

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                if x and i and j:
                    row[j] += min(matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1])
        return sum(map(sum, matrix))

###java

class Solution {
    public int countSquares(int[][] matrix) {
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            for (int j = 0; j < row.length; j++) {
                if (row[j] > 0 && i > 0 && j > 0) {
                    row[j] += Math.min(Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]), row[j - 1]);
                }
                ans += row[j];
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int ans = 0;
        for (int i = 0; i < matrix.size(); i++) {
            auto& row = matrix[i];
            for (int j = 0; j < row.size(); j++) {
                if (i && j && row[j]) {
                    row[j] += min({matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1]});
                }
                ans += row[j];
            }
        }
        return ans;
    }
};

###go

func countSquares(matrix [][]int) (ans int) {
for i, row := range matrix {
for j, x := range row {
if x > 0 && i > 0 && j > 0 {
row[j] += min(matrix[i-1][j], matrix[i-1][j-1], row[j-1])
}
ans += row[j]
}
}
return
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{matrix}$ 的行数和列数。
  • 空间复杂度：优化前 $\mathcal{O}(mn)$，优化后 $\mathcal{O}(1)$。

专题训练

见下面动态规划题单的「§7.5 子矩形 DP」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

统计全为 1 的正方形子矩阵

✇LeetCode 每日一题题解
LeetCode-Solution

方法一：动态规划

思路

我们用 $f[i][j]$ 表示以 $(i, j)$ 为右下角的正方形的最大边长，那么除此定义之外，$f[i][j] = x$ 也表示以 $(i, j)$ 为右下角的正方形的数目为 $x$（即边长为 $1, 2, \cdots, x$ 的正方形各一个）。在计算出所有的 $f[i][j]$ 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。

我们尝试挖掘 $f[i][j]$ 与相邻位置的关系来计算出 $f[i][j]$ 的值。

fig1

如上图所示，若对于位置 $(i, j)$ 有 $f[i][j] = 4$，我们将以 $(i, j)$ 为右下角、边长为 $4$ 的正方形涂上色，可以发现其左侧位置 $(i, j - 1)$，上方位置 $(i - 1, j)$ 和左上位置 $(i - 1, j - 1)$ 均可以作为一个边长为 $4 - 1 = 3$ 的正方形的右下角。也就是说，这些位置的的 $f$ 值至少为 $3$，即：

  • $f[i][j - 1] \ge f[i][j] - 1$
  • $f[i - 1][j] \ge f[i][j] - 1$
  • $f[i - 1][j - 1] \ge f[i][j] - 1$

将这三个不等式联立，可以得到：

$$\texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])\ge f[i][j]−1$$

这是我们通过固定 $f[i][j]$ 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 $f[i][j]$ 相邻位置的值，得到另外的限制条件。

fig2

如上图所示，假设 $f[i][j - 1]$，$f[i - 1][j]$ 和 $f[i - 1][j - 1]$ 中的最小值为 $3$，即，$(i, j - 1)$，$(i - 1, j)$ 和 $(i - 1, j - 1)$ 均可以作为一个边长为 $3$ 的正方形的右下角。我们将这些边长为 $3$ 的正方形依次涂上色，可以发现，如果位置 $(i, j)$ 的元素为 $1$，那么它可以作为一个边长为 $4$ 的正方形的右下角，$f$ 值至少为 $4$，即：

$$f[i][j]\geq \texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])+1$$

将其与上一个不等式联立，可以得到：

$$f[i][j] = \texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])+1$$

再考虑一些边界情况，我们就得到了完整的递推式：

$$
f[i][j] =
\begin{cases}
matrix[i][j] & \texttt{if } i=0 \texttt{ or } j=0 \
0 & \texttt{if } matrix[i][j]=0 \
\min(f[i][j-1], f[i-1][j], f[i-1][j-1]) + 1 & \texttt{otherwise}
\end{cases}
$$

我们按照行优先的顺序依次计算 $f[i][j]$ 的值，累加就可以得到最终的答案。

代码

###Python

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0] * n for _ in range(m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    f[i][j] = matrix[i][j]
                elif matrix[i][j] == 0:
                    f[i][j] = 0
                else:
                    f[i][j] = min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1
                ans += f[i][j]
        return ans

###C++

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> f(m, vector<int>(n, 0));
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    f[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 0) {
                    f[i][j] = 0;
                } else {
                    f[i][j] = min({f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]}) + 1;
                }
                ans += f[i][j];
            }
        }
        return ans;
    }
};

###Java

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] f = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    f[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 0) {
                    f[i][j] = 0;
                } else {
                    f[i][j] = Math.min(Math.min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1;
                }
                ans += f[i][j];
            }
        }
        return ans;
    }
}

###C#

public class Solution {
    public int CountSquares(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int[,] f = new int[m, n];
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    f[i, j] = matrix[i][j];
                } else if (matrix[i][j] == 0) {
                    f[i, j] = 0;
                } else {
                    f[i, j] = Math.Min(Math.Min(f[i, j - 1], f[i - 1, j]), f[i - 1, j - 1]) + 1;
                }
                ans += f[i, j];
            }
        }
        return ans;
    }
}

###Go

func countSquares(matrix [][]int) int {
    m, n := len(matrix), len(matrix[0])
    f := make([][]int, m)
    for i := range f {
        f[i] = make([]int, n)
    }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 || j == 0 {
                f[i][j] = matrix[i][j]
            } else if matrix[i][j] == 0 {
                f[i][j] = 0
            } else {
                f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1
            }
            ans += f[i][j]
        }
    }
    return ans
}

###C

int countSquares(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize, n = matrixColSize[0];
    int** f = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; ++i) {
        f[i] = (int*)malloc(n * sizeof(int));
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 || j == 0) {
                f[i][j] = matrix[i][j];
            } else if (matrix[i][j] == 0) {
                f[i][j] = 0;
            } else {
                f[i][j] = fmin(f[i][j - 1], fmin(f[i - 1][j], f[i - 1][j - 1])) + 1;
            }
            ans += f[i][j];
        }
    }
    for (int i = 0; i < m; ++i) {
        free(f[i]);
    }
    free(f);
    return ans;
}

###JavaScript

var countSquares = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i === 0 || j === 0) {
                f[i][j] = matrix[i][j];
            } else if (matrix[i][j] === 0) {
                f[i][j] = 0;
            } else {
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1;
            }
            ans += f[i][j];
        }
    }
    return ans;
};

###TypeScript

function countSquares(matrix: number[][]): number {
    const m = matrix.length, n = matrix[0].length;
    const f: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0));
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i === 0 || j === 0) {
                f[i][j] = matrix[i][j];
            } else if (matrix[i][j] === 0) {
                f[i][j] = 0;
            } else {
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1;
            }
            ans += f[i][j];
        }
    }
    return ans;
}

###Rust

impl Solution {
    pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut f = vec![vec![0; n]; m];
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                if i == 0 || j == 0 {
                    f[i][j] = matrix[i][j];
                } else if matrix[i][j] == 0 {
                    f[i][j] = 0;
                } else {
                    f[i][j] = f[i][j - 1].min(f[i - 1][j]).min(f[i - 1][j - 1]) + 1;
                }
                ans += f[i][j];
            }
        }
        ans
    }
}

复杂度分析

  • 时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 是输入 $\textit{matrix}$ 的行和列。

  • 空间复杂度：$O(m\times n)$。

【统计全为 1 的正方形子矩阵】非常朴素（暴力）的dp及优化

✇LeetCode 每日一题题解
97wgl

题目描述

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：

matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]

输出： 15

解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：
输入：

matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

输出： 7

解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

思路

首先，暴力解就是以矩阵每一个点为起点，依次判断边长为1，2，3，...，min{m, n}的区域是否是全1正方形(该区域所有点的和等于该区域面积)，显然，这种复杂度是过不了的。

很容易知道，上述过程在判断较大区域是否为正方形的时候，并没有用到前面计算的结果，每一次判断都从头开始。这也是复杂度过高的原因。

那么怎么利用之前判断过的结果呢？举个例子，比如我要判断以(2, 3)为右下角边长为3的正方形区域（红色边框区域）是否是全为1：

  • 先判断(i, j)位置是否为1，如果否，则显然不满足；如果是，进行下一步判断
  • 判断分别以(i - 1, j), (i - 1, j - 1), (i, j - 1)为右下角的区域是否能构成边长为2的正方形，如果能，那就满足条件。
    image.png

基于上述，我们可以看出思路大致跟最大正方形那题差不多，设dp[i][j][k]表示以(i, j)为右下角，边长为k的正方形区域是否全为1，那么易得出如下状态转移方程：

###java

dp[i][j][k] = (matrix[i][j] == 1 && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1] [k - 1]);

代码

###java

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int len = Math.min(m, n);
        boolean[][][] dp = new boolean[m][n][len];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][0] = (matrix[i][j] == 1);
                count += dp[i][j][0] ? 1 : 0;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                for (int k = 1; k < len; k++) {
                    dp[i][j][k] = (matrix[i][j] == 1 && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1] [k - 1]);
                    if (dp[i][j][k]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

}

更新

经评论区@da-fei-kai提醒，上述代码可以做进一步优化。

首先，题目并不关心边长为1,2,...,k的各有多少个，并且我们知道，以(i, j)为右下角边长为k的正方形全为1的话，那么以(i, j)为右下角边长分别为1,2,...,k - 1的正方形区域一定是全为1，如下图：

image.png

上图中，如果红色区域是边长为3的全1正方形区域，那么它一定包含了一个边长为2和边长为1的全1正方形区域。所以，我们只需记录以(i, j)为右下角的区域包含的最大全1正方形边长即可，这个最大边长也即以(i , j)为右下角的全1正方形的个数.
那么基于此，我们就可以将原始的dp降一维度，设dp[i][j]表示以(i, j)为右下角的最大全1正方形区域的边长，则有如下状态转移方程：

###java

dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;

这就和最大正方形那题的状态转移方程完全一样了。

代码

###java

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int ans = 0;
        // 预处理每一行和每一列
        for (int i = 0; i < m; i++) {
            ans += dp[i][0] = matrix[i][0];
        }
        for (int j = 0; j < n; j++) {
            ans += dp[0][j] = matrix[0][j];
        }
        // 上述过程(0, 0)判断了两次, 如果matrix[0][0] == 1，说明ans多算了一个
        if (matrix[0][0] == 1) {
            ans--;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 1) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    ans += dp[i][j];
                }
            }
        }
        return ans;
    }
}

每日一题-全 0 子数组的数目🟡

✇LeetCode 每日一题题解

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

 

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

 

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

两种更具一般性的方法：滑动窗口/增量法（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

前言

本题做法很多，下面讲两个更具一般性的方法。

方法一：用滑动窗口思考

子数组越长，越可能包含非零元素，不满足题目要求；子数组越短，越可能全为 $0$，满足题目要求。我们枚举子数组的右端点，当右端点变大（子数组变长）的时候，子数组左端点要么不变，要么也变大。

不仅是本题，有这样性质的题目，都可以用滑动窗口解决，见 滑动窗口【基础算法精讲 03】。

本题属于「越短越合法」型滑动窗口。由于题目的特殊性，有更简单的解决方法：

  1. 记录上一个非零数字的位置 $\textit{last}$。那么 $\textit{last}+1$ 就是窗口的左端点。
  2. 当子数组右端点在 $i$ 时，子数组左端点可以是 $\textit{last}+1,\textit{last}+2,\dots,i$，一共有 $i-\textit{last}$ 个，加入答案。

示例 1 的 $\textit{nums} = [1,3,0,0,2,0,0,4]$，当右端点在 $i=3$ 时，$\textit{last}=1$，我们找到了 $i-\textit{last}=2$ 个右端点在 $3$ 的全 $0$ 子数组，加入答案。

为了兼容 $\textit{nums}=[0,0,0,2,0,0]$ 这种一开始就是 $0$ 的情况，初始化 $\textit{last}=-1$。

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        last = -1
        for i, x in enumerate(nums):
            if x:
                last = i  # 记录上一个非 0 元素的位置
            else:
                ans += i - last
        return ans

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long ans = 0;
        int last = -1;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (x != 0) {
                last = i; // 记录上一个非 0 元素的位置
            } else {
                ans += i - last;
            }
        }
        return ans;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long ans = 0;
        int last = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]) {
                last = i; // 记录上一个非 0 元素的位置
            } else {
                ans += i - last;
            }
        }
        return ans;
    }
};

long long zeroFilledSubarray(int* nums, int numsSize) {
    long long ans = 0;
    int last = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i]) {
            last = i; // 记录上一个非 0 元素的位置
        } else {
            ans += i - last;
        }
    }
    return ans;
}

func zeroFilledSubarray(nums []int) (ans int64) {
last := -1
for i, x := range nums {
if x != 0 {
last = i // 记录上一个非 0 元素的位置
} else {
ans += int64(i - last)
}
}
return
}

var zeroFilledSubarray = function(nums) {
    let ans = 0;
    let last = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            last = i; // 记录上一个非 0 元素的位置
        } else {
            ans += i - last;
        }
    }
    return ans;
};

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut last = -1;
        for (i, x) in nums.into_iter().enumerate() {
            let i = i as i64;
            if x != 0 {
                last = i; // 记录上一个非 0 元素的位置
            } else {
                ans += (i - last) as i64;
            }
        }
        ans
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
  • 空间复杂度：$\mathcal{O}(1)$。

方法二：增量法

遍历到 $\textit{nums}[i]=0$，现在来计算右端点为 $i$ 的全 $0$ 子数组的个数。

我们可以在右端点为 $i-1$ 的全 $0$ 子数组的末尾添加一个 $0$。比如右端点为 $i-1$ 的全 $0$ 子数组有 $5$ 个，那么在这 $5$ 个子数组的末尾添加 $\textit{nums}[i]=0$，再算上 $\textit{nums}[i]$ 单独组成一个长为 $1$ 的子数组，我们得到了 $5+1=6$ 个右端点为 $i$ 的全 $0$ 子数组，加入答案。

具体来说：

  1. 用一个计数器 $\textit{cnt}_0$ 统计遍历到的连续 $0$ 的个数。
  2. 如果 $\textit{nums}[i]\ne 0$，把计数器重置为 $0$。
  3. 否则，把 $\textit{cnt}_0$ 加一，表示右端点为 $i$ 的全 $0$ 子数组比右端点为 $i-1$ 的全 $0$ 子数组多一个。然后把 $\textit{cnt}_0$ 加到答案中。
class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = cnt0 = 0
        for x in nums:
            if x:
                cnt0 = 0
            else:
                cnt0 += 1  # 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0
        return ans

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long ans = 0;
        int cnt0 = 0;
        for (int x : nums) {
            if (x != 0) {
                cnt0 = 0;
            } else {
                cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0;
            }
        }
        return ans;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long ans = 0;
        int cnt0 = 0;
        for (int x : nums) {
            if (x) {
                cnt0 = 0;
            } else {
                cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0;
            }
        }
        return ans;
    }
};

long long zeroFilledSubarray(int* nums, int numsSize) {
    long long ans = 0;
    int cnt0 = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i]) {
            cnt0 = 0;
        } else {
            cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
            ans += cnt0;
        }
    }
    return ans;
}

func zeroFilledSubarray(nums []int) (ans int64) {
cnt0 := 0
for _, x := range nums {
if x != 0 {
cnt0 = 0
} else {
cnt0++ // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += int64(cnt0)
}
}
return
}

var zeroFilledSubarray = function(nums) {
    let ans = 0;
    let cnt0 = 0;
    for (const x of nums) {
        if (x !== 0) {
            cnt0 = 0;
        } else {
            cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
            ans += cnt0;
        }
    }
    return ans;
};

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut cnt0 = 0;
        for x in nums {
            if x != 0 {
                cnt0 = 0;
            } else {
                cnt0 += 1; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
                ans += cnt0 as i64;
            }
        }
        ans
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
  • 空间复杂度：$\mathcal{O}(1)$。

注：本题还有其他方法，例如找极大连续 $0$ 的长度，然后用等差数列计算。

相似题目

413. 等差数列划分

专题训练

方法一：滑动窗口题单的「§2.3.1 越短越合法」。

方法二：动态规划题单「§7.3 子数组 DP」的「思维扩展」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

groupby 分组

✇LeetCode 每日一题题解
981377660LMT

代码

###python3

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        groups = [(char, len(list(group))) for char, group in groupby(nums)]
        return sum(count * (count + 1) // 2 for char, count in groups if char == 0)

「动态规划」Java

✇LeetCode 每日一题题解
t5un4m1

解题思路

统计连续0出现的次数，即为构成当前子数组的数量：

一个0，构成数组：

[0] //第一个0

两个0，构成数组：

[0]     //第一个0

[0,0]   //第一个0和第二个0
[0]     //第二个0

三个0，构成数组：

三个0包含两个0的所有情况：
[0]     //第一个0
[0,0]   //第一个0和第二个0
[0]     //第二个0

两个0的所有情况+第三个0
[0]     //第一个0           和第三个0（以[0]单独构成子数组）
[0,0,0] //第一个0和第二个0   和第三个0
[0,0]   //第二个0           和第三个0

可得:每多一个连续的0, 都可以和上一个0所构成的子数组 构成一个新的子数组。

状态转移方程：

连续的n个0对答案的贡献 = 连续的n-1个0对答案的贡献  + n

代码

###java

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long count = 0;//答案
        int zeroCnt = 0;//当前0的个数
        for (int x : nums) {
            if (x == 0) {
                zeroCnt++;
                count += zeroCnt;
            } else {
                zeroCnt = 0;
            }
        }
        return count;
    }
}

每日一题-24 点游戏🔴

✇LeetCode 每日一题题解

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

  • 除法运算符 '/' 表示实数除法，而不是整数除法。
    • 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
  • 每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
    • 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
  • 你不能把数字串在一起
    • 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

 

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

 

提示:

  • cards.length == 4
  • 1 <= cards[i] <= 9

Java 回溯, 经典面试题

✇LeetCode 每日一题题解
airmelt

微软一面平行面出了这个题, 比这个还麻烦, 给的输入是 n 个数字
用的 Java 回溯解决的, 第一轮已经通过
提一下需要注意的细节

  1. 不要使用魔法数字 24, 1e-6 等, 需要使用有意义的变量代替
  2. double 类型不能使用 "==", 需要用做差和一个较小的值比较判断
  3. 将函数拆分成几个小的函数分别求解, 可以先提出思路和写一个空函数
  4. 从 2 个数字开始逐步扩展
  5. 注意不能产生除 0 错误
  6. 一旦回溯有一条路能产生 true 需要立即返回

###Java

class Solution {
    private static final double TARGET = 24;
    private static final double EPISLON = 1e-6;
    
    public boolean judgePoint24(int[] cards) {
        return helper(new double[]{ cards[0], cards[1], cards[2], cards[3] });
    }
    
    private boolean helper(double[] nums) {
        if (nums.length == 1) return Math.abs(nums[0] - TARGET) < EPISLON;
        // 每次选择两个不同的数进行回溯
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                // 将选择出来的两个数的计算结果和原数组剩下的数加入 next 数组
                double[] next = new double[nums.length - 1];
                for (int k = 0, pos = 0; k < nums.length; k++) if (k != i && k != j) next[pos++] = nums[k];
                for (double num : calculate(nums[i], nums[j])) {
                    next[next.length - 1] = num;
                    if (helper(next)) return true;
                }
            }
        }
        return false;
    }
    
    private List<Double> calculate(double a, double b) {
        List<Double> list = new ArrayList<>();
        list.add(a + b);
        list.add(a - b);
        list.add(b - a);
        list.add(a * b);
        if (!(Math.abs(b) < EPISLON)) list.add(a / b);
        if (!(Math.abs(a) < EPISLON)) list.add(b / a);
        return list;
    }
}

Python一行大法好!

###Python

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        return sorted(nums) in [[1, 1, 1, 8], [1, 1, 2, 6], [1, 1, 2, 7], [1, 1, 2, 8], [1, 1, 2, 9], [1, 1, 3, 4], [1, 1, 3, 5], [1, 1, 3, 6], [1, 1, 3, 7], [1, 1, 3, 8], [1, 1, 3, 9], [1, 1, 4, 4], [1, 1, 4, 5], [1, 1, 4, 6], [1, 1, 4, 7], [1, 1, 4, 8], [1, 1, 4, 9], [1, 1, 5, 5], [1, 1, 5, 6], [1, 1, 5, 7], [1, 1, 5, 8], [1, 1, 6, 6], [1, 1, 6, 8], [1, 1, 6, 9], [1, 1, 8, 8], [1, 2, 2, 4], [1, 2, 2, 5], [1, 2, 2, 6], [1, 2, 2, 7], [1, 2, 2, 8], [1, 2, 2, 9], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 8], [1, 2, 3, 9], [1, 2, 4, 4], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4, 7], [1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5, 5], [1, 2, 5, 6], [1, 2, 5, 7], [1, 2, 5, 8], [1, 2, 5, 9], [1, 2, 6, 6], [1, 2, 6, 7], [1, 2, 6, 8], [1, 2, 6, 9], [1, 2, 7, 7], [1, 2, 7, 8], [1, 2, 7, 9], [1, 2, 8, 8], [1, 2, 8, 9], [1, 3, 3, 3], [1, 3, 3, 4], [1, 3, 3, 5], [1, 3, 3, 6], [1, 3, 3, 7], [1, 3, 3, 8], [1, 3, 3, 9], [1, 3, 4, 4], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4, 7], [1, 3, 4, 8], [1, 3, 4, 9], [1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 5, 9], [1, 3, 6, 6], [1, 3, 6, 7], [1, 3, 6, 8], [1, 3, 6, 9], [1, 3, 7, 7], [1, 3, 7, 8], [1, 3, 7, 9], [1, 3, 8, 8], [1, 3, 8, 9], [1, 3, 9, 9], [1, 4, 4, 4], [1, 4, 4, 5], [1, 4, 4, 6], [1, 4, 4, 7], [1, 4, 4, 8], [1, 4, 4, 9], [1, 4, 5, 5], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 5, 9], [1, 4, 6, 6], [1, 4, 6, 7], [1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 7], [1, 4, 7, 8], [1, 4, 7, 9], [1, 4, 8, 8], [1, 4, 8, 9], [1, 5, 5, 5], [1, 5, 5, 6], [1, 5, 5, 9], [1, 5, 6, 6], [1, 5, 6, 7], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [1, 5, 8, 8], [1, 5, 8, 9], [1, 5, 9, 9], [1, 6, 6, 6], [1, 6, 6, 8], [1, 6, 6, 9], [1, 6, 7, 9], [1, 6, 8, 8], [1, 6, 8, 9], [1, 6, 9, 9], [1, 7, 7, 9], [1, 7, 8, 8], [1, 7, 8, 9], [1, 7, 9, 9], [1, 8, 8, 8], [1, 8, 8, 9], [2, 2, 2, 3], [2, 2, 2, 4], [2, 2, 2, 5], [2, 2, 2, 7], [2, 2, 2, 8], [2, 2, 2, 9], [2, 2, 3, 3], [2, 2, 3, 4], [2, 2, 3, 5], [2, 2, 3, 6], [2, 2, 3, 7], [2, 2, 3, 8], [2, 2, 3, 9], [2, 2, 4, 4], [2, 2, 4, 5], [2, 2, 4, 6], [2, 2, 4, 7], [2, 2, 4, 8], [2, 2, 4, 9], [2, 2, 5, 5], [2, 2, 5, 6], [2, 2, 5, 7], [2, 2, 5, 8], [2, 2, 5, 9], [2, 2, 6, 6], [2, 2, 6, 7], [2, 2, 6, 8], [2, 2, 6, 9], [2, 2, 7, 7], [2, 2, 7, 8], [2, 2, 8, 8], [2, 2, 8, 9], [2, 3, 3, 3], [2, 3, 3, 5], [2, 3, 3, 6], [2, 3, 3, 7], [2, 3, 3, 8], [2, 3, 3, 9], [2, 3, 4, 4], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4, 7], [2, 3, 4, 8], [2, 3, 4, 9], [2, 3, 5, 5], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 5, 9], [2, 3, 6, 6], [2, 3, 6, 7], [2, 3, 6, 8], [2, 3, 6, 9], [2, 3, 7, 7], [2, 3, 7, 8], [2, 3, 7, 9], [2, 3, 8, 8], [2, 3, 8, 9], [2, 3, 9, 9], [2, 4, 4, 4], [2, 4, 4, 5], [2, 4, 4, 6], [2, 4, 4, 7], [2, 4, 4, 8], [2, 4, 4, 9], [2, 4, 5, 5], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 5, 9], [2, 4, 6, 6], [2, 4, 6, 7], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 7], [2, 4, 7, 8], [2, 4, 7, 9], [2, 4, 8, 8], [2, 4, 8, 9], [2, 4, 9, 9], [2, 5, 5, 7], [2, 5, 5, 8], [2, 5, 5, 9], [2, 5, 6, 6], [2, 5, 6, 7], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 7], [2, 5, 7, 8], [2, 5, 7, 9], [2, 5, 8, 8], [2, 5, 8, 9], [2, 6, 6, 6], [2, 6, 6, 7], [2, 6, 6, 8], [2, 6, 6, 9], [2, 6, 7, 8], [2, 6, 7, 9], [2, 6, 8, 8], [2, 6, 8, 9], [2, 6, 9, 9], [2, 7, 7, 8], [2, 7, 8, 8], [2, 7, 8, 9], [2, 8, 8, 8], [2, 8, 8, 9], [2, 8, 9, 9], [3, 3, 3, 3], [3, 3, 3, 4], [3, 3, 3, 5], [3, 3, 3, 6], [3, 3, 3, 7], [3, 3, 3, 8], [3, 3, 3, 9], [3, 3, 4, 4], [3, 3, 4, 5], [3, 3, 4, 6], [3, 3, 4, 7], [3, 3, 4, 8], [3, 3, 4, 9], [3, 3, 5, 5], [3, 3, 5, 6], [3, 3, 5, 7], [3, 3, 5, 9], [3, 3, 6, 6], [3, 3, 6, 7], [3, 3, 6, 8], [3, 3, 6, 9], [3, 3, 7, 7], [3, 3, 7, 8], [3, 3, 7, 9], [3, 3, 8, 8], [3, 3, 8, 9], [3, 3, 9, 9], [3, 4, 4, 4], [3, 4, 4, 5], [3, 4, 4, 6], [3, 4, 4, 7], [3, 4, 4, 8], [3, 4, 4, 9], [3, 4, 5, 5], [3, 4, 5, 6], [3, 4, 5, 7], [3, 4, 5, 8], [3, 4, 5, 9], [3, 4, 6, 6], [3, 4, 6, 8], [3, 4, 6, 9], [3, 4, 7, 7], [3, 4, 7, 8], [3, 4, 7, 9], [3, 4, 8, 9], [3, 4, 9, 9], [3, 5, 5, 6], [3, 5, 5, 7], [3, 5, 5, 8], [3, 5, 5, 9], [3, 5, 6, 6], [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9], [3, 5, 7, 8], [3, 5, 7, 9], [3, 5, 8, 8], [3, 5, 8, 9], [3, 5, 9, 9], [3, 6, 6, 6], [3, 6, 6, 7], [3, 6, 6, 8], [3, 6, 6, 9], [3, 6, 7, 7], [3, 6, 7, 8], [3, 6, 7, 9], [3, 6, 8, 8], [3, 6, 8, 9], [3, 6, 9, 9], [3, 7, 7, 7], [3, 7, 7, 8], [3, 7, 7, 9], [3, 7, 8, 8], [3, 7, 8, 9], [3, 7, 9, 9], [3, 8, 8, 8], [3, 8, 8, 9], [3, 8, 9, 9], [3, 9, 9, 9], [4, 4, 4, 4], [4, 4, 4, 5], [4, 4, 4, 6], [4, 4, 4, 7], [4, 4, 4, 8], [4, 4, 4, 9], [4, 4, 5, 5], [4, 4, 5, 6], [4, 4, 5, 7], [4, 4, 5, 8], [4, 4, 6, 8], [4, 4, 6, 9], [4, 4, 7, 7], [4, 4, 7, 8], [4, 4, 7, 9], [4, 4, 8, 8], [4, 4, 8, 9], [4, 5, 5, 5], [4, 5, 5, 6], [4, 5, 5, 7], [4, 5, 5, 8], [4, 5, 5, 9], [4, 5, 6, 6], [4, 5, 6, 7], [4, 5, 6, 8], [4, 5, 6, 9], [4, 5, 7, 7], [4, 5, 7, 8], [4, 5, 7, 9], [4, 5, 8, 8], [4, 5, 8, 9], [4, 5, 9, 9], [4, 6, 6, 6], [4, 6, 6, 7], [4, 6, 6, 8], [4, 6, 6, 9], [4, 6, 7, 7], [4, 6, 7, 8], [4, 6, 7, 9], [4, 6, 8, 8], [4, 6, 8, 9], [4, 6, 9, 9], [4, 7, 7, 7], [4, 7, 7, 8], [4, 7, 8, 8], [4, 7, 8, 9], [4, 7, 9, 9], [4, 8, 8, 8], [4, 8, 8, 9], [4, 8, 9, 9], [5, 5, 5, 5], [5, 5, 5, 6], [5, 5, 5, 9], [5, 5, 6, 6], [5, 5, 6, 7], [5, 5, 6, 8], [5, 5, 7, 7], [5, 5, 7, 8], [5, 5, 8, 8], [5, 5, 8, 9], [5, 5, 9, 9], [5, 6, 6, 6], [5, 6, 6, 7], [5, 6, 6, 8], [5, 6, 6, 9], [5, 6, 7, 7], [5, 6, 7, 8], [5, 6, 7, 9], [5, 6, 8, 8], [5, 6, 8, 9], [5, 6, 9, 9], [5, 7, 7, 9], [5, 7, 8, 8], [5, 7, 8, 9], [5, 8, 8, 8], [5, 8, 8, 9], [6, 6, 6, 6], [6, 6, 6, 8], [6, 6, 6, 9], [6, 6, 7, 9], [6, 6, 8, 8], [6, 6, 8, 9], [6, 7, 8, 9], [6, 7, 9, 9], [6, 8, 8, 8], [6, 8, 8, 9], [6, 8, 9, 9], [7, 8, 8, 9]]

【详解】递归回溯，考察基本功 | 679. 24点游戏

✇LeetCode 每日一题题解
xiao_ben_zhu

思路

  • 游戏的第一步是挑出两个数，算出一个新数替代这两个数。

  • 然后，在三个数中玩 24 点，再挑出两个数，算出一个数替代它们。

  • 然后，在两个数中玩 24 点……

很明显的递归思路。每次递归都会挑出两个数，我们尝试挑出不同的两数组合：

  • 挑 1、2，基于它，继续递归。
  • 挑 1、3，基于它，继续递归。
  • 挑 ……

即通过两层 for 循环，枚举所有的两数组合，展开出不同选择所对应的递归分支。

挑出的每一对数，我们…

  • 枚举出所有可能的运算操作：加减乘除…——（对应不同的递归调用）
  • 逐个尝试每一种运算——（选择进入一个递归分支）
  • 传入长度变小的新数组继续递归——（递归计算子问题）
  • 当递归到只剩一个数——（到达了递归树的底部），看看是不是 24 。
    • 是就返回 true——结束当前递归，并且控制它不进入别的递归分支，整个结束掉。
    • 否则返回 false，离开错误的分支，进入别的递归分支，尝试别的运算。

剪枝小技巧

当递归返回 true，代表游戏成功，不用继续探索了，剩下的搜索分支全部砍掉。怎么做到？

  • 代码如下。标识变量isValid初始为 false，默认会执行||后面的递归。
  • 一旦某个递归返回真，isValid就变为真，由于||的短路特性，后面的递归不会执行。
  • 所有递归子调用都这么写，isValid就像一个开关，避免写很多判断语句。

###js

isValid = isValid || judgePoint24([...newNums, n1 + n2]);
isValid = isValid || judgePoint24([...newNums, n1 - n2]);
isValid = isValid || judgePoint24([...newNums, n2 - n1]);
isValid = isValid || judgePoint24([...newNums, n1 * n2]);
// ...

代码

const judgePoint24 = (nums) => {
    const len = nums.length;
    if (len == 1) {                // 递归的出口
        return Math.abs(nums[0] - 24) < 1e-9;
    }
    let isValid = false;           // 用于控制是否进入递归

    for (let i = 0; i < len; i++) { // 两层循环，枚举出所有的两数组合
        for (let j = i + 1; j < len; j++) {
            const n1 = nums[i];
            const n2 = nums[j];     // 选出的两个数 n1 n2
            const newNums = [];     // 存放剩下的两个数
            for (let k = 0; k < len; k++) {
                if (k != i && k != j) {  // 剔除掉选出的两个数
                    newNums.push(nums[k]);
                }
            }
            // 加
            isValid = isValid || judgePoint24([...newNums, n1 + n2]);
            // 减与被减
            isValid = isValid || judgePoint24([...newNums, n1 - n2]);
            isValid = isValid || judgePoint24([...newNums, n2 - n1]);
            // 乘
            isValid = isValid || judgePoint24([...newNums, n1 * n2]);
            if (n2 !== 0) { // 除
                isValid = isValid || judgePoint24([...newNums, n1 / n2]);
            }
            if (n1 !== 0) { // 被除
                isValid = isValid || judgePoint24([...newNums, n2 / n1]);
            }
            if (isValid) {
                return true;
            }
        }
    }
    return false; // 遍历结束，始终没有返回真，则返回false
};

func judgePoint24(nums []int) bool {
floatNums := make([]float64, len(nums))
for i := range floatNums {
floatNums[i] = float64(nums[i])
}
return dfs(floatNums)
}

func dfs(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24) < 1e-9
}
flag := false
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
n1, n2 := nums[i], nums[j]
newNums := make([]float64, 0, len(nums))
for k := 0; k < len(nums); k++ {
if k != i && k != j {
newNums = append(newNums, nums[k])
}
}
flag = flag || dfs(append(newNums, n1+n2))
flag = flag || dfs(append(newNums, n1-n2))
flag = flag || dfs(append(newNums, n2-n1))
flag = flag || dfs(append(newNums, n1*n2))
if n1 != 0 {
flag = flag || dfs(append(newNums, n2/n1))
}
if n2 != 0 {
flag = flag || dfs(append(newNums, n1/n2))
}
if flag {
return true
}
}
}
return false
}

执行情况

Runtime: 68 ms, faster than 100.00% of JavaScript online submissions for 24 Game.
Runtime: 0 ms, faster than 100.00% of Go online submissions for 24 Game.

感谢阅读，文字经过反复修改打磨，希望你能感受到这份真诚。欢迎提出建议。

最后修改于：2022-01-10

❌