医院设计网站建设,网站模板破解版,苏州建设档案馆官方网站,南昌seo营销文章目录 Tag题目来源题目解读解题思路方法一#xff1a;公共前缀方法二#xff1a;n (n-1) 写在最后 Tag
【位运算】 题目来源
201. 数字范围按位与 题目解读
计算给定区间内所有整数的按位与的结果。 解题思路
本题朴素的方法是直接将区间内的所有整数按位与公共前缀方法二n (n-1) 写在最后 Tag
【位运算】 题目来源
201. 数字范围按位与 题目解读
计算给定区间内所有整数的按位与的结果。 解题思路
本题朴素的方法是直接将区间内的所有整数按位与时间复杂度为 O ( n ) O(n) O(n)数据量已经达到 1 0 1 0 10^10 1010必然超时。接下来介绍两种不会超时的方法。
方法一公共前缀
先来说说什么是公共前缀公共前缀指的是所有需要按位与计算的数对应的二进制数从高位到低位公共的二进制字符。比如 [9, 12] 的公共前缀为 0000 1解释如图所示 根据上图我们发现连续数字按位与的值等于公共前缀后面再补上剩余的 0。 这个规律正确吗我们来证明一下。假设对于连续区间内所有数的二进制数前 i 位从高位开始数均相同第 i1 位开始不同由于区间 [m, n] 连续所以区间内从小到大先枚举出来的数的第 i1 位为 0枚举出来相对靠后数的第 i1 位全部为 1。 并且一定存在连续的两个数 x 和 x1 满足 x 的第 i1 位为 0后面全为 1x1 的第 i1 位为 1后面全为 0对应上图中的例子即为 11 和 12。这种形如 0111… 和 1000… 的二进制串的按位与的结果一定为 0000…因此第 i1 位开始的剩余位均为 0前 i 位由于均相同因此按位与结果不变。最后的答案即为二进制字符串的公共前缀再用零补上后面的剩余位。
实现代码
class Solution {
public:int rangeBitwiseAnd(int left, int right) {int res 0;for (int i 0; i 32; i) {for (int num left; num right; num) {res | num 1;num 1;}}return res;}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn) n n n 为 right 的值、
空间复杂度 O ( 1 ) O(1) O(1)。
方法二n (n-1)
根据方法一我们知道需要保留的是区间 [m, n] 中的公共前缀也就是去掉非公共前缀的部分我们可以使用 n (n-1) 来去除直到 m n最后返回 n 即可。于是有代码
实现代码
class Solution {
public:int rangeBitwiseAnd(int m, int n) {while (m n) {n (n-1);}return n;}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn) n n n 为 right 的值、
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
