0861. 翻转矩阵后的得分 #
- 标签:贪心、位运算、数组、矩阵
- 难度:中等
题目大意 #
描述:给定一个二维矩阵 A
,其中每个元素的值为 0
或 1
。
我们可以选择任一行或列,并转换该行或列中的每一个值:将所有 0
都更改为 1
,将所有 1
都更改为 0
。
在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩阵的得分就是这些数字的总和。
要求:返回尽可能高的分数。
说明:
- $1 \le A.length \le 20$。
- $1 \le A[0].length \le 20$。
A[i][j]
值为0
或1
。
示例:
|
|
解题思路 #
思路 1:贪心算法 #
对于一个二进制数来说,应该优先保证高位(靠前的列)尽可能的大,也就是保证高位尽可能值为 1
。
- 我们先来看矩阵的第一列数,只要第一列的某一行为
0
,则将这一行的值进行翻转。这样就保证了最高位一定为1
。 - 接下来,我们再来关注除了第一列的其他列,这里因为有最高位限制,所以我们不能随意再将某一行的值进行翻转,只能选择某一列进行翻转。
- 为了保证当前位上有尽可能多的
1
。我们可以用两个变量one_cnt
、zeo_cnt
来记录当前列上1
的个数和0
的个数。如果0
的个数多于1
的个数,那么我们就将当前列进行翻转。从而保证当前位上有尽可能多的1
。 - 当所有列都遍历完成后,我们会得到加和最大的情况。
思路 1:贪心算法代码 #
|
|