题目描述：
给定 $n \times m$ 矩阵matrix，从中选出任意数量的列并翻转其上的每个单元格。（翻转后，单元格的值从 $0$ 变成 $1$ ，或者从 $1$ 变成 $0$ 。）经过一些翻转之后，行内所有值都相等的最大的行数。（全为 $0$ ，或全为 $1$ 的最大行数）
数据范围：
$1\le m, n \le 300$
题解：
注意题目说的是行内值相等，不是两行完全相等。也就是说相等的或者互补的通过翻转之后会得到行内值相等的行，每一行都进行翻转与不翻转使用 $hash$ 记录相等的个数，得到答案。
优化一下，对行内第一个字符为 $0$ 的不翻转，为 $0$ 的翻转，然后使用 $hash$ 记录最大值。
也可以使用 vector<bool>，这个数据类型带压缩，可以直接 $hash$ ，也可以调用 .flip() 翻转。
.flip：可以翻转该 vector<bool>。.swap：交换两个位置的元素。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
unordered_map<string, int> mp;
int maxEqualRowsAfterFlips(vector<vector<int>> &matrix)
{
int n = matrix.size(), m = matrix[0].size(), ans = 0;
for (int i = 0; i < n; ++i)
{
string s(m, 0);
for (int j = 0; j < m; ++j)
{
s[j] = (matrix[i][j] ^ matrix[i][0]) + '0';
}
ans = max(ans, ++mp[s]);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
unordered_map<vector<bool>, int> mp;
int maxEqualRowsAfterFlips(vector<vector<int>> &matrix)
{
int n = matrix.size(), m = matrix[0].size(), ans = 0;
for (int i = 0; i < n; ++i)
{
vector<bool> tmp(matrix[i].begin(), matrix[i].end());
if (tmp[0])
tmp.flip();
ans = max(ans, ++mp[tmp]);
}
return ans;
}
};
|