一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动,你能任意交换两列或是两行的位置。
返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换,输出 -1。
“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下,从左到右:
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。
解:
棋盘的合法性:
首先要考虑到棋盘的合法性,如果第一行为10101,那么第二行就为01010,第三行就和第一行相同。所以要么和第一行相同,要么和第一行完全相反。期盼才是合法的。
然后从整体看,分为偶数和奇数类型,我们可以看到四个角要么是0101,要么是全为1或全为0.那么如果不符合这个,棋盘业不合法。
public int movesToChessboard(int[][] board) {if (!check(board)) {return -1;}int[] col = new int[board.length];for (int i = 0; i < board.length; i++) {col[i] = board[i][0];}return getSwapCount(board[0]) + getSwapCount(col);}/*** 检查合法性 分别检查行和列** @param board 数组* @return*/public boolean check(int[][] board) {return checkFirstRow(board) &&checkFirstCol(board) &&checkRow(board) &&checkCol(board);}public boolean checkFirstRow(int[][] board) {int rowOneCnt = 0;int rowZeroCnt = 0;int[] first = board[0];for (int num : first) {if (num == 0) {rowZeroCnt++;} else {rowOneCnt++;}}return rowOneCnt == rowZeroCnt || Math.abs(rowOneCnt - rowZeroCnt) == 1;}public boolean checkFirstCol(int[][] board) {int oneCnt = 0, zeroCnt = 0;for (int i = 0; i < board.length; i++) {if (board[i][0] == 0) {zeroCnt++;} else {oneCnt++;}}return oneCnt == zeroCnt || Math.abs(oneCnt - zeroCnt) == 1;}public boolean checkRow(int[][] board) {//第一行当做哨兵 其他的行要么和第一行相等 要么和第一行相反//如:第一行0110 后续的行只能是 0110、1001int[] sentinel = board[0];int sameCnt = 0, oppositeCnt = 0;for (int[] cur : board) {//相同if (sentinel[0] == cur[0]) {for (int i = 0; i < sentinel.length; i++) {if (sentinel[i] != cur[i]) {return false;}}sameCnt++;} else {//相反for (int i = 0; i < sentinel.length; i++) {if (sentinel[i] + cur[i] != 1) {return false;}}oppositeCnt++;}}return sameCnt == oppositeCnt || Math.abs(sameCnt - oppositeCnt) == 1;}public boolean checkCol(int[][] board) {//第一列当做哨兵 其他的列要么和第一列相等 要么和第一列相反//如:第一列0110 后续的列只能是 0110、1001int sameCnt = 0, oppositeCnt = 0;int[] sentinel = new int[board.length];for (int j = 0; j < board.length; j++) {sentinel[j] = board[j][0];}for (int j = 0; j < board.length; j++) {if (board[0][j] == sentinel[0]) {for (int i = 0; i < sentinel.length; i++) {if (sentinel[i] != board[i][j]) {return false;}}sameCnt++;} else {for (int i = 0; i < sentinel.length; i++) {if (sentinel[i] + board[i][j] != 1) {return false;}}oppositeCnt++;}}return sameCnt == oppositeCnt || Math.abs(sameCnt - oppositeCnt) == 1;}private int getSwapCount(int[] sentinel) {//假设都是10101010...int preNum = 1;int errorCnt = 0;for (int i : sentinel) {//统计有多少错位if (i != preNum) {errorCnt++;}preNum = preNum == 1 ? 0 : 1;}//数组是偶数个还是奇数个if (sentinel.length % 2 == 0) {//偶数个 可以是01010101 或者 10101010return Math.min(sentinel.length - errorCnt, errorCnt) / 2;} else {//奇数个 取决于1多还是0多 1多则是1 0 1 0 1 0 1 0 1 、0多则是0 1 0 1 0 1 0 1 0//并且错误的个数一定是偶数个if (errorCnt % 2 == 0) {return errorCnt / 2;} else {return (sentinel.length - errorCnt) >> 1;}}}
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/transform-to-chessboard
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。