LeetCode1072-按列翻转得到最大值等行数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/

中文链接：https://leetcode-cn.com/problems/flip-columns-for-maximum-number-of-equal-rows/

题目详述

给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的 每个 单元格。翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。

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

示例 1：

1
2
3
输入：[[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

示例 2：

1
2
3
输入：[[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

示例 3：

1
2
3
输入：[[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

提示：

  • 1 <= matrix.length <= 300
  • 1 <= matrix[i].length <= 300
  • 所有 matrix[i].length 都相等
  • matrix[i][j] 为 0 或 1

题目详解

  • 行上所有值都相等，即该行所有元素都为 0 或都为 1。
  • 根据题意，实际上，要达到要求，只存在两种情况：
    • 两行完全相等。
    • 一行翻转后与另一行相等。
  • 现在要求可以最大值，需要把这两种情况合并，产生一个统一条件。可以维持每一行的第一个数永远是 0。如果原本为 0，不做处理；如果为 1，翻转整行。
  • 然后运用哈希表来统计，这需要由一行产生一个 key，可以采用序列化为 String 的方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_01072 {

    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> map = new HashMap<>();
        for (int[] row : matrix) {
            if (row[0] == 1) {
                for (int i = 0; i < row.length; ++i) {
                    row[i] ^= 1;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int x : row) {
                sb.append(x);
            }
            String s = sb.toString();
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        return map.values().stream().max(Integer::compareTo).get();
    }
}
  • 可以换一种方式来产生哈希表的 key，运用 Arrays.hashCode 产生的值为 int。
  • 哈希表的 key 由String 转化为 Integer 可以提高效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_01072 {

    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] row : matrix) {
            if (row[0] == 1) {
                for (int i = 0; i < row.length; ++i) {
                    row[i] ^= 1;
                }
            }
            int k = Arrays.hashCode(row);
            map.put(k, map.getOrDefault(k, 0) + 1);
        }
        return map.values().stream().max(Integer::compareTo).get();
    }
}