模板网站会员_科技英语_百度的营销策略_今日头条新闻推荐

这里是题目“201. 数字范围按位与”的 Java 解决方案：

class Solution {public int rangeBitwiseAnd(int left, int right) {int shift = 0;// 找到公共前缀while (left < right) {left >>= 1;right >>= 1;shift++;}// 将公共前缀左移回去return left << shift;}
}

解题思路：

1. 观察按位与的特点：

   • 当某一位在区间内可能出现0时，按位与结果的这一位必然是0。
   • 因此，我们只需要找到left和right的公共前缀（必然是区间内所有数的公共前缀）。

2. 如何找到公共前缀：

   • 不断将left和right右移，直到两者相等（意味着找到公共前缀）。
   • 记录右移的次数shift。

3. 还原结果：

   • 将找到的公共前缀左移shift次，就得到了最终结果。

示例：

• 示例1: 输入 left = 5, right = 7

  • 二进制表示：
    • 5 -> 101
    • 6 -> 110
    • 7 -> 111
  • 找到公共前缀为 100（十进制4），结果为 4。

• 示例2: 输入 left = 0, right = 0

  • 直接返回 0。

• 示例3: 输入 left = 1, right = 2147483647

  • 因为从1到2147483647覆盖了所有可能的位，最终结果是 0。

该算法的时间复杂度为 $\text{O}(\log (\text{right}))$，因为右移操作的次数与right的二进制长度成正比。

之所以只需要考虑 left 和 right 的公共前缀，而不是区间内所有数的公共前缀，是因为它已经代表了区间 [left, right] 中所有数字高位上都一致的部分，就相当于也是区间内所有数的公共前缀。

java 实现

class Solution {public int rangeBitwiseAnd(int left, int right) {int shift = 0; //用于记录找到公共前缀所用的右移次数while(left < right) {left = left >> 1;right = right >> 1;shift++;}return left << shift;}
}