class Solution {
public:
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
}
};
1072. 按列翻转得到最大值等行数
给定 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.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j] == 0 或 1原站题解
python3 解法, 执行用时: 164 ms, 内存消耗: 16.2 MB, 提交时间: 2022-12-04 13:52:32
class Solution:
def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
#------------ 只有当行有相同的mode后，再经过列的翻转，同时改变。可以同时行中数字全相同。
mode_freq = defaultdict(int)
for row in matrix:
mode = ""
if row[0] == 0:
mode = ''.join([str(c) for c in row])
else:
for c in row:
mode += ('0' if c == 1 else '1')
mode_freq[mode] += 1
return max(mode_freq.values())
javascript 解法, 执行用时: 108 ms, 内存消耗: 50.4 MB, 提交时间: 2022-12-04 13:51:59
/**
* @param {number[][]} matrix
* @return {number}
* 只有某两行对应元素全部相同或相反，变换任意列数的列后这两行才能
* 同时各自行内元素全部相同，否则不论变换哪几列、这两行一定有一行无法做到
* 行内元素全部相同
* 题目要求变换任意列数的列后行内元素相同的列的最大数量，
* 就是要求原矩阵中按位全部相同或全部相反的行的最大数量。
*/
var maxEqualRowsAfterFlips = function(matrix) {
let res = 0
let map = new Map()
let p = 0
let temp = ''
for(let r of matrix) {
p = 1 ^ r[0]
for(let i = 0;i < r.length;i++) r[i] = r[i] ^ p
temp = r.join('')
if(map.has(temp)) {
map.set(temp, map.get(temp) + 1)
} else map.set(temp, 1)
res = Math.max(res, map.get(temp))
}
return res
};
python3 解法, 执行用时: 108 ms, 内存消耗: 17 MB, 提交时间: 2022-12-04 13:51:29
class Solution:
def maxEqualRowsAfterFlips(self, matrix) -> int:
counter_dic = dict()
maxCount = 0
for row in matrix:
if row[0] == 1:
tup_row = tuple(1-x for x in row)
else:
tup_row = tuple(row)
# 把tuple_row存在字典里
if tup_row in counter_dic:
counter_dic[tup_row] += 1
else:
counter_dic[tup_row] = 1
# 遍历找到最大值
for count in counter_dic.values():
maxCount = max(maxCount, count)
return maxCount
cpp 解法, 执行用时: 152 ms, 内存消耗: 68.9 MB, 提交时间: 2022-12-04 13:50:50
class Solution {
public:
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string, int> m;
int res = 0;
for (auto& r : matrix) {
string s;
int d = 1 ^ r[0];
for (auto x : r) {
s += (d ^ x) + '0';
}
++m[s];
res = max(res, m[s]);
}
return res;
}
};
javascript 解法, 执行用时: 136 ms, 内存消耗: 50.6 MB, 提交时间: 2022-12-04 13:50:14
/**
* @param {number[][]} matrix
* @return {number}
*/
var maxEqualRowsAfterFlips = function(matrix) {
let obj = matrix.reduce((obj, item) => {
let str
if (item[0] === 0) {
str = item.map(item => item ^ 1).join('')
} else {
str = item.join('')
}
obj[str] ? obj[str]++ : obj[str] = 1
return obj
}, {})
return Math.max(...Object.values(obj))
};