营销型网站建设效果,企业建设H5响应式网站的5大好处,商贸公司经营范围,科技侠智能锁Every day a Leetcode
题目来源#xff1a;201. 数字范围按位与
最直观的解决方案就是迭代范围内的每个数字#xff0c;依次执行按位与运算#xff0c;得到最终的结果#xff0c;但此方法在 [left, right] 范围较大的测试用例中会因超出时间限制而无法通过#xff0c;因…Every day a Leetcode
题目来源201. 数字范围按位与
最直观的解决方案就是迭代范围内的每个数字依次执行按位与运算得到最终的结果但此方法在 [left, right] 范围较大的测试用例中会因超出时间限制而无法通过因此我们需要另寻他路。
我们观察按位与运算的性质。对于一系列的位只要有一个零值的位那么这一系列位的按位与运算结果都将为零。
对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。
这个结果实际上是这些数的二进制表示的最长公共前缀后面补零。
解法1位移
鉴于上述问题的陈述我们的目的是求出两个给定数字的二进制字符串的公共前缀这里给出的第一个方法是采用位移操作。
我们的想法是将两个数字不断向右移动直到数字相等即数字被缩减为它们的公共前缀。然后通过将公共前缀向左移动将零添加到公共前缀的右边以获得最终结果。
代码
/** lc appleetcode.cn id201 langcpp** [201] 数字范围按位与*/// lc codestart
class Solution
{
public:int rangeBitwiseAnd(int left, int right){int shift 0;// 找到公共前缀while (left right){left 1;right 1;shift;}return left shift;}
};
// lc codeend结果 复杂度分析
时间复杂度O(log(right))算法的时间复杂度取决于 left 和 right 的二进制位数由于 right 更大因此时间复杂度取决于 right 的二进制位数。
空间复杂度O(1)。我们只需要常数空间存放若干变量。
解法2Brian Kernighan 算法
还有一个位移相关的算法叫做「Brian Kernighan 算法」它用于清除二进制串中最右边的 1。
「Brian Kernighan 算法」的关键在于我们每次对 number 和 number − 1 之间进行按位与运算后number 中最右边的 1 会被抹去变成 0。
基于上述技巧我们可以用它来计算两个二进制字符串的公共前缀。
其思想是对于给定的范围 [left, right]我们可以对数字 right 迭代地应用上述技巧清除最右边的 1直到它小于或等于 left此时非公共前缀部分的 1 均被消去。因此最后我们返回 right 即可。
代码
class Solution
{
public:int rangeBitwiseAnd(int left, int right){while (left right){// 抹去最右边的 1right right (right - 1);}return right;}
};结果 复杂度分析
时间复杂度O(log(right))和位移方法类似算法的时间复杂度取决于 left 和 right 二进制展开的位数。尽管和位移方法具有相同的渐近复杂度但「Brian Kernighan 算法」需要的迭代次数会更少因为它跳过了两个数字之间的所有零位。
空间复杂度O(1)。我们只需要常数空间存放若干变量。
