题目描述
给了一个二维矩阵，矩阵的元素不是0就是1
你可以进行任意次操作，让某行或者某列进行翻转
元素的得分是每一行二进制的和
问怎么操作可以让总得分最大？
| f1 贪心+计算增量 |
基本分析
- 为啥可以贪心？（1）对每行来说，首位肯定是1最好，遮掩某些行需要翻转，某些不翻；（2）对同一列来说，大家的优先级都是一样的，这样比就看当前1的个数多还是当前0的个数多
- 怎么计算结果？按照列来计算，每次计算当前位置对结果的贡献
- 有翻转的时候怎么考虑？没有翻转的时候直接计数，有的时候看grid[i][0]就能看出来，如果翻转，那么0或者1的个数是1 - grid[i][j]
代码
class Solution:
def matrixScore(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = m * (1 << (n - 1))
for j in range(1, n):
cnt = 0
for i in range(m):
if grid[i][0] == 1:
cnt += grid[i][j]
else:
cnt += 1 - grid[i][j]
cnt = max(cnt, m - cnt)
ans += cnt * (1 << (n - 1 - j))
return ans
总结
- 看出行和列贪心的逻辑
- 计算每一列的值的时候需要考虑这一行是不是进行了翻转
- 计算累加结果的时候不能忘了*每一列的1的个数，否则这一列只计算了一个