Description:
image.png
Link:
https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
解題方法：
解這道題有一些細(xì)節(jié)需要想清楚：
- 矩陣中元素要么是0要么是1，而我們能做的操作是翻轉(zhuǎn)
（0->1 or 1->0），所以最后結(jié)果某一行不管是全為0還是全為1其實(shí)是一樣的（以下稱為全等），并不會影響這道題的解。 - 假設(shè)任意兩行在某一列上不相同，那么無論如果翻轉(zhuǎn)，他們的最終結(jié)果都不會相同，但是需要注意的是，這并不影響他們成為全等的行（他們也可能一個全為0，另一個全為1）。
- 我們總是能通過翻轉(zhuǎn)操作讓至少一行全等.
- （
這個細(xì)節(jié)可以用來論證解法）因?yàn)槊看畏D(zhuǎn)我們都要對每一列上的所有元素進(jìn)行翻轉(zhuǎn)，我們并不能對單獨(dú)幾行的列進(jìn)行翻轉(zhuǎn)，所以當(dāng)我們通過一系列翻轉(zhuǎn)，讓一行全等之后，其他行的結(jié)果已經(jīng)便成為了一個定值，總結(jié)來說就是：當(dāng)某一行全等時，整個矩陣全等行數(shù)已經(jīng)成為一個定值。 - 根據(jù)細(xì)節(jié)4，這道題的解肯定會出現(xiàn)在我們嘗試讓某一行全等的時候，也就是說，如果我們輪流讓某一行全等（根據(jù)細(xì)節(jié)1，全為0還是全為1無所謂）的過程中，矩陣中最多的全等行數(shù)就是這道題的解。
- （
減少時間復(fù)雜度的細(xì)節(jié)）對任意的兩行i和j，假設(shè)i和j為0的列數(shù)的集合各自為i0和j0，為1的列數(shù)的集合各自為i1和j1，如果i0 == j0或者i0 == j1的時候，那么這嘗試吧一行變成全等之后，另一行肯定也會是全等。 - 所以根據(jù)細(xì)節(jié)6，我們只需要把每行為0和為1的列數(shù)都統(tǒng)計起來，可以把列數(shù)轉(zhuǎn)換為string，用兩個hash存起來，然后遍歷其中一個hash表的string，獲得對應(yīng)的計數(shù)，再加上另一個hash表中相同string的計數(shù)，就是其中一個解（即把一行變成全等的解），找出這些解的最大值就是本題所求。
Tips
其實(shí)不需要兩個hash表，一個就夠了。
Time Complexity：
O(mn)
完整代碼：
class Solution {
public:
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
int ans = 0;
unordered_map<string, int> zeros;
unordered_map<string, int> ones;
for(int i = 0; i < matrix.size(); i++) {
string zero, one;
for(int j = 0; j < matrix[0].size(); j++) {
if(matrix[i][j] == 1) {
one += to_string(j);
} else {
zero += to_string(j);
}
}
zeros[zero]++;
ones[one]++;
}
for(auto a: zeros) {
ans = max(a.second + ones[a.first], ans);
}
return ans;
}
};
