【2022-08-23每日一题】782. 变为棋盘

2022-08-23每日一题：782. 变为棋盘

• 难度：Hard
• 标签：位运算 、 数组 、 数学 、 矩阵

一个 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

func getMoves(mask uint, count, n int) int {
    ones := bits.OnesCount(mask)
    if n&1 > 0 {
        // 如果 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 - bits.OnesCount(mask&0xAAAAAAAA)
        } else {
            // 奇数位变为 1 的最小交换次数
            return (n+1)/2 - bits.OnesCount(mask&0x55555555)
        }
    } else {
        // 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替
        if ones != n>>1 || count != n>>1 {
            return -1
        }
        // 偶数位变为 1 的最小交换次数
        count0 := n/2 - bits.OnesCount(mask&0xAAAAAAAA)
        // 奇数位变为 1 的最小交换次数
        count1 := n/2 - bits.OnesCount(mask&0x55555555)
        return min(count0, count1)
    }
}

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

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

LeetCode题库地址

• https://leetcode.cn/problems/transform-to-chessboard

精选题解

• https://leetcode.cn/problems/transform-to-chessboard/solution/bian-wei-qi-pan-by-leetcode-solution-39dd/
• https://leetcode.cn/problems/transform-to-chessboard/solution/zhua-wa-mou-si-by-muse-77-pit5/
• https://leetcode.cn/problems/transform-to-chessboard/solution/by-ac_oier-vf1m/
• https://leetcode.cn/problems/transform-to-chessboard/solution/bian-wei-qipan-by-capital-worker-rlzb/