leetcode 201. Bitwise AND of Numbers Range 最长公共前缀问题 + 位操作-蒲公英云

leetcode 201. Bitwise AND of Numbers Range 最长公共前缀问题 + 位操作

Dear 丶 2022-06-08 09:12 258阅读 0赞

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

这道题最自觉的做法就是循环做位and操作，但是我在网上看到了一个做法，想法很棒，这道题可以直接转化为另一个问题：再一串连续的数组中，寻找他们的公共前缀。

直接暴力去计算可能要超时

代码如下：

/*
 * 这道题考察的是位运算的使用
 * 那么这道题其实并不难，我们先从题目中给的例子来分析，
 * [5, 7]里共有三个数字，分别写出它们的二进制为：
 * 101　　110　　111
 * 相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，
 * 如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：
 * 11010　　11011　　11100　　11101　　11110
 * 
 * 那么本题就可以转化为另一个问题，直接找一串连续数字的公共前缀
 * 
 * */
public class Solution 
{
    public int rangeBitwiseAnd(int m, int n) 
    {
        int i=0;
        while(m!=n)
        {
            m=m>>1;
            n=n>>1;
            i++;
        }
        return (m<<i);
    }
    /*
     * 这是直接做或操作，但是可能超时
     * */
    public int rangeBitwiseAndByLoop(int m, int n) 
    {
        int res=m;
        for(int i=m+1;i<=n;i++)
            res &=i;
        return res;
    }
}

下面是C++的做法，这道题肯定是用位运算来组，最直接的做法就是循环遍历去做，但是会超时，后来网上发现了一个寻找公共前缀的做法，很棒

代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
class Solution 
{
public:
    int rangeBitwiseAnd(int m, int n) 
    {
        int i = 0;
        while (m != n)
        {
            m = m >> 1;
            n = n >> 1;
            i++;
        }
        return m << i;
    }
};