注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex201 Bitwise AND of Numbers Range  

2015-05-22 21:44:18|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题很有意思

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.

肯定要先观察m和n的特点,暴力and肯定过不去。后来确实让我发现规律了,对m和n取对数之后得到k1和k2,只有k1==k2情况下结果才不等于0,而且可以继续往下递推。比如 4(100)  和8(1000),他们中间有个1000,and的时候会把所有的数字都给变成0的,这个就是解题的关键。
见c++代码,

/*
* 解这道题目需要先观察一下m->n这些数字的构造
* 我们可以看到如果2^n的话,只有第n+1位才是1,
* 如果m->n之间有一个刚好是2对数的话,全部求and之后肯定是0
* 比如 4 100 和 8 1000,他们的对数值差1不在一个范围内
* 这样的话,我们就需要做一个循环 对m,n一直求对数,看看他们的k1和k2是否是相等的,如果相等的话
* 继续往后push 保存2^k1,这个后面要加起来的
* 否则一旦遇到m或者n变成0了的话,不用算了,肯定都是0了
* 这里我自己写了一个对数函数和一个指数函数,其实是没有必要的
* 要是自己写的话可能速度更快,落到c程序的区域里面去了。
*/
class Solution {
public:
vector<int>array;
int rangeBitwiseAnd(int m, int n) {
int k1,k2;
if (m == 0 || n == 0)
return 0;
k1 = myLog(m);
k2 = myLog(n);

int low = m,high = n;
// 当k1 == k2的时候才有结果
while (k2 == k1)
{
array.push_back(k1);
int tmp = myExp(k1);
low -= tmp;
high -= tmp;

//任意一个数为0的话就直接退出了,不用算了
if (low == 0 || high == 0)
break;

k1 = myLog(low);
k2 = myLog(high);
}
int len = array.size();
if (len <= 0)
{
return 0;
}
else
{
int sum = 0;
for (int i = 0; i < len; i++)
{
sum += myExp(array[i]);
}
return sum;
}
}
int myLog(int n)
{
int i = 0;
while (n >= 2)
{
n = n / 2;
i++;
}
return i;
}
int myExp(int n)
{
int i = 0;
int num = 1;
for (i = 0; i < n; i++)
{
num *= 2;
}

return num;
}
};



  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017