README.md

1072. 按列翻转得到最大值等行数

English Version

题目描述

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

返回 经过一些翻转后，行与行之间所有值都相等的最大行数 。

 

示例 1：

输入：matrix = [[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

示例 2：

输入：matrix = [[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

示例 3：

输入：matrix = [[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] == 0 或 1

解法

方法一：哈希表

Python3

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnt = Counter()
        for row in matrix:
            t = []
            for v in row:
                if row[0] == 1:
                    v ^= 1
                t.append(str(v))
            s = ''.join(t)
            cnt[s] += 1
        return max(cnt.values())

Java

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> map = new HashMap<>();
        for (int[] row : matrix) {
            if (row[0] == 1) {
                for (int i = 0; i < row.length; ++i) {
                    row[i] ^= 1;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int x : row) {
                sb.append(x);
            }
            String s = sb.toString();
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        return map.values().stream().max(Integer::compareTo).get();
    }
}

C++

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> cnt;
        int ans = 0;
        for (auto& row : matrix) {
            string s = "";
            for (int v : row) {
                if (row[0] == 1) v ^= 1;
                s += to_string(v);
            }
            ++cnt[s];
            ans = max(ans, cnt[s]);
        }
        return ans;
    }
};

Go

func maxEqualRowsAfterFlips(matrix [][]int) int {
	ans := 0
	cnt := map[string]int{}
	for _, row := range matrix {
		s := []byte{}
		for _, v := range row {
			if row[0] == 1 {
				v ^= 1
			}
			s = append(s, byte(v+'0'))
		}
		t := string(s)
		cnt[t]++
		ans = max(ans, cnt[t])
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...