【从零开始的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

我的解答

class Solution {
    public int movesToChessboard(int[][] board) {
        /**
         *  棋盘需满足一下条件：
         *      1.n为偶数时，每行的‘0’，‘1’数量一致，每列的‘0’，‘1’数量也一致
         *      2.n为奇数时，每行的‘0’，‘1’数量差值为1，每列的‘0’，‘1’数量差值也为1
         *  满足上述两个条件后，才能变为棋盘
         */
        int n = board.length;
        int[] colume = new int[n];
        int row_count = 0;
        for(int i = 0; i < n; i++){
            // 记入第一列的格子，用于后面计算行交换的最小次数
            colume[i] = board[i][0];
            // 获取每行从0和从1开始变成01交替所需的交换次数
            int row_res = row_sub(board[i]);
            if(row_res == -1) return -1;

            if(i == 0) row_count = row_res;
            if(row_count != row_res) return -1;
        }
        /**
         * 每行都能使用相同的交换次数变为满足棋盘的形式，那么只需看其中一列是否能交换成满足棋盘的形式即可
         * 因为当行中的某个位置需要进行交换时，其整一列都是同步移动的
         * 所以任取一列进行交换，查看其满足棋盘条件的最小交换次数
         */ 
        int column_count = row_sub(colume);
        if(column_count == -1) return -1;


        return (row_count + column_count) / 2;
    }

    private int row_sub(int[] b){
        int size = b.length;
        int o_count = 0,l_count = 0;
        int o = 0;
        for(int i = 0; i < size; i++){
            // 遍历偶数位时，偶数位与起点相同
            if(i % 2 == 0){
                // 以0为起点，偶数位若不为0则需要交换
                o_count +=  b[i] == 0 ? 0 : 1;
                // 以1为起点，偶数位若为0则需要交换
                l_count +=  b[i] == 0 ? 1 : 0;
            }
            // 遍历奇数位时，奇数位与起点相反
            else if(i % 2 != 0){
                // 以0为起点，奇数位若为0则需要交换
                o_count +=  b[i] == 0 ? 1 : 0;
                // 以1为起点，奇数位若不为0则需要交换
                l_count +=  b[i] == 0 ? 0 : 1;
            }
            // 同时统计0的数量
            o += b[i] == 0 ? 1 : 0;
        }
        
        // 算出1的数量
        int l = size - o;
        // 当棋盘格子n为偶数时
        if(size % 2 == 0){
            // 若01格子数相同，那就返回二者中所需交换次数最小的
            if(l == o) return o_count < l_count ? o_count : l_count;
        }
        // 当棋盘格子n为奇数时
        else{
            // 1的数量比0多1时
            if(l - o == 1) return l_count;
            // 0的数量比1多1时
            if(o - l == 1) return o_count;
        }
        // 其他情况
        return -1;
    }
}

原文地址：https://blog.csdn.net/qq_40878316/article/details/144325254

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