[LeetCode] 1072. Flip Columns For Maximum Number of Equal Rows

[grandyang]

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.

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.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1.

这道题给了一个 mxn 大小的二进制数组 matrix，即只含有0和1两个数字，说是可以选择任意数量的列进行翻转，即将0翻为1，或将1翻为0。问经过翻转后最多能有多少行可以使得其数字完全相同，即该行数字均为0，或者均为1。题目中给了好几个例子可以帮助我们理解，首先来想一下，什么情况下通过翻转可以得到相同数字的行，比如例子2，第一行是 [0, 1]，第二行是 [1, 0]，对应位置的数字正好错开了，则依次翻转正好可以形成两个完全相同的行。而对于例子3，后两行经过翻转后可以变为相同的行，但这种翻转方式无论如何也无法将首行变为完全相同，所以必须要有一种方式来归纳所有可以通过某种翻转变成完全相同的行。当然这里并不能真的去翻转所有的列的组合，然后再去一个一个检验行上的数字是否相同，想想都觉得太不高效了，会被 OJ 教育。这里需要将每一行 encode 成为一个 pattern，使得可以通过翻转若干列形成相同数字的列都能被编码成相同的 pattern，这样使用一个 HashMap 来建立 pattern 和其出现次数之间的映射，最终某个 pattern 出现的最多的次数就是能翻转成相同的数字的行数。编码每一个行成为一个字符串是比较理想的操作，但这里不能直接将每行转为字符串，比如例子2，若直接将两行编码成 "01" 和 "10"，并不能达到统计的效果，所以这里的编码规则需要改一下，当需要编码的行的第一个数字是1的话，按照其原有的数字编码，若是0的话，则每个数字都翻转一下再编码，则例子2的两行都可以编码成 "10"，从而知道了出现次数最多的是2，即为所求，理解了思路，不难写出代码如下所示：

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
		unordered_map<string, int> patternCnt;
		int m = matrix.size(), n = matrix[0].size(), res = 0;
		for (int i = 0; i < m; ++i) {
			string row;
			for (int j = 0; j < n; ++j) {
				if (matrix[i][0] == 1) row += to_string(matrix[i][j]);
				else row += to_string(!matrix[i][j]);
			}
			++patternCnt[row];
			res = max(res, patternCnt[row]);
		}
		return res;
    }
};

Github 同步地址:

#1072

参考资料：

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/discuss/303897/Java-easy-solution-%2B-explanation

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/discuss/303847/Simple-C%2B%2B-Solution-with-comments

LeetCode All in One 题目讲解汇总(持续更新中...)