1072. Flip Columns For Maximum Number of Equal Rows

1072. Flip Columns For Maximum Number of Equal Rows

难度: Medium

刷题内容

原题连接

内容描述

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column.  Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.



Example 1:

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.
Example 2:

Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.
Example 3:

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.


Note:

1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
All matrix[i].length's are equal
matrix[i][j] is 0 or 1

思路 1
*- 时间复杂度: O(m * n)- 空间复杂度: O(m)*

  • 对于某一行,我们如果想让它那一行元素全部相等的话,我们要不全部变成1,要不全部变成0
  • 对于任意两行,如果他们的某一列的cell相等,那么无论这列被翻转多少次,这两列都是一样的
  • 对于任意两行,如果他们的某一列的cell不相等,那么无论这列被翻转多少次,这两列都不会一样

对于每一行来说,我们如果想让这一行变成全部一样的元素,我们需要反转某些列。然后对于需要反转的列我们就在原matrix上将该行该列置为1,否则置为0

接下来对于任意两行,如果他们需要反转的列是相等的或者是互补的,如果他们当中任意一个最终全部相等的话,另外一个也会全部相等。

因此我们可以对每一行i做假设,行i会出现在最终结果中,如果我们把行i全部变成0,需要反转哪些列呢?假设为seti,我们就反转全部的seti,
然后我们看看别的哪些行变成的样子跟当前行是一样的或者互补的,最终结果就肯定就会有它。最后取最大值就可以了

```python
class Solution:

top Created with Sketch.