这题是 LeetCode 782. Transform to Chessboard,属于找规律 + 数学模拟题,直接给你可提交 Java 代码 + 极简思路。

Java 代码

java

class Solution {
public int movesToChessboard(int[][] board) {
int n = board.length;
int rowSum = 0, colSum = 0;
int rowSwap = 0, colSwap = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ((board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) == 1) {
                return -1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        rowSum += board[0][i];
        colSum += board[i][0];
        if (board[i][0] == i % 2) rowSwap++;
        if (board[0][i] == i % 2) colSwap++;
    }

    if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1;
    if (colSum != n / 2 && colSum != (n + 1) / 2) return -1;

    if (n % 2 == 1) {
        if (rowSwap % 2 == 1) rowSwap = n - rowSwap;
        if (colSwap % 2 == 1) colSwap = n - colSwap;
    } else {
        rowSwap = Math.min(rowSwap, n - rowSwap);
        colSwap = Math.min(colSwap, n - colSwap);
    }

    return (rowSwap + colSwap) / 2;
}

}

核心规律(必背三点)

1. 合法棋盘必须满足
任意四个角落  (0,0),(i,0),(0,j),(i,j)  异或必须为 0,否则直接返回  -1 。
2. 1 的个数必须接近一半
第一行/第一列中 1 的数量只能是:

  • n/2  或  (n+1)/2 ,否则不合法。
    3. 计算最小交换次数
  • 看有多少行、列不在正确位置。
  • 奇数长度:只能取偶数交换那一种。
  • 偶数长度:取两种方案最小。
  • 答案 =  (行交换 + 列交换) / 2 。

时间复杂度

  • O(n²),遍历一遍矩阵即可。

如果你需要,我可以一步步带你模拟样例,保证你彻底懂这题。

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐