Leetcode打卡：变为棋盘

执行结果：通过

题目：782 变为棋盘

一个 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.length
• n == board[i].length
• 2 <= n <= 30
• board[i][j] 将只包含 0或 1

代码以及解题思路

代码:

#define MIN(a, b) ((a) < (b) ? (a) : (b))

static int countBit(int x) {
    int ans = 0;
    while (x != 0) {
        x &= (x - 1);
        ans++;
    }
    return ans;
}

static int getMoves(int mask, int count, int n) {
    int ones = countBit(mask);
    if (n & 1) {
        /* 如果 n 为奇数，则每一行中 1 与 0 的数目相差为 1，且满足相邻行交替 */
        if (abs(n - 2 * ones) != 1 || abs(n - 2 * count) != 1 ) {
            return -1;
        }
        if (ones == (n >> 1)) {
            /* 偶数位变为 1 的最小交换次数 */
            return n / 2 - countBit(mask & 0xAAAAAAAA);
        } else {
            /* 奇数位变为 1 的最小交换次数 */
            return (n + 1) / 2 - countBit(mask & 0x55555555);
        }
    } else { 
        /* 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替 */
        if (ones != (n >> 1) || count != (n >> 1)) {
            return -1;
        }
        /* 偶数位变为 1 的最小交换次数 */
        int count0 = n / 2 - countBit(mask & 0xAAAAAAAA);
        /* 奇数位变为 1 的最小交换次数 */
        int count1 = n / 2 - countBit(mask & 0x55555555);  
        return MIN(count0, count1);
    }
}


int movesToChessboard(int** board, int boardSize, int* boardColSize) {
     int rowMask = 0, colMask = 0;        

    /* 检查棋盘的第一行与第一列 */
    for (int i = 0; i < boardSize; i++) {
        rowMask |= (board[0][i] << i);
        colMask |= (board[i][0] << i);
    }
    int reverseRowMask = ((1 << boardSize) - 1) ^ rowMask;
    int reverseColMask = ((1 << boardSize) - 1) ^ colMask;
    int rowCnt = 0, colCnt = 0;
    for (int i = 0; i < boardSize; i++) {
        int currRowMask = 0;
        int currColMask = 0;
        for (int j = 0; j < boardSize; j++) {
            currRowMask |= (board[i][j] << j);
            currColMask |= (board[j][i] << j);
        }
        /* 检测每一行的状态是否合法 */
        if (currRowMask != rowMask && currRowMask != reverseRowMask) {
            return -1;
        } else if (currRowMask == rowMask) {
            /* 记录与第一行相同的行数 */
            rowCnt++;
        }
        /* 检测每一列的状态是否合法 */
        if (currColMask != colMask && currColMask != reverseColMask) {
            return -1;
        } else if (currColMask == colMask) {
            /* 记录与第一列相同的列数 */
            colCnt++;
        }
    }
    int rowMoves = getMoves(rowMask, rowCnt, boardSize);
    int colMoves = getMoves(colMask, colCnt, boardSize);
    return (rowMoves == -1 || colMoves == -1) ? -1 : (rowMoves + colMoves); 

}

解题思路：

1. 定义辅助宏和函数：
   • MIN(a, b) 宏用于计算两个数中的最小值。
   • countBit(int x) 函数计算整数 x 的二进制表示中 1 的个数。
   • getMoves(int mask, int count, int n) 函数计算将一行或一列的当前状态（通过 mask 表示）转换为标准状态所需的最小翻转次数。这里 count 表示当前状态与第一行或第一列相同的行或列的数量，n 是棋盘的大小。
2. 检查棋盘的第一行和第一列：
   • 遍历棋盘的第一行和第一列，分别生成它们的位掩码 rowMask 和 colMask。
   • 计算这两个掩码的反掩码 reverseRowMask 和 reverseColMask。
3. 检查棋盘的每一行和每一列：
   • 遍历棋盘的每一行和每一列，生成当前行和列的位掩码 currRowMask 和 currColMask。
   • 检查当前行或列的状态是否与第一行或第一列的状态相同或相反，如果不是，则棋盘无法转换为标准棋盘，返回 -1。
   • 如果当前行或列与第一行或第一列相同，则分别计数 rowCnt 和 colCnt。
4. 计算行和列的最小翻转次数：
   • 使用 getMoves 函数计算将第一行和第一列的状态转换为标准状态所需的最小翻转次数 rowMoves 和 colMoves。
   • 如果 rowMoves 或 colMoves 中有一个为 -1，则表示无法仅通过翻转行或列来使棋盘标准化，返回 -1。
   • 否则，返回 rowMoves + colMoves 作为将棋盘转换为标准棋盘所需的最小翻转次数。

关键细节：

• getMoves 函数中，根据 n 的奇偶性和 mask 中 1 的数量，计算将当前行或列的状态转换为标准状态所需的最小翻转次数。
• 对于奇数大小的棋盘，每行或每列中 1 和 0 的数量相差 1，且相邻行或列的状态交替。
• 对于偶数大小的棋盘，每行或每列中 1 和 0 的数量相等，且相邻行或列的状态交替。
• countBit 函数通过不断将 x 与 x-1 做按位与操作来计算 x 中 1 的个数，这是一种高效的位操作技巧。