目标

请你判断一个 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;
    }
}

性能

目标

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

}

性能

目标

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。

矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：

• 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。
• 令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。

然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。

返回矩阵 answer 。

矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。

如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。

示例 1：

输入：grid = [[1,2,3],[3,1,5],[3,2,1]]
输出：[[1,1,0],[1,0,1],[0,1,1]]
解释：第 1 个图表示最初的矩阵 grid 。 
第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。
第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。
第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。
- 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。
- 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。
- 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。
其他单元格的对应答案也可以按照这样的流程进行计算。

示例 2：

输入：grid = [[1]]
输出：[[0]]
解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n, grid[i][j] <= 50

思路

计算矩阵元素左上对角线的不同元素个数与右下对角线的不同元素个数的差的绝对值。即将元素所在的左上右下对角线，以当前元素为分界点（不包括当前元素），分成左上与右下两部分，计算每部分不同元素的个数，取差的绝对值。

暴力解法是枚举每个格子的左上右下元素，每一对角线都要遍历它所包含的元素个数次。

可以直接按对角线遍历，先记录前缀中的不同元素个数，然后再倒着遍历，计算差值的绝对值。

网友提到由于元素值不大，可以将其保存到 long 型数字中。

代码

/**
 * @date 2025-03-25 0:12
 */
public class DifferenceOfDistinctValues2711 {

    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m + n - 1; i++) {
            int row = i / n < 1 ? 0 : i - n + 1 % m;
            int col = row > 0 ? 0 : n - 1 - i;
            Set<Integer> set = new HashSet<>();
            while (row < m && col < n){
                res[row][col] = set.size();
                set.add(grid[row][col]);
                row++;
                col++;
            }
            row--;
            col--;
            set.clear();
            while (row >= 0 && col >= 0){
                res[row][col] = Math.abs(res[row][col] - set.size());
                set.add(grid[row][col]);
                row--;
                col--;
            }
        }
        return res;
    }

}

性能

目标

给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

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

示例 2：

输入：n = 1
输出：[[1]]

说明：

1 <= n <= 20

思路

生成一个 n x n 的正方形矩阵，元素值 1 ~ n^2 按顺时针螺旋顺序排列。

定义 4 个方向，用 direction[i] 表示沿着 i 方向前进的坐标变化量。首先从 (0, 0) 开始向右遍历，预先计算下一步的坐标，如果越界或者已经设置过值则转向。这种解法需要标记已经设置过值的数组，由于填充的元素值都大于 0，数组初值无需特殊处理，只需判断元素是否大于 0 即可。

代码

/**
 * @date 2025-02-07 0:11
 */
public class GenerateMatrix59 {

    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0, num = 1, d = 0;
        for (int i = 0; i < n * n; i++) {
            matrix[x][y] = num++;
            int xNext = x + direction[d][0];
            int yNext = y + direction[d][1];
            if (xNext == n || yNext < 0 || yNext == n || matrix[xNext][yNext] != 0) {
                d = (d + 1) % 4;
            }
            x += direction[d][0];
            y += direction[d][1];
        }
        return matrix;
    }

}

性能

目标

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。

象棋骑士可能的移动方式如下图所示:

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。

给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 10^9 + 7.

示例 1：

输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3：

输入：n = 3131
输出：136006598
解释：注意取模

说明：

• 1 <= n <= 5000

思路

有一个电话键盘，布局如下：

1  2  3
4  5  6
7  8  9
*  0  #

开始时，将一个骑士棋子放在数字键上，然后按照国际象棋骑士的走法（类似于中国象棋里的马）走 n - 1 步，问能够组成多少种长度为 n 的不同号码（不能走到 * 和 #）。

这道题与 688.骑士在棋盘上的概率 类似，只不过棋盘更小，状态转移是确定的。

定义 dp[k][i] 表示以 i 结尾长度为 k 的号码组合数。初始时，dp[1][i] 均为 1。状态转移方程，针对不同的数字有所不同，例如 dp[k][1] = dp[k - 1][8] + dp[k - 1][6]，dp[k][4] = dp[k - 1][3] + dp[k - 1][9] + dp[k - 1][0]等等。

1 - 6 - 7
|   |   |
8   0   2
|   |   |
3 - 4 - 9

仔细分析可以得到上面的状态转化图，1 3 7 9 的结果是完全相同的，同理 2 8 也可以认为是一个状态，4 6 是一个状态，0 是一个状态。定义以上 4 个状态为 a b c d，那么最终结果可以表示为 4 * dp[n][a] + 2 * dp[n][b] + 2 * dp[n][c] + dp[n][d]，状态转移方程为：

• dp[k][a] = dp[k - 1][b] + dp[k - 1][c]
• dp[k][b] = 2 * dp[k - 1][a]
• dp[k][c] = 2 * dp[k - 1][a] + dp[k - 1][d]
• dp[k][d] = 2 * dp[k - 1][c]

注意 k 的初值为 2，k == 1 是特殊情况，骑士可以在数字 5，但是无法继续移动。dp[2][a] = 2, dp[2][b] = 2, dp[2][c] = 3, dp[2][d] = 2

如果写成矩阵的形式 列向量 dp[k] 等于 A · dp[k - 1]，其中矩阵 A 为：

0 1 1 0
2 0 0 0
2 0 0 1
0 0 2 0

因此 dp[n] = A^(n - 1) · dp[1]，其中 dp[1] = [1, 1, 1, 1]。我们可以使用矩阵的快速幂求解。

代码

/**
 * @date 2024-12-10 9:39
 */
public class KnightDialer935 {

    public static int mod = 1000000007;

    public int knightDialer_v3(int n) {
        if (n == 1) {
            return 10;
        }
        long[][] A = new long[][]{
                {0, 1, 1, 0},
                {2, 0, 0, 0},
                {2, 0, 0, 1},
                {0, 0, 2, 0},
        };
        A = pow(A, n - 1);
        long[] res = new long[4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                res[i] += A[i][j];
            }
        }
        return (int) ((4 * res[0] + 2 * res[1] + 2 * res[2] + res[3]) % mod);
    }

    public long[][] pow(long[][] A, int exponent) {
        long[][] res = new long[][]{
                {1, 0, 0, 0},
                {0, 1, 0, 0},
                {0, 0, 1, 0},
                {0, 0, 0, 1},
        };
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                res = mul(A, res);
            }
            A = mul(A, A);
            exponent >>= 1;
        }
        return res;
    }

    public long[][] mul(long[][] A1, long[][] A2) {
        long[][] res = new long[4][4];
        for (int i = 0; i < 4; i++) {
            for (int k = 0; k < 4; k++) {
                if (A1[i][k] == 0) {
                    continue;
                }
                for (int j = 0; j < 4; j++) {
                    res[i][j] = (res[i][j] + A1[i][k] * A2[k][j]) % mod;
                }
            }
        }
        return res;
    }

    public static long[][] dp;
    public static int MAX = 5001;

    static {
        dp = new long[MAX][4];
        dp[2][0] = 2;
        dp[2][1] = 2;
        dp[2][2] = 3;
        dp[2][3] = 2;
        for (int k = 3; k < MAX; k++) {
            dp[k][0] = (dp[k - 1][1] + dp[k - 1][2]) % mod;
            dp[k][1] = (2 * dp[k - 1][0]) % mod;
            dp[k][2] = (2 * dp[k - 1][0] + dp[k - 1][3]) % mod;
            dp[k][3] = (2 * dp[k - 1][2]) % mod;
        }
    }

    public int knightDialer_v2(int n) {
        if (n == 1) {
            return 10;
        }
        return (int)((4 * dp[n][0] + 2 * dp[n][1] + 2 * dp[n][2] + dp[n][3]) % mod);
    }

    public int knightDialer_v1(int n) {
        long[][] dp = new long[n + 1][10];
        dp[1] = new long[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        int MOD = 1000000007;
        int res = 0;
        for (int k = 2; k <= n; k++) {
            dp[k][0] = (dp[k - 1][4] + dp[k - 1][6]) % MOD;
            dp[k][1] = (dp[k - 1][6] + dp[k - 1][8]) % MOD;
            dp[k][2] = (dp[k - 1][7] + dp[k - 1][9]) % MOD;
            dp[k][3] = (dp[k - 1][4] + dp[k - 1][8]) % MOD;
            dp[k][4] = (dp[k - 1][3] + dp[k - 1][9] + dp[k - 1][0]) % MOD;
            dp[k][6] = (dp[k - 1][1] + dp[k - 1][7] + dp[k - 1][0]) % MOD;
            dp[k][7] = (dp[k - 1][2] + dp[k - 1][6]) % MOD;
            dp[k][8] = (dp[k - 1][1] + dp[k - 1][3]) % MOD;
            dp[k][9] = (dp[k - 1][2] + dp[k - 1][4]) % MOD;
        }
        for (int i = 0; i < 10; i++) {
            res = (int) (res + dp[n][i]) % MOD;
        }
        return res;
    }

}

性能