Bitwise AND of Numbers Range——LeetCode
2024-10-10 17:39:48
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.
题目大意:给一个范围,返回这个范围中所有的数按位相与最后的结果。
解题思路:当拿到这个题目的时候,我是拒绝的,这么简单的题,直接与然后返回不就是了,然后发现范围太大会TLE,后来想范围里有一个数某位是0,其他的就不用判断了,肯定是0,然后写出来这个解法,
public int rangeBitwiseAnd(int m, int n) {
int res = 0;
int[] bits = new int[32];
Set<Integer> offset = new HashSet<>();
for (int i = 0; i < 32; i++) {
bits[i] = 1;
}
out:
for (int j = 0; j < 32; j++) {
for (int i = m; i <= n; i++) {
if (bits[j] == 0)
break;
if ((i & (1 << j)) == 0) {
bits[j] = 0;
offset.add(j);
}
if (offset.size() == 32 || i == Integer.MAX_VALUE) {
break out;
}
}
}
for (int i = 0; i < 32; i++) {
res += bits[i] << i;
}
return res;
}
结果还是TLE。
然后看了别人的解法,更巧妙,当m!=n,那么最末位必定等0,因为[m,n]必定包含奇偶数,相与最末位等0。当m=n的时候,后面都是0,前面的就是这个范围内的数按位相与的相同部分。
举例来说:m=4(0000 0100), n=6(0000 0110), 那么范围[4,6]中包含4、5、6,即0000 0100, 0000 0101, 0000 0110,所有的结果按位与得到0000 0100。
初始:m!=n,于是m,n分别右移一位得到0000 0010, 0000 0011,同时偏移量offset+1;
m!=n,于是m,n继续右移一位得到0000 0001, 0000 0001,同时偏移量offset+1;
m=n,得到结果m<<offset。
public int rangeBitwiseAnd(int m, int n) {
int res = 0;
int offset = 0;
while(m!=n){
m>>=1;
n>>=1;
offset++;
}
return m<<offset;
}
最新文章
- Java递归目录结构
- java .bat批处理(java cmd命令)
- 如何部署Icinga服务端
- gif显示
- PDF.NET 开发框架之 SOD框架 Ver 5.2 正式版开源源码发布
- Shader的语法
- 六月计划#2A(6.10-6.16)
- [有向图的强连通分量][Tarjan算法]
- 一个ios的各种组件、代码分类,供参考
- 基于无域故障转移群集 配置高可用SQLServer 2016数据库
- WINDOWS7环境下Informatica的安装[新手]
- vscode ";find all references"; 提示: no result found.
- Tomcat 下载安装与配置
- maven导出项目依赖的jar包
- 启动Tomcat服务时,出现org.apache.catalina.startup.VersionLoggerListener报错
- P1564 膜拜
- Syncthing -- 开源的云储存和同步服务工具
- 一个检测网页是否有日常链接的python脚本
- [转]solr系统query检索词特殊字符的处理
- [bzoj1024][SCOI2009]生日快乐 (枚举)
热门文章
- Meth | phpstorm invalid descendent file name
- [转] prerender-SPA程序的SEO优化策略
- Android开发系列(一)Activity与Fragment获取屏幕获取屏幕像素的不同方式
- android背景平铺方式 tileMode
- Directive Definition Object
- Swift - 18 - 数组的基础操作
- MySQL 删除数据库
- 如果使用的是orm,是否还需要关系索引
- 疯狂学习java web3(javaScript)
- [Python笔记]第二篇:运算符、基本数据类型