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

问题背景

一个 $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++) {
            // 利用异或的定义，直接统计 diff
            diff += (i % 2) ^ arr[i] ^ bit;
        }
        return n % 2 == 0 ? Math.min(diff, n - diff) >>> 1 : diff >>> 1;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/144322281

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！