X

LEETCODE 201. Bitwise AND of Numbers Range 解题思路分析

题目大意:

数字范围按位与

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

示例 1:

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

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

解题思路分析:

看完本题的数据规模后,心里一凉,发现暴力解是行不通的。不过好在我们可以通过剪枝操作来达到优化的效果,因此暴力解法是本题的基础。接下来我们先看下原始版本的代码:

    int res=m;
    for(int i=m+1;i<=n;i++){
        res &= i;
    }
    return res;

在思考如何优化之前,我们应该先思考一下按位与的特性:

  1. 数字0与任何数进行按位与的结果一定是0。
  2. 如果两个二进制数的长度不同,他们进行按位与的结果也一定是0。

上面两个知识点是我们本题优化的关键所在,首先我们来求出两个数字的二进制长度并进行比较,如果不一致,直接返回0。这一步剪枝至关重要,这使得剩下的分支中,m和n的差距大大降低,这也就大幅减少了循环的次数。接下来我们需要按照上面暴力解的方式从m循环至n,计算出所有数字的按位与。不过,在循环过程中,当我们遇到了值为0的中间结果时,根据按位与的第一条特性,最终结果一定是0,因此此时可中断退出循环。

不过到这里还没有结束,先看下目前为止的代码:

public int rangeBitwiseAnd(int m, int n) {
    // 如果两个数字的二进制长度不同,返回0
    if(Integer.toBinaryString(m).length()!=
      Integer.toBinaryString(n).length()){
        return 0;
    }
    int res=m;
    for(int i=m+1;i<=n;i++){
        res &= i;
        if(res == 0){
            break;
        }
    }
    return res;
}

看似天衣无缝的代码,提交后,竟然错在了下面这个例子上:

输入:
2147483646
2147483647

输出:
0 (错误)

正确答案:
2147483646

想了半天才反应过来,原因出在java语言Integer型数字的最大值问题上(其他语言可能没事)。java中int的最大值是2147483647,当i循环完2147483647并进行加一操作时,i并不会变成2147483648(int越界),而是会变成0,此时循环继续,0再与之前的结果进行按位与操作后结果变为0,退出循环,造成返回结果是0。因此修改后的最终代码如下:

public int rangeBitwiseAnd(int m, int n) {
    // 如果两个数字的二进制长度不同,返回0
    if(Integer.toBinaryString(m).length()!=
      Integer.toBinaryString(n).length()){
        return 0;
    }
    // 如果两个数字相同,返回m
    // 此处实际上是为了避免m等于MAX_VALUE
    if(m == n){
        return m;
    }
    int res=m;
    for(int i=m+1;i<=n;i++){
        res &= i;
        // 如果res为0,或者i已经循环至MAX_VALUE
        if(res == 0 || i == Integer.MAX_VALUE){
            break; // 退出循环
        }
    }
    return res;
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 43.16% of Java online submissions for Bitwise AND of Numbers Range.

Memory Usage: 39 MB, less than 10.00% of Java online submissions for Bitwise AND of Numbers Range.

实际上本题还存在其他解法,看了很多大神的帖子,发现通过纯粹的二进制运算的解法效率更高,这里暂且掠过(偷懒)。

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