medium – 第 17 页 – shelterofly

36.有效的数独

目标

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

思路

依题意模拟即可。

代码


/**
 * @date 2025-01-19 20:00
 */
public class IsValidSudoku36 {

    public boolean isValidSudoku(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            boolean[] exists = new boolean[10];
            for (int j = 0; j < n; j++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                if (exists[c - '0']) {
                    return false;
                }
                exists[c - '0'] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            boolean[] exists = new boolean[10];
            for (int i = 0; i < m; i++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                if (exists[c - '0']) {
                    return false;
                }
                exists[c - '0'] = true;
            }
        }
        boolean[] exists = null;
        for (int j = 0; j < n; j += 3) {
            for (int i = 0; i < m; i++) {
                if (i % 3 == 0) {
                    exists = new boolean[10];
                }
                for (int k = j; k < j + 3; k++) {
                    char c = board[i][k];
                    if ('.' == c) {
                        continue;
                    }
                    if (exists[c - '0']) {
                        return false;
                    }
                    exists[c - '0'] = true;
                }
            }
        }
        return true;
    }

}

性能

3021.Alice和Bob玩鲜花游戏

目标

Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花，Alice 到 Bob 之间顺时针有 x 朵鲜花，逆时针有 y 朵鲜花。

游戏过程如下：

Alice 先行动。
每一次行动中，当前玩家必须选择顺时针或者逆时针，然后在这个方向上摘一朵鲜花。
一次行动结束后，如果所有鲜花都被摘完了，那么当前玩家抓住对手并赢得游戏的胜利。

给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：

按照上述规则，Alice 必须赢得游戏。
Alice 顺时针方向上的鲜花数目 x 必须在区间 [1,n] 之间。
Alice 逆时针方向上的鲜花数目 y 必须在区间 [1,m] 之间。

请你返回满足题目描述的数对 (x, y) 的数目。

示例 1：

输入：n = 3, m = 2
输出：3
解释：以下数对满足题目要求：(1,2) ，(3,2) ，(2,1) 。

示例 2：

输入：n = 1, m = 1
输出：0
解释：没有数对满足题目要求。

说明：

1 <= n, m <= 10^5

思路

代码

性能

3446.按对角线进行矩阵排序

目标

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

左下角三角形（包括中间对角线）的对角线按非递增顺序排序。
右上角三角形的对角线按非递减顺序排序。

示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]
输出： [[8,2,3],[9,6,7],[4,5,1]]
解释：
标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：
[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：
[7, 2] 变为 [2, 7]。
[3] 保持不变。

示例 2：

输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解释：
标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]
输出： [[1]]
解释：
只有一个元素的对角线已经符合要求，因此无需修改。

说明：

grid.length == grid[i].length == n
1 <= n <= 10
-10^5 <= grid[i][j] <= 10^5

思路

参考 498.对角线遍历

代码


/**
 * @date 2025-08-28 8:57
 */
public class SortMatrix3446 {

    public int[][] sortMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int k = m + n - 1;
        for (int l = 1; l < n; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(null);
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        for (int l = n; l <= k; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(Collections.reverseOrder());
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        return grid;
    }
}

性能

498.对角线遍历

目标

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

说明：

m == mat.length
n == mat[i].length
1 <= m, n <= 10^4
1 <= m * n <= 10^4
-10^5 <= mat[i][j] <= 10^5

思路

按照左上、右下、左上、右下…… 的顺序枚举矩阵的对角线。

m = 4, n = 3

 1  2   3 (k)
↗ ↙ ↗
↙ ↗ ↙ 4
↗ ↙ ↗ 5
↙ ↗ ↙ 6

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)
(3, 0) (3, 1) (3, 2)

定义 k - 1 = i + j，可得 j = k - 1 - i

当 i = 0 时，j 取得最大值 k - 1，由于 j <= n - 1，因此 maxJ = Math.min(k - 1, n - 1)
当 i = m - 1 时，j 取得最小值 k - m，由于 j >= 0，因此 minJ = Math.max(k - m, 0)

代码


/**
 * @date 2025-08-25 8:51
 */
public class FindDiagonalOrder498 {

    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int l = m + n - 1;
        int[] res = new int[m * n];
        int p = 0;
        for (int k = 1; k <= l; k++) {
            int minJ = Math.max(0, k - m);
            int maxJ = Math.min(k - 1, n - 1);
            if (k % 2 == 0) {
                for (int j = maxJ; j >= minJ; j--) {
                    res[p++] = mat[k - 1 - j][j];
                }
            } else {
                for (int j = minJ; j <= maxJ; j++) {
                    res[p++] = mat[k - 1 - j][j];
                }
            }
        }
        return res;
    }

}

性能

1493.删掉一个元素以后全为1的最长子数组

目标

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

示例 1：

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3：

输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。

说明：

1 <= nums.length <= 10^5
nums[i] 要么是 0 要么是 1 。

思路

有一个二进制数组 nums，从中删除一个元素，求剩余元素中连续的 1 的最大长度。

计算从当前下标为起点的连续 1 的结束下标，end - start 表示连续 1 的长度，允许删掉一个元素可以直接加上以 end + 1 为起点的连续 1 的个数。

更优的解法是使用滑动窗口计算最长子数组长度，要求窗口内部至多一个 0。

代码


/**
 * @date 2025-08-24 12:20
 */
public class LongestSubarray1493 {

    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int res = 0;
        int i = 0;
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == 1) {
                i++;
            }
            for (int j = start; j < i; j++) {
                nums[j] = i;
            }
            if (i == start) {
                nums[i] = i;
                i++;
            }
        }
        for (int j = 0; j < n; j++) {
            res = Math.max(res, nums[j] - j + (nums[j] < n - 1 ? nums[nums[j] + 1] - nums[j] - 1 : 0));
        }
        return res == n ? n - 1 : res;
    }

}

性能

3195.包含所有1的最小矩形面积I

目标

给你一个二维二进制数组 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 。

思路

已知一个二维二进制数组，找出包含矩阵中所有 1 的矩阵的最小面积。

找到 1 的横纵坐标的上下界即可。

代码


/**
 * @date 2025-08-22 10:08
 */
public class MinimumArea3195 {

    public int minimumArea(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int rowMin = m - 1, rowMax = 0;
        int colMin = n - 1, colMax = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowMin = Math.min(rowMin, i);
                    rowMax = Math.max(rowMax, i);
                    colMin = Math.min(colMin, j);
                    colMax = Math.max(colMax, j);
                }
            }
        }
        return (rowMax - rowMin + 1) * (colMax - colMin + 1);
    }

}

性能

1504.统计全1子矩形

目标

给你一个 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

思路

返回 m x n 矩阵的全 1 子矩阵个数。

枚举行的上下界，计算高度 h，将纵向的 1 压缩到一行，计算全 h 子数组的数目（参考 2348.全0子数组的数目）。

代码


/**
 * @date 2025-08-21 8:48
 */
public class NumSubmat1504 {

    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int res = 0;
        for (int u = 0; u < m; u++) {
            for (int l = u; l < m; l++) {
                int h = l - u + 1;
                int[] row = new int[n];
                for (int i = u; i <= l; i++) {
                    for (int j = 0; j < n; j++) {
                        row[j] += mat[i][j];
                    }
                }
                int p = 0;
                while (p < n) {
                    if (row[p] != h) {
                        p++;
                        continue;
                    }
                    int start = p;
                    while (p < n && row[p] == h) {
                        p++;
                    }
                    int cnt = p - start;
                    res += (cnt + 1) * cnt / 2;
                }
            }
        }
        return res;
    }

}

性能

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

目标

给你一个 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

思路

统计 m x n 矩阵中全是 1 的正方形子矩阵个数。

遍历的逻辑是枚举长度，以左上顶点为圆心，长度为半径进行遍历。

代码


/**
 * @date 2025-08-20 8:44
 */
public class CountSquares1277 {

    public int countSquares(int[][] matrix) {
        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++) {
                if (matrix[i][j] != 1) {
                    continue;
                }
                int max = Math.min(m - i, n - j);
                int l = 1;
                here:
                for (; l < max; l++) {
                    for (int y = i + l; y >= i; y--) {
                        if (matrix[y][j + l] == 0) {
                            break here;
                        }
                    }
                    for (int x = j + l; x >= j; x--) {
                        if (matrix[i + l][x] == 0) {
                            break here;
                        }
                    }
                }
                res += l;
            }
        }
        return res;
    }

}

性能

2348.全0子数组的数目

目标

给你一个整数数组 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 <= 10^5
-10^9 <= nums[i] <= 10^9

思路

返回数组的全 0 子数组个数。

长度为 k 的子数组个数为 (1 + k) * k / 2。可以使用贪心策略，如果当前元素是 0 找到以它为起点的最长连续 0 数组，计算子数组个数。

代码


/**
 * @date 2025-08-19 8:54
 */
public class ZeroFilledSubarray2348 {

    public long zeroFilledSubarray(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int i = 0;
        while (i < n){
            if (nums[i] != 0){
                i++;
                continue;
            }
            int start = i;
            while (i < n && nums[i] == 0){
                i++;
            }
            int cnt = i - start;
            res += (1L + cnt) * cnt / 2;
        }

        return res;
    }
}

性能

837.新21点

目标

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得 k 分或更多分时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过 10^-5 的答案将被视为正确答案。

示例 1：

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。

示例 2：

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。

示例 3：

输入：n = 21, k = 17, maxPts = 10
输出：0.73278

2026 年 8 月
一	二	三	四	五	六	日
					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