共计 3072 个字符，预计需要花费 8 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 782. 变为棋盘 ，难度为 艰难。
Tag :「结构」
一个 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
结构剖析
数据范畴具备肯定的迷惑性，但其并不是一个棋盘搜寻问题。
咱们须要思考何种状况下无解，以及有解状况的最小步数。
在给定棋盘大小 $n$ 的前提下，所能结构的非法棋盘只有两种状况：首个格子为 $0$ 或首个格子为 $1$，即问题转化为是否结构出非法棋盘，以及结构哪种非法棋盘所用步数更小。
同时，替换行和替换列均不会影响行的品种数量和列的品种数量，因而咱们能够失去第一个判断无解的条件：若起始棋盘的行 / 列品种数不为 $2$，必然无奈结构出非法棋盘。
假如起始的行别离为 r1 和 r2，起始的列别离为 c1 和 c2。不难发现第二性质：若能形成非法棋盘，r1 和 r2 中 $0$ 和 $1$ 的数量必然相等，c1 和 c2 中的 $0$ 和 $1$ 的数量必然相等。
同时因为替换行和替换列具备对称性和独立性，咱们能够先应用「替换列」来进行剖析，替换列不会导致行品种发生变化，但会导致行的数值散布发生变化。
因而第二性质可拓展为：r1 和 r2 对称地位为必然不同，c1 和 c2 对称地位必然不同，即两者异或后果为必然为 $(111…111)_2$，即为 mask = (1 << n) - 1，否则必然无解。
若上述两性质满足，可能有解。
因为 r1 和 r2 及 c1 和 c2 对称地位必然不同，因而咱们调整好 r1 后，r2 惟一确定（c1 和 c2 同理），同时结构其中一种距离行为 t = $(…101)_2$，依据非法棋盘定义可知要么是将首行调整为 $t$，要么是将次行调整为 $t$。
咱们设置函数 int getCnt(int a, int b) 计算将 a 变为 b 所须要的最小转换次数，两状态转换所需次数为不同位个数除以 $2$（一次替换可实现打消两个不同位）。
别离计算「将 r1 和 r2 转换为 t 所需步数」和「将 c1 和 c2 转换为 t 所需步数」，两者之和即为答案。
Java 代码：
class Solution {
int n = 0, INF = 0x3f3f3f3f;
int getCnt(int a, int b) {return Integer.bitCount(a) != Integer.bitCount(b) ? INF : Integer.bitCount(a ^ b) / 2;
}
public int movesToChessboard(int[][] g) {
n = g.length;
int r1 = -1, r2 = -1, c1 = -1, c2 = -1, mask = (1 << n) - 1;
for (int i = 0; i < n; i++) {
int a = 0, b = 0;
for (int j = 0; j < n; j++) {if (g[i][j] == 1) a += (1 << j);
if (g[j][i] == 1) b += (1 << j);
}
if (r1 == -1) r1 = a;
else if (r2 == -1 && a != r1) r2 = a;
if (c1 == -1) c1 = b;
else if (c2 == -1 && b != c1) c2 = b;
if (a != r1 && a != r2) return -1;
if (b != c1 && b != c2) return -1;
}
if (Integer.bitCount(r1) + Integer.bitCount(r2) != n) return -1;
if (Integer.bitCount(c1) + Integer.bitCount(c2) != n) return -1;
if ((r1 ^ r2) != mask || (c1 ^ c2) != mask) return -1;
int t = 0;
for (int i = 0; i < n; i += 2) t += (1 << i);
int ans = Math.min(getCnt(r1, t), getCnt(r2, t)) + Math.min(getCnt(c1, t), getCnt(c2, t));
return ans >= INF ? -1 : ans;
}
}TypeScript 代码：
let n: number = 0, INF = 0x3f3f3f3f
function bitCount(x: number): number {
let ans = 0
while (x != 0 && ++ans >= 0) x -= (x & -x)
return ans
}
function getCnt(a: number, b: number): number {return bitCount(a) != bitCount(b) ? INF : bitCount(a ^ b) / 2
}
function movesToChessboard(g: number[][]): number {
n = g.length
let r1 = -1, r2 = -1, c1 = -1, c2 = -1, mask = (1 << n) - 1
for (let i = 0; i < n; i++) {
let a = 0, b = 0
for (let j = 0; j < n; j++) {if (g[i][j] == 1) a += (1 << j)
if (g[j][i] == 1) b += (1 << j)
}
if (r1 == -1) r1 = a
else if (r2 == -1 && a != r1) r2 = a
if (c1 == -1) c1 = b
else if (c2 == -1 && b != c1) c2 = b
if (a != r1 && a != r2) return -1
if (b != c1 && b != c2) return -1
}
if (bitCount(r1) + bitCount(r2) != n) return -1
if (bitCount(c1) + bitCount(c2) != n) return -1
if ((r1 ^ r2) != mask || (c1 ^ c2) != mask) return -1
let t = 0
for (let i = 0; i < n; i += 2) t += (1 << i)
const ans = Math.min(getCnt(r1, t), getCnt(r2, t)) + Math.min(getCnt(c1, t), getCnt(c2, t))
return ans >= INF ? -1 : ans
};- 工夫复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.782 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
