搭建网站需要什么,凯里门户网,竞价单页系统,合肥网站设java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 异或统计1的个数2. 位移操作处理3. Brian Kernighan算法 位运…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 异或统计1的个数2. 位移操作处理3. Brian Kernighan算法 位运算https://blog.csdn.net/grd_java/article/details/136119268
1. 异或统计1的个数
解题思路时间复杂度O( 1 1 1)或者32反正最多就是每个二进制为查一下空间复杂度O( 1 1 1) 异或操作两数相同异或为0两数不相同异或为1我们异或x和y后统计结果二进制中1的数量即可 代码 使用编程语言自带的计算二进制表达式中1的个数的函数 class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);//统计x异或y后1的个数}
}2. 位移操作处理
解题思路时间复杂度O( l o g 2 C log_2C log2C)C是数据范围最多31表示二进制的位数空间复杂度O( 1 1 1) 法一是调用函数来统计1的个数如果不能用函数呢我们自己如何实现相同效果 代码 通过位移操作不断取x和y的最低位进行比较如果不一样就统计 class Solution {public int hammingDistance(int x, int y) {int ans 0;//计数while(x!0 || y!0){//只要x或y都不是全0就继续ans (x 1) ! (y 1)? 1 : 0;//x和y都取最低位如果不一样ans1否则ans0x 1;//统计最低位后右移一位将最低位移走下一次比较最低位的高位y y1;}//下面代码是上面代码的简化版
// for(int i 0;i32;i){//题目规定每个二进制有32位
// int i1 x i 1;//让当前为移到最低位后通过1操作取出
// int i2 y i 1;
// if (i1!i2) ans;//如果取出的最低位不一样就ans1
// }return ans;}
}异或后通过位移操作统计1的个数。上面第二种实现方式同时位移x和y这里直接计算x^y后统计1的个数即可 class Solution {public int hammingDistance(int x, int y) {int ans 0;//计数int i x ^ y;//异或不同位会置为1while(i!0){//只要还有1就继续ans i1;//取最低位是1就ans1否则ans0i1;//右移一位将当前已经处理的最低位抛弃}return ans;}
}3. Brian Kernighan算法
解题思路时间复杂度O( l o g 2 C log_2C log2C)C是数据范围最多31表示二进制的位数空间复杂度O( 1 1 1) x异或y后我们需要统计1的个数但是如果异或结果为100000000001.我们使用法2需要对所有位进行处理虽然我们一眼看到只有两个1但是法二依然需要将所有的位数都处理一遍我们如何跳过中间的0直接统计1的个数呢让上面这一串只循环右移2次针对这个问题BK算法出现了他利用了二进制的特性实现一次性删除最右侧的1的效果 对于十进制来说我们做减法时低位不够减需要向高位借1拿过来就是10二进制也一样不够减就得借1.拿过来就是2也就是说如果对2进制串进行-1操作的话最低位是1还好可以直接减去如果不够减就必须一直向高位借直到遇到一个够借1的。这样就会将2进制串中最后一个1借掉例如上图中x 10001000-1后最后一个1被借了变成10000111此时将这两个二进制串进行与运算就会实现将最后一个1去掉的效果 我们能够这样用BK算法搞几次就说明这个二进制串有几个1.直到其为0为止 代码 class Solution {public int hammingDistance(int x, int y) {int ans 0;//计数int i x ^ y;while(i!0){i (i-1);//取最后面的1ans;//取一次加一次1出现次数}return ans;}
}
