按列翻转得到最大值等行数【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; } }
逆向思维+哈希表+位运算
- 思路
- 我们需要寻找将某些列进行翻转后，最多的行值相同的行数
- 从结果出发进行相同列翻转后，值全部为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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
