每日一题20201207（861. 翻转矩阵后的得分）

链接就不放了 容易被和谐

image-20201207142055840

思路

• 贪心

  只要保证每一行的数是最大的，那么总的数字就是最大的。

  怎么保证每一行的数字是最大的呢，高位越大，整个数字就越大。

  分3步:

  1. 把所有高位都变成1
  2. 开始遍历第2到N行，把每列里面0比较多的进行旋转，保障1比0多
  3. 遍历求和

class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        for l in range(len(A)):
            # 把每一列第一个数为0的行进行替换
            if A[l][0] == 0:
                self.changeLine(A, l)
        for k in range(len(A[0])):
            for _ in range(1, len(A)):
                self.changeColumn(A, k)
        result = 0
        for l in range(len(A)):
            temp = 0
            for c in range(len(A[l])):
                temp = temp + A[l][c] * 2 ** (len(A[l]) - c - 1)
            result += temp
        return result
    
    def changeLine(self, A, line):
        for i in range(len(A[line])):
            A[line][i] = 1 - A[line][i]
    
    def changeColumn(self, A, col):
        avg = sum([A[x][col] for x in range(len(A))]) / len(A)
        # 如果这一列加起来平均数小于0.5，那么说明0比1多
        if avg < 0.5:
            for l in range(len(A)):
                A[l][col] = 1 - A[l][col]

image-20201207142914652