1. 题目
给定由若干 0 和 1 组成的矩阵 matrix,从中选出任意数量的列并翻转其上的 每个 单元格。翻转后,单元格的值从 0 变成 1,或者从 1 变为 0 。
回经过一些翻转后,行与行之间所有值都相等的最大行数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/flip-columns-for-maximum-number-of-equal-rows
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 示例
输入:[[0,1],[1,1]]
输出:1 解释:不进行翻转,有 1 行所有值都相等。
3. 思路
首先,判断两行能否经过一定反转达到相同:
000与111可以;
001与110可以;
010与101可以;
发现,以上例子是所有对应列异或为1就能达到相同。
扩展到所有:
此时要使用一定的规则控制所有行变化,用HashMap<String, Integer>实现。
1. 如果第一个元素为0,则整行不变,整行作为Key存储,Value + 1;
2. 如果第一个元素为1,整行与1异或,并将结果作为Key存储,Value+1;
3. 返回最大值。
4. Code实现
1 public class MaxEqualRowsAfterFlips {
2 public int maxEqualRowsAfterFlips (int[][] matrix) {
3 /**
4 * @Method: maxEqualRowsAfterFlips
5 * @Author: haifwu
6 * @Version: 1.0
7 * @Date: 23/05/2021 13:38
8 * @param matrix
9 * @Return: int
10 * @Description:
11 * 首先要知道,怎么判断两个行的能否经过一定的翻转达到全行相同.
12 * 000 和 111 这两个是一样的;
13 * 010 和 101 这两个也是一样的,因为它们可以通过翻转第二列完成相同。
14 * 110 和 001 也是一样,因为不管是翻转前两列还是翻转最后一列,都会让两行都进入相同的状态。
15 * 如果两个行是可以通过翻转相同的列达到全行相同,那么就要满足,两行的相同的位置上的值异或之后等于全1.
16 * 具体的规则就是:
17 * 1. 如果第一位是 0 的话,那么就把全行都不用异或操作,直接转为字符串类型,作为key保存,且 value + 1.
18 * 2. 如果第一位是 1 的话,那么就把全行的每个位置上的值都和 1 进行异或操作,然后转为字符串类型,作为key保存在下来,且 value+1.
19 */
20 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
21 return 0;
22 }
23 Map<String, Integer> map = new HashMap<>();
24 int res = 0;
25 boolean firstZero = false;
26 for (int i = 0, len = matrix.length; i < len; i++) {
27 if(matrix[i][0] == 0) {
28 firstZero = true;
29 } else {
30 firstZero = false;
31 }
32 StringBuilder temp = new StringBuilder();
33 for(int j = 0, colLen = matrix[i].length; j < colLen; j++) {
34 if(firstZero) {
35 temp.append(matrix[i][j]);
36 } else {
37 temp.append((matrix[i][j] ^ 1));
38 }
39 }
40 String tempStr = temp.toString();
41 res = Math.max(map.getOrDefault(tempStr, 0) + 1, res);
42 map.put(tempStr, map.getOrDefault(tempStr, 0) + 1);
43 }
44 return res;
45 }
46
47 public static void main(String[] args) {
48 Scanner scanner = new Scanner(System.in);
49 int m = scanner.nextInt(), n = scanner.nextInt();
50 int[][] matrix = new int[m][n];
51 for (int i = 0; i < m; i++) {
52 for (int j = 0; j < n; j++) {
53 matrix[i][j] = scanner.nextInt();
54 }
55 }
56 System.out.println(new MaxEqualRowsAfterFlips().maxEqualRowsAfterFlips(matrix));
57 }
58 }