861. 翻转矩阵后的得分（Rating 1818）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

861. 翻转矩阵后的得分

Rating 1818

思路

需要想清楚这样几个结论

1. 对于二进制数，最高位是1比其他位全是1要大，如1000 > 0111
2. 对于一个翻转策略，交换其中的翻转顺序后结果不变，如【翻转第1行再翻转第2列】与【翻转第2列再翻转第1行】结果是一样的

因此，本题优先保证所有数最高位是1即可。如果第一列都为0那么翻转第1列即可，否则翻转最高位是0的行即可

接着从第2列开始依次遍历列，让每列1的数量尽可能多即可

代码

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt0, cnt1 = 0, 0
        for i in range(m):
            cnt0 += (grid[i][0] == 0)
            cnt1 += (grid[i][0] == 1)
        if cnt1 == 0: # 如果第1列全是0
            for i in range(m):
                grid[i][0] = 1
        else: # 否则，翻转最高位为0点行
            for i in range(m):
                if grid[i][0] == 0:
                    for j in range(n):
                        grid[i][j] = 1 - grid[i][j]
        for j in range(1, n): # 从第2列开始遍历
            cnt0, cnt1 = 0, 0
            for i in range(m):
                cnt0 += (grid[i][j] == 0)
                cnt1 += (grid[i][j] == 1)
            if cnt1 >= cnt0: # 1的数量大于等于0的数量，则不用翻转
                continue
            for i in range(m): # 否则，翻转该列
                grid[i][j] = 1 - grid[i][j]
        ret = 0
        for i in range(m):
            num = 0
            for j in range(n):
                num = (num << 1) + grid[i][j]
            ret += num
        return ret