豆包 LeetCode 782.变为棋盘 public int movesToChessboard(int[][] board)
这题是 LeetCode 782. Transform to Chessboard,属于找规律 + 数学模拟题,直接给你可提交 Java 代码 + 极简思路。任意四个角落(0,0),(i,0),(0,j),(i,j)异或必须为 0,否则直接返回-1。如果你需要,我可以一步步带你模拟样例,保证你彻底懂这题。2. 1 的个数必须接近一半。1. 合法棋盘必须满足。核心规律(必背三点)
·
这题是 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²),遍历一遍矩阵即可。
如果你需要,我可以一步步带你模拟样例,保证你彻底懂这题。
更多推荐




所有评论(0)