1072. Flip Columns For Maximum Number of Equal Rows
Problem
You are given an m x n binary matrix matrix.
You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).
Return the maximum number of rows that have all values equal after some number of flips.
https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
Example 1:
Input:
matrix = [[0,1],[1,1]]
Output:1
Explanation: After flipping no values, 1 row has all values equal.
Example 2:
Input:
matrix = [[0,1],[1,0]]
Output:2
Explanation: After flipping values in the first column, both rows have equal values.
Example 3:
Input:
matrix = [[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.
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]is either0or1.
Test Cases
class Solution:
def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:import pytest
from solution import Solution
@pytest.mark.parametrize('matrix, expected', [
([[0,1],[1,1]], 1),
([[0,1],[1,0]], 2),
([[0,0,0],[0,0,1],[1,1,0]], 2),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, matrix, expected):
assert sol.maxEqualRowsAfterFlips(matrix) == expected
Thoughts
如果某一行经过若干列的翻转可以变成全零(或全一),那么初始时跟它完全相同的行也会变成全零(或全一),而跟它完全相反(零一互补)的行会变成全一(或全零)。
把 matrix 中完全相同或互补的行归为一堆,最终看最大的一堆有多少行即可。
为了方便地处理互补的行,可以把所有行的第一个数字都翻转成一样的,比如都是 1。如果一行的第一个数字原本就是 1 则不用动,如果是 0 则把每个数字都翻转。
时间复杂度 O(m * n),空间复杂度最坏情况也是 O(m * n)。
Code
from collections import defaultdict
class Solution:
def maxEqualRowsAfterFlips(self, matrix: list[list[int]]) -> int:
counter: dict[tuple[int], int] = defaultdict(int)
for row in matrix:
if row[0]:
key = tuple(row)
else:
key = tuple(1 - x for x in row)
counter[key] += 1
return max(counter.values())
评论需要 JavaScript。