题目如下:
- 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
解题思路: 把 matrix 任意一行的的所有元素拼成一个字符串, 例如 0010110, 要把这行变成全是 0 或者全是 1, 那么要经过 4 次或者 3 次的列变换. 变换之后, 很显然 matrix 中字符串为 0010110 或者 1101001 的行最后也会变成全为 0 或者全为 1. 因此题目就变成了找出 matrix 中的某一行, 使得在整个 matrix 中和这行相等的行或者相反的行的最多 (即 0 对应 1,1 对应 0 的行). 怎么求出最大值的呢? 并查集很适合这个场景.
代码如下:
- class Solution(object):
- def maxEqualRowsAfterFlips(self, matrix):
- """
- :type matrix: List[List[int]]
- :rtype: int
- """
- parent = [i for i in range(len(matrix))]
- def find(v1):
- p1 = parent[v1]
- if p1 != v1:
- return find(p1)
- return p1
- def union(v1,v2):
- p1 = find(v1)
- p2 = find(v2)
- if p1 <= p2:
- parent[v2] = p1
- else: parent[v1] = p2
- def toString(l1):
- new_l1 = map(lambda x: str(x), l1)
- return ''.join(new_l1)
- row = []
- row_inverse = []
- for i in range(len(matrix)):
- row.append(toString(matrix[i]))
- v1_inverse = ''
- for k in row[i]:
- v1_inverse += '0' if k == '1' else '1'
- row_inverse.append(v1_inverse)
- for i in range(len(matrix)):
- v1 = row[i]
- v1_inverse = row_inverse[i]
- for j in range(i+1,len(matrix)):
- v2 = row[j]
- if v1 == v2 or v1_inverse == v2:
- union(i,j)
- dic = {}
- res = 0
- for i in range(len(matrix)):
- p = find(i)
- dic[p] = dic.setdefault(p,0) + 1
- res = max(res,dic[p])
- return res
来源: http://www.bubuko.com/infodetail-3092524.html