青海专业网站建设推广平台建设_网站建设行业的前景分析_nba西部最新排名_seo快速入门教程

问题背景

一个 $n\times n$ 的二维网络 $board$ 仅由 $0$ 和 $1$ 组成 。每次移动，你能交换任意两列或是两行的位置。
返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 $-1$。
“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

数据约束

• $n=board.length$
• $n=board[i].length$
• $2\le n\le 30$
• $board[i][j]$ 将只包含 $0$ 或 $1$

解题过程

首先要确定所给矩阵能否转化成题目要求的形式。从结果上来看，符合条件的矩阵只由两种行构成，它们都是 $0$ 和 $1$ 交替出现，区别在于首位数字是 $0$ 还是 $1$。交替出现，意味着同一行中 $0$ 和 $1$ 的数量之差不能超过 $1$，否则无法实现转化。
同样的道理，按列来看，矩阵同样需要满足这样的特征。
但是不必要按行并且按列来遍历矩阵，可以将第一行作为标准，之后每一行都应该与标准完全相同或者完全相反，否则就要返回$-1$。
交换次数的计算，依赖的是纯粹的数学规律。参考 灵神的分析，若用$diff$来表示当前行与标准行之间不同的位数：

• 若$n$为奇数，那么交换的次数是 $\frac{diff}{2}$。
• 若$n$为偶数，那么交换的次数是 $\frac{min(diff,n-diff)}{2}$。

根据标准行的首位是 $0$ 还是 $1$，可以用是否需要异或运算来对 $diff$ 进行计数，而不必要实际地构造标准行来进行判断：

• 若标准行的首位为 $0$，遍历的过程中可以用 $(i\%2)\oplus 0$ 来累计。
• 若标准行的首位为 $1$，遍历的过程中可以用 $(i\%2)\oplus 1$ 来累计。

综合上述情况，考虑到 $0$ 异或任何数都等于该数本身，可以用一个标志位 $bit$ 来表示是否需要异或 $1$。

根据当前数字是 $0$ 还是 $1$，使用长度为 $2$ 的哈希表来方便地统计元素的数量，也是一种常用的重要技巧。另外还需要注意积累的是，利用异或的定义直接来统计 $diff$ 这样的操作。

具体实现

class Solution {public int movesToChessboard(int[][] board) {int n = board.length;int[] firstRow = board[0];int[] firstCol = new int[n];int[] rowCount =  new int[2];int[] colCount =  new int[2];// 统计第一行和第一列中 0 和 1 的数量for(int i = 0; i < n; i++) {rowCount[firstRow[i]]++;firstCol[i] = board[i][0];colCount[firstCol[i]]++;}// 如果第一行或者第一列的 0 与 1 数量之差超过 1，那么无法实现转换if(Math.abs(rowCount[0] - rowCount[1]) > 1 || Math.abs(colCount[0] - colCount[1]) > 1) {return -1;}// 判断剩余行是否和第一行完全相同或者完全相反for(int[] row : board) {// 将其中第一位数字作为标准，后面所有位上的情况应该与之相同boolean same = row[0] == firstRow[0];for(int i = 0; i < n; i++) {if((row[i] == firstRow[i]) != same) {return -1;}}}return min(firstRow, rowCount) + min(firstCol, colCount);}private int min(int[] arr, int[] count) {int n = arr.length;int bit = count[1] > count[0] ? 1 : 0;int diff = 0;for(int i = 0; i < n; i++) {// 利用异或的定义，直接统计 diffdiff += (i % 2) ^ arr[i] ^ bit;}return n % 2 == 0 ? Math.min(diff, n - diff) >>> 1 : diff >>> 1;}
}