海外手表网站,wordpress有商城吗,用什么工具做网站视图,室内设计有限公司java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 位运算#xff1a;取出非前导0位标1#xff0c;进行异或2. …java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 位运算取出非前导0位标1进行异或2. 笨办法 1. 位运算取出非前导0位标1进行异或 因为这道题考察的就是求十进制整数的有效数值位反码问题不是原码补码反码那个反码。而是1变0,0变1那个反码各大编程语言源码实现此功能的经典方法就是这个方法所以推荐直接理解这个方法。另外还有一道题1009. 十进制整数的反码也是和这道题完全一样的考题。 解题思路时间复杂度O( l o g 2 l o g 2 n u m log_2{log_2{num}} log2log2num)空间复杂度O( 1 1 1) 对整数num的二进制不操作前导0全部取反就是num的补数例如5的二进制0000 0000 0000 0000 0000 0000 0000 0101红色的0都是前导0求补数时是不需要取反的。5的补数0000 0000 0000 0000 0000 0000 0000 0010只有黄色的非前导0部分才进行取反如果只对010操作的话我们只需要让其每一位和1异或就可以取反例如101 ^ 111 010但是计算机中5的二进制是0000 0000 0000 0000 0000 0000 0000 0101。如果异或1111 1111 1111 1111 1111 1111 1111 1111,会得到1111 1111 1111 1111 1111 1111 1111 1010,这样的话答案就错了如何解决这个问题呢如果我们能让5的二进制只异或0000 0000 0000 0000 0000 0000 0000 0111的话就可以得到5的补数0000 0000 0000 0000 0000 0000 0000 0010 所以对于一个数num 0000 0000 0000 0000 0000 0000 0000 0101如何能找出只有黄色部分全1红色部分全0的二进制串t 0000 0000 0000 0000 0000 0000 0000 0111就是破题的关键 而针对这个问题有个很简单的操作方式就是通过位移操作和或操作配合对1,2,4,8,16,…的右移结果相或就可以抛弃前导0对其余位全部填充1.案例如下下面的案例是针对32位的int型所以只需要右移到16.如果是64位的long型需要右移到32依此类推。 /** 将num中非前导0的地方都填充为1 **/
//tnum: 0100 0000 0000 0000 0000 0000 0000 0101
//t1 0010 0000 0000 0000 0000 0000 0000 0010
//tt|t1 0110 0000 0000 0000 0000 0000 0000 0111
//t2 0001 1000 0000 0000 0000 0000 0000 0001
//tt|t2 0111 1000 0000 0000 0000 0000 0000 0111
//t4 0000 0111 1000 0000 0000 0000 0000 0000
//tt|t4 0111 1111 1000 0000 0000 0000 0000 0111
//t8 0000 0000 0111 1111 1000 0000 0000 0000
//tt|t8 0111 1111 1111 1111 1000 0000 0000 0111
//t16 0000 0000 0000 0000 0111 1111 1111 1111
//tt|t16 0111 1111 1111 1111 1111 1111 1111 1111
int t num;
t t | (t 1);
t | t 2;
t | t 4;
t | t 8;
t | t 16;有了这个然后再进行异或操作就完成了这道题目 代码 class Solution {public int findComplement(int num) {/** 将num中非前导0的地方都填充为1 **///tnum: 0100 0000 0000 0000 0000 0000 0000 0101//t1 0010 0000 0000 0000 0000 0000 0000 0010//tt|t1 0110 0000 0000 0000 0000 0000 0000 0111//t2 0001 1000 0000 0000 0000 0000 0000 0001//tt|t2 0111 1000 0000 0000 0000 0000 0000 0111//t4 0000 0111 1000 0000 0000 0000 0000 0000//tt|t4 0111 1111 1000 0000 0000 0000 0000 0111//t8 0000 0000 0111 1111 1000 0000 0000 0000//tt|t8 0111 1111 1111 1111 1000 0000 0000 0111//t16 0000 0000 0000 0000 0111 1111 1111 1111//tt|t16 0111 1111 1111 1111 1111 1111 1111 1111int t num;t t | (t 1);t | t 2;t | t 4;t | t 8;t | t 16;//num: 0100 0000 0000 0000 0000 0000 0000 0101//t: 0111 1111 1111 1111 1111 1111 1111 1111//num ^ t 0011 1111 1111 1111 1111 1111 1111 1010return num ^ t;}
}2. 笨办法
解题思路时间复杂度O( l o g 2 n u m log_2 num log2num)空间复杂度O( 1 1 1) 用循环位移操作找到最高位的1属于暴力找位置的笨办法也是Leetcode官方题解给出的方法毕竟是官方解法需要同时照顾老手和新手推荐学有余力的同学直接掌握方法1。因为这个方法2会有溢出的风险。而方法1是各大编程语言源码中也使用的方法。然后通过-1操作生成除了前导0全是1的二进制串其思路和法1一样但是需要自己循环找最高位然后通过-1操作得到目标二进制串。具体看代码注释 代码 class Solution {public int findComplement(int num) {int highbit 0;//找到比num最高位高的第一位。例如num 0101的最高为是2位置的[3位置2位置1位置0位置], highbit 1000的1的位置为3位置正好比num的最高位高一位//找这个比num最高位的1高一位的1for (int i 1; i 30; i) {if (num (1 i)) {//如果num还是比highbit大说明没找到继续找highbit i;} else {//如果num比highbit小break;//找到了跳出循环} }//对highbit位进行 - 1找到全是1的低位。例如二进制1000 - 1 0111//但是如果highbit正好30位则会进行溢出。直接赋值0111 1111 1111 1111 1111 1111 1111 1111//如果小于30位我们就获取其二进制然后-1.int mask highbit 30 ? 0x7fffffff : (1 (highbit 1)) - 1;return num ^ mask;//最后进行异或操作}
}
