X

LEETCODE 1072. Flip Columns For Maximum Number of Equal Rows 解题思路分析

题目大意:

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

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

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

示例 1:

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

示例 2:

输入:[[0,1],[1,0]]
输出: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 或


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1072

解题思路分析:

这道题目很巧妙,暴力解是行不通的,我们需要动脑筋变换一下思路。题目给出的matrix每一行都有若干个0和1组成,例如,101,我们可以把每一行看做一个字符串,要想把这行全变成0或者全变成1,我们需要变换1列(将1个0都变为1)或者2列(将2个1都变为0)。这样变换之后,由于是列上的元素同时翻转,因此其他行如果事先也存在 101 或者010的话,他们也会相应的变成全是0或者全是1。

这样问题就转化为:

  1. 先将当前行看做是一个字符串。
  2. 看Matrix中含有多少个当前字符串或者当前字符串的翻转字符串。(当前字符串和翻转字符串可以看做是相同的。因为当字符串全变为1时,翻转字符串会全变为0,都是符合条件的答案)
  3. 找到一个相同个数最大的值即为结果。

思路大体清楚了,按照这个解法,代码虽然可以通过,但效率不高,执行时间需要200多毫秒。主要原因在于用字符串作为key存储时效率较低,进而考虑优化方案,由于字符串中都是0和1,用2进制数代替String是非常好的选择。

之前的文章多次讲到过有关2进制数的位运算,这里简单再啰嗦两句如何将一组数[1, 1, 0]转化为二进制的表现形式。我们想要得到100这个二进制数,这并不像字符串操作那样方便,几个加号就能解决,首先,需要循环这组数字,从第0位开始,取出数字1,当前的二进制数就是1,然后我们要在1的后面添加第1位的1,我们需要将1先向左边移动一位,空出最低位,左移的位操作运算符为<<,即1 << 1,代表将1左移1位。此时二进制数变为10。接下来,用或运算将下一个1放在二进制的最低位,即 10 | 1 = 11。以此类推。因此将[1, 1, 0]变为二进制数的流程大概如下:

// [1, 1, 0]
1             // [1, 0]
1 << 1 = 10   // [1, 0]
10 | 1 = 11   // [0]
11 << 1 = 110 // [0]
110 | 0 = 110 // []

看下完整代码:

public int maxEqualRowsAfterFlips(int[][] matrix) {
    Map<Integer, Integer> map = new HashMap<>(); // 用于记录每种字符串出现的次数
    int res=0; // 定义返回结果
    for(int i=0;i<matrix.length;i++){ // 循环每一行
        int n1=0, n2=0; // 定义两个2进制数,代表当前行组成的字符串,以及翻转字符串
        for(int j=0;j<matrix[i].length;j++){ // 循环当前行的每一列
            n1 = ((n1<<1) | matrix[i][j]); // 二进制形式的字符串
            n2 = ((n2<<1) | (matrix[i][j] == 0? 1:0)); // 二进制形式的翻转字符串
        }
        int n = map.getOrDefault(n1, 0) + 1; // 当前字符串出现次数加一
        map.put(n1, n); // 更新当前字符串出现次数
        map.put(n2, n); // 更新当前翻转字符串的出现次数
        res = Math.max(res, n); // 更新最大值
    }
    return res;
}

本解法用时8ms。

Runtime: 8 ms, faster than 97.17% of Java online submissions for Flip Columns For Maximum Number of Equal Rows.

Memory Usage: 52.8 MB, less than 100.00% of Java online submissions for Flip Columns For Maximum Number of Equal Rows.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1072-flip-columns-for-maximum-number-of-equal-rows-解题思路分析/
Categories: leetcode
kwantong: