題目

https://leetcode.com/problems/transform-to-chessboard/

題解

沒思路，看了答案。這道題沒有套路，需要發(fā)現獨特的規(guī)律，參考：

簡單易懂的解法

【Python3】要么等于第一行 要么和第一行完全相反

代碼是看著答案的思路，一句一句翻譯過來的…詳細原理見注釋。

class Solution {public int movesToChessboard(int[][] board) {// 規(guī)則#1// 所有的"行"，要么等于第0行，要么和第0行完全相反// 列也一樣，但不需要去檢查列，因為如果"行"合法，列必然合法，因此只需要判斷"行"就行int N = board.length;boolean[] reverse = new boolean[N];for (int i = 1; i < N; i++) {reverse[i] = board[i][0] != board[0][0];}for (int i = 1; i < N; i++) {for (int j = 0; j < N; j++) {if (reverse[i] && board[i][j] == board[0][j]) return -1;}}// 規(guī)則#2// 每行的"1"的個數必須要么等于"0"的個數，要么相差1。因為規(guī)則#1已經通過，這次只要檢查第0"行"就行。// 這次除了第0行，還需要檢查第0列。int one = 0;for (int i = 0; i < N; i++) {if (board[0][i] == 1) one++;}if (Math.abs(N - 2 * one) > 1) return -1;one = 0;for (int i = 0; i < N; i++) {if (board[i][0] == 1) one++;}if (Math.abs(N - 2 * one) > 1) return -1;// 【計算交換次數】// 只需要計算第0行和第0列的交換次數就行，因為滿足規(guī)則#1，所以剩下的行列肯定自動合法// 【首先，變換行】// (1)假設左上角單元格是0，則可推知整行的每個單元格。計算實際與目標的diff個數，如果diff為偶數，則變化次數為差異點個數的一半// （因為交換一次可以消除兩個差異點）。如果diff為奇數，則無法變換為目標風格// (2)假設左上角單元格是1。同上。// (3)最后，選交換次數最小的作為行交換次數。// 【然后，變換列】// 列的變換算法和行沒有任何差異，且行交換結果不影響列交換結果。// 【最后，行列交換次數相加】// 就是最終結果。int diffRow = 0;int swapRow;for (int i = 0; i < N; i++) { // 假設左上角為0，計算"行"交換個數if (i % 2 == 0) diffRow += board[0][i];else diffRow += (1 - board[0][i]);}if (diffRow % 2 == 0) {swapRow = diffRow / 2;if ((N - diffRow) % 2 == 0) swapRow = Math.min(swapRow, (N - diffRow) / 2); // N-diff是假設左上角為1的情況} else {swapRow = (N - diffRow) / 2;}// 行交換結果不影響列交換結果int diffCol = 0;int swapCol;for (int i = 0; i < N; i++) { // 假設左上角為0，計算"列"交換個數if (i % 2 == 0) diffCol += board[i][0];else diffCol += (1 - board[i][0]);}if (diffCol % 2 == 0) {swapCol = diffCol / 2;if ((N - diffCol) % 2 == 0) swapCol = Math.min(swapCol, (N - diffCol) / 2); // N-diff是假設左上角為1的情況} else {swapCol = (N - diffCol) / 2;}return swapRow + swapCol;} }

總結

以上是生活随笔為你收集整理的leetcode 782. Transform to Chessboard | 782. 变为棋盘（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。