leetcode：782. 变为棋盘【数学找规律 + 模拟】

分析

发现规律：不管怎么行变列变，每行每列的01个数都不变
然后不同行的个数就得等于2（不管怎么变）
所以引申四个判断点：
判断点1：最后只有两种行形式，所以最初也只有两种
判断点2：不同的行的个数差不超过1
判断点3：每行01的个数差不超过1
判断点4：不同行真的是每一位都不同

判断完之后，又有两种选法：10101010，010101
首先先看010101跟当前有多少个不同
如果有奇数个，那么很可惜，我们只能变成101010（因为必须偶数个不同）
另一种是都是偶数个，但101010的改动更少，我们也变更
最后只用考虑第一行跟第一列变更的次数和即可
其他都会跟随

Ac code

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        # 数学题
        # 考虑第一行第一列（简化思维）
        n = len(board)
        if n <= 1:
            return 0
        
        # 找规律1：行列变换不会改变每行每列的01个数
        rows = [''.join(str(c) for c in r) for r in board]
        # 只考虑行即可
        counter = Counter(rows)
        # 取出具体每行的值
        keys = list(counter.keys())
        # 判断点1：最后只有两种行形式，所以最初也只有两种
        if len(keys) != 2:
            return -1
        # 判断点2：不同的行的个数差不超过1
        if abs(counter[keys[0]] - counter[keys[1]]) > 1:
            return -1
        # 判断点3：每行01的个数差不超过1
        if abs(keys[0].count('1') - keys[0].count('0')) > 1:
            return -1
        # 判断点4：不同行真的是每一位都不同
        if any(a == b for a, b in zip(*keys)):
            return -1
        
        # 考虑行列是按010101，找出不同的个数
        rowdiff = sum(board[0][i] != i % 2 for i in range(n))
        coldiff = sum(board[i][0] != i % 2 for i in range(n))
        # 考虑10101010
        # 如果之前的是奇数，那只能变偶数
        # 如果都是偶数，那么选一个小的
        rowdiff = n - rowdiff if rowdiff % 2 != 0 or (n % 2 == 0 and n - rowdiff < rowdiff) else rowdiff
        coldiff = n - coldiff if coldiff % 2 != 0 or (n % 2 == 0 and n - coldiff < coldiff) else coldiff
        
        return (rowdiff + coldiff) // 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结

数学找规律 + 模拟 + 构造