【Leetcode】1072. Flip Columns For Maximum Number of Equal Rows（异或运算）

迷南。 2022-01-23 05:03 184阅读 0赞

Given a `matrix` consisting of 0s and 1s, we may choose any number of columns in the matrix and flip **every** cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

**Example 1:**

Input: [[0,1],[1,1]]
    Output: 1
    Explanation: After flipping no values, 1 row has all values equal.

**Example 2:**

Input: [[0,1],[1,0]]
    Output: 2
    Explanation: After flipping values in the first column, both rows have equal values.

**Example 3:**

Input: [[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.

**Note:**

1.  `1 <= matrix.length <= 300`
2.  `1 <= matrix[i].length <= 300`
3.  All `matrix[i].length`'s are equal
4.  `matrix[i][j]` is `0` or `1`

题目大意：

给出一个矩阵，可以按照列翻转一整列的数字 1-0 0-1。最后得到的矩阵中全行数字相同的行最多有多少。

解题思路：

我们会发现，最终满足条件只有全1、0。

所以对于每一行与**其余全部行**按照位置异或之后得出结果为0或者为列数可以满足条件。

最终找出最大值。

class Solution {
    public:
        int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
            int row = matrix.size();
            int col = matrix[0].size();
            
            int ans = 1;
            for(int i =0;i<row;i++){
                int res = 0;
                for(int j=0;j<row;j++){
                    int tmp = 0;
                    for(int k=0;k<col;k++){
                        tmp += (matrix[i][k] ^ matrix[j][k]);
                    }
                    if(tmp==col||tmp==0) res++;
                }
                ans = max(ans, res);
            }
            return ans;
        }
    };