leetcode 861

xiaoxiao2021-03-01  2

此题较简单,主要是一种贪婪的思想,已经知道最后的结果是按照二进制来进行评分的,那么首先肯定要让每行的第一个数字都为1,这样就完成了对行的遍历,然后对列进行遍历,因为对于每一列来说,每个数字对结果的贡献都是一样的,那么我们就应该判断1的数目是不是占了大多数,如果没有就进行翻转,所以遍历了行和列之后,就得到最终的结果。看了别人的答案,写的很精简,但还是O(MN)的算法,没有本质的提高,所以没细看。附代码

class Solution:     def matrixScore(self, A):         """         :type A: List[List[int]]         :rtype: int         """         score = 0         if len(A) == 0:             return score         for i in range(len(A)):             if A[i][0] == 1:                 continue             else:                 for j in range(len(A[i])):                     A[i][j] = 1 - A[i][j]         for k in range(1,len(A[0])):             count = 0             for p in range(len(A)):                 if A[p][k] == 1:                     count += 1             if 2*count < len(A):                 for q in range(len(A)):                     A[q][k] = 1 - A[q][k]                      for i in range(len(A)):             for j in range(len(A[0])):                 score += A[i][j] * (2**(len(A[0])-j-1))                          return score

转载请注明原文地址: https://www.6miu.com/read-3650206.html

最新回复(0)