1072. 按列翻转得到最大值等行数

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 }

 

上一篇:Django终端打印SQL语句


下一篇:1072 Gas Station