月度归档： 2025 年 8 月

目标

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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;
    }

}

性能

目标

给你一个大小为 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;
    }
}

性能

目标

给你一个大小为 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;
    }

}

性能

目标

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

}

性能

目标

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

}

性能