每日一题20201207(861. 翻转矩阵后的得分)

每日一题20201207(861. 翻转矩阵后的得分)

链接就不放了 容易被和谐

每日一题20201207(861. 翻转矩阵后的得分)

思路

  • 贪心

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

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

    分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]

每日一题20201207(861. 翻转矩阵后的得分)