变为棋盘
难度:
标签:
题目描述
一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能任意交换两列或是两行的位置。
返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。
“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
示例 1:
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]] 输出: 2 解释:一种可行的变换方式如下，从左到右： 第一次移动交换了第一列和第二列。 第二次移动交换了第二行和第三行。
示例 2:
输入: board = [[0, 1], [1, 0]] 输出: 0 解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.
示例 3:
输入: board = [[1, 0], [1, 0]] 输出: -1 解释: 任意的变换都不能使这个输入变为合法的棋盘。
提示：
n == board.lengthn == board[i].length2 <= n <= 30board[i][j]将只包含0或1
代码结果
运行时间: 25 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 利用Java Stream计算行和列的状态，并统计出各状态的数量。
* 2. 计算将行和列转换为棋盘模式的最小移动次数。
* 3. 使用流操作来计算需要的移动次数，并检查是否可以达成棋盘状态。
*/
import java.util.stream.*;
public int movesToChessboard(int[][] board) {
int n = board.length;
int[] rowCount = new int[2];
int[] colCount = new int[2];
int rowPattern = 0, colPattern = 0;
for (int i = 0; i < n; i++) {
rowPattern = rowPattern * 2 + board[0][i];
colPattern = colPattern * 2 + board[i][0];
}
rowCount[rowPattern % 2]++;
colCount[colPattern % 2]++;
long rowMoves = IntStream.range(0, n).filter(i -> board[0][i] != i % 2).count();
long colMoves = IntStream.range(0, n).filter(i -> board[i][0] != i % 2).count();
if (Math.abs(rowCount[0] - rowCount[1]) > 1 || Math.abs(colCount[0] - colCount[1]) > 1) return -1;
if (n % 2 == 1) {
if (rowCount[0] > rowCount[1]) rowMoves = n - rowMoves;
if (colCount[0] > colCount[1]) colMoves = n - colMoves;
} else {
rowMoves = Math.min(rowMoves, n - rowMoves);
colMoves = Math.min(colMoves, n - colMoves);
}
return (int) ((rowMoves + colMoves) / 2);
}
解释
方法:
这个题解的思路是先检查棋盘的第一行和第一列是否满足特定的模式。如果满足，则统计第一行和第一列中 1 的数量，以及需要交换的行数和列数。如果 1 的数量不在合法范围内，则返回 -1。否则，根据棋盘大小的奇偶性，计算最小的行交换次数和列交换次数。最后返回行列交换次数之和的一半作为最小移动次数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在检查棋盘第一行和第一列的模式时，使用了异或运算 `board[0][0]^board[0][i]^board[i][0]^board[i][i]`？这个表达式具体是如何确保棋盘能够被转换成棋盘模式的？
▷🦆
题解中提到如果第一行或第一列中1的数量不在合法范围内，就返回-1。具体来说，这个合法范围是如何根据棋盘的大小确定的？
▷🦆
在计算需要交换的行数和列数时，为什么要检查`board[i][0] == i % 2`和`board[0][i] == i % 2`？这样的检查与棋盘的目标模式有什么关系？
▷