【每日一题Day207】LC1072按列翻转得到最大值等行数 | 逆向思维+哈希表+位运算网站首页 技术交流

【每日一题Day207】LC1072按列翻转得到最大值等行数 | 逆向思维+哈希表+位运算

TIkitianya 2024-06-17 10:22:31

简介【每日一题Day207】LC1072按列翻转得到最大值等行数 | 逆向思维+哈希表+位运算

按列翻转得到最大值等行数【LC1072】

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的每个单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

返回 经过一些翻转后，行与行之间所有值都相等的最大行数 。

第四天了，马上就能出去了
逆向思维很重要

回溯【超时】

思路：回溯【超时】

暴力枚举每一列翻转或不翻转，统计每一行单元格为0的个数，如果个数为0或者为n，那么代表该行为所有值均相等。

实现

class Solution {
    int[][] matrix;
    int[] count0;
    int m, n;
    int res = 0;
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        this.matrix = matrix;
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.count0 = new int[m];// 为0或者n时，等行
        // 回溯 m^2*m
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (matrix[i][j] == 0){
                    count0[i]++;
                }
            }
        }
        dfs(0);
        return res;
    }
    public void dfs(int j){
        if (j == n){
            res = Math.max(res, equalRow());
            return;
        }
        // 不翻
        dfs(j + 1);
        // 翻
        for (int i = 0; i < m; i++){
            if (matrix[i][j] == 0){
                count0[i]--;
            }else{
                count0[i]++;
            }
        }
        dfs(j + 1);
        // 回溯
        for (int i = 0; i < m; i++){
            if (matrix[i][j] == 0){
                count0[i]++;
            }else{
                count0[i]--;
            }
        }

    }
    public int equalRow(){
        int rows = 0;
        for (int i = 0; i < m; i++){
            if (count0[i] == 0 || count0[i] == n){
                rows++;
            }
        }
        return rows;
    }
}

复杂度
- 时间复杂度： $O(m^3)$
- 空间复杂度： $O (m)$

逆向思维+哈希表+位运算

思路
- 我们需要寻找将某些列进行翻转后，最多的行值相同的行数
- 从结果出发进行相同列翻转后，值全部为0或者为1的行一定是相同的行或者互补的行，该类行可以称为等价行
  - 1，0，0，1以及1，0，0，1
  - 1，0，0，1以及0，1，1，0
  - 1，0，0，1与1，0，1，1无论进行怎样的列翻转，一定只有某一行值相等
- 因此题意可以转化为寻找等价行的最多数目，可以将每一行转化为起始值为0的行，将互补行转化为相同的行，使用哈希表统计相同行的最大数目，返回即可
  - 转化时利用异或的性质
    - 如果第一个数为0，那么不需要进行转化，0异或其他数为自身
    - 如果第一个数为1，那么需要进行转化，1异或其他数为相反数

实现

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int res = 0;
        Map<String,Integer> count = new HashMap<>();
        for (int[] r : matrix){
            char[] cs = new char[n];
            for (int j = 0; j < n; j++){
                cs[j] = (char) (r[0] ^ r[j]);
            }
            int c = count.merge(String.valueOf(cs), 1, Integer::sum);
            res = Math.max(res, c);
        }
        return res;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/flip-columns-for-maximum-number-of-equal-rows/solutions/2270101/ni-xiang-si-wei-pythonjavacgo-by-endless-915k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。