【Leetcode 每日一题】782. 变为棋盘

问题背景

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

数据约束

• n = b o a r d . l e n g t h n = board.length n=board.length
• n = b o a r d [ i ] . l e n g t h n = board[i].length n=board[i].length
• 2 ≤ n ≤ 30 2 \le n \le 30 2≤n≤30
• b o a r d [ i ] [ j ] board[i][j] board[i][j] 将只包含 0 0 0 或 1 1 1

解题过程

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

• 若 n n n为奇数，那么交换的次数是 d i f f 2 \frac {diff} {2} 2diff​。
• 若 n n n为偶数，那么交换的次数是 m i n ( d i f f , n − d i f f ) 2 \frac {min(diff, n - diff)} {2} 2min(diff,n−diff)​。

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

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

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

根据当前数字是 0 0 0 还是 1 1 1，使用长度为 2 2 2 的哈希表来方便地统计元素的数量，也是一种常用的重要技巧。另外还需要注意积累的是，利用异或的定义直接来统计 d i f f diff 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++) {
            // 利用异或的定义，直接统计 diff
            diff += (i % 2) ^ arr[i] ^ bit;
        }
        return n % 2 == 0 ? Math.min(diff, n - diff) >>> 1 : diff >>> 1;
    }
}