网站加入百度广告联盟天津做网站好的公司

网站加入百度广告联盟,天津做网站好的公司,app市场调研报告,1688网站怎么做#x1f3ac; 胖咕噜的稞达鸭#xff1a;个人主页#x1f525; 个人专栏: 《数据结构》《C初阶高阶》 《Linux系统学习》 《算法日记》⛺️技术的杠杆#xff0c;撬动整个世界! #x1f425;位运算常见总结#xff1a; 本专题的前缀文章#xff1a; 算法日记专题#x… 胖咕噜的稞达鸭个人主页 个人专栏: 《数据结构》《C初阶高阶》《Linux系统学习》《算法日记》⛺️技术的杠杆撬动整个世界!位运算常见总结本专题的前缀文章算法日记专题位运算I汉明距离I II 面试题判断是不是唯一的字符 丢失的数字 两个整数相加只出现一次的数字I力扣链接算法原理:将数组中所有元素都异或在一起除了某个元素只出现一次以外其余每个元素均出现两次。最终异或的结果就是所求。classSolution{public:intsingleNumber(vectorintnums){intsum0;for(intnum:nums)sum^num;returnsum;}};只出现一次的数字II链接力扣算法原理位运算把数组中的数字都放在bit中有32个位0 和 1 指的是某个数字的二进制表示中的一位bit的值。3n个0 singel 0; -----取模 03n个0 singel 1; -----取模 13n个1 singel 0; -----取模 03n个1 singel 1; -----取模 1对于每一位 i统计数组中所有数字在该位为 1 的个数sum因为除了目标数字外其他数字都出现 3 次所以 sum 3×k bk 是出现 3 次的数字中该位为 1 的个数b 是目标数字在该位的值0 或 1sum % 3 b所以如果 b 0 → 目标数字该位为 0如果 b 1 → 目标数字该位为 1设置 ret 的该位为 1这样遍历完 32 位后ret 就是只出现一次的数字。classSolution{public:intsingleNumber(vectorintnums){intret0;//用于返回最后的结果for(inti0;i32;i)//修改ret中的值{intsum0;for(intx:nums)//遍历nums,计算nums中所有数字的第i位的和if(((xi)1)1)//此时第i位置的数字为1sum;sum%3;//所有出现在nums第0位的数字都加起来再取模3if(sum1)ret|(1i);//判断如果sum 最后取模等于1就说明这个数字单独出现过}returnret;}};只出现一次的数字III只出现一次的数字力扣链接解题原理所有数异或一个数组中只有两个数字只出现了一次其余都出现了两次先将数组中所有的数字都进行异或最后剩下的一个数字就是唯一出现一次的这两个数字的异或和分组找不同找出不同的才可以分组那干脆去找异或和中的最低位置的1先找出这个异或和最低位置的1定义为diff(一定有1存在)找出这个1所在的编号如果这个编号跟1按位与最终结果就是1再跟数组中的其他数字异或最后可以找出来这个数这个编号跟0按位与最终结果就是0再跟数组中的其他数字异或最后可以找出另外一个数字最后返回这两个数字。classSolution{public:vectorintsingleNumber(vectorintnums){inttmp0;for(inti:nums)tmp^i;//tmp中存储异或和unsignedintdiff(unsignedint)tmp-(unsignedint)tmp;inta0,b0;for(intnum:nums){if(diffnum)a^num;elseb^num;}return{a,b};}};面试题消失的两个数字消失的两个数字力扣链接解法数组中本身有nums个数字这些数字加上消失的两个数字a,b恰好是1~N中连续的数字区间所以nums中数字缺失数组 这段区间完整数组 —构成问题只出现一次的数字III关键其余数字都出现了两次只有a和b出现了一次返回a 和 b.解题可以将所有的数字异或在一起将结果收集在tmp中tmp a^ b;找到tmp中比特位为1的那一位异或的时候相同为0相异为1根据x位的不同划分为两类异或将这个x位置比特位为1的数字将其其余的数字都跟1异或在一起假设是b类将这个x位置比特位为0的数字将其其余的数字都跟0异或在一起假设是a类注意这个其余的数字既要在完整数组中进行异或操作也要在缺失数组中进行异或。其余数字都出现过两次只有其中一位数字只出现了一次classSolution{public:vectorintmissingTwo(vectorintnums){inttmp0;for(inti1;inums.size()2;i)tmp^i;for(intnum:nums)tmp^num;//找出ab比特位中不同的那一位intdiff0;while(1){if(((tmpdiff)1)1)break;elsediff;}//根据diff的不同将所有的数字都划分为两类来进行异或inta0,b0;for(intnum:nums)if(((numdiff)1)1)b^num;elsea^num;for(inti1;inums.size()2;i)if(((idiff)1)1)b^i;elsea^i;return{a,b};}};方法二位运算取最低位次的1classSolution{public:vectorintmissingTwo(vectorintnums){intsum0;for(inti1;inums.size()2;i)sum^i;for(intnum:nums)sum^num;intlowbitsum-sum;//取出最低位置的1在哪一位如果是倒数第二位就是2倒数第三位就是3是一个编号inta0,b0;for(inti1;inums.size()2;i){if(ilowbit)a^i;//判断这个位置的数字和i按位与如果i是0按位与的结果是0;elseb^i;//如果按位与的结果是1最终要按照lowbit算取编号}for(intnum:nums){if(numlowbit)a^num;elseb^num;}return{a,b};}};比特位计数比特位计数力扣链接题目解析对于0 i n中的每个i计算其二进制表示中1的个数返回一个长度为n 1的数组ans作为答案。思路找出0 i n中每一个数字二进制表示中总共有几个1数组中表示的是每一个i位有几个1将每一个数字放到位图中,每一位为1sum ,一个数字放好到位图中之后返回sum。ret[x]中收集每一个countBit中返回的sum个数sum用来计数字1.classSolution{public:vectorintcountBits(intn){vectorintret(n1);//用于返回最终结果的ret有n1个空间第n个数字二进制中有几个1也要返回autocountBit[](intx){intsum0;for(inti0;i32;i){if((xi)1)sum;//将x右移动i位并且按位与1判断它的第i个位置是1还是0如果是1就sum}returnsum;//返回这个数字的二进制数有多少个1};//多次调用countBit(x) 函数计算 x 的二进制中 1 的个数for(intx0;xn;x){ret[x]countBit(x);//将结果存储在数组 ret 的第 x 个位置}returnret;}};通过这道题我们可以总结出x i) 1的操作适用于以下情景判断n的第i位是0还是1if((ni)1)统计二进制中1的个数intcountBits(intx){intsum0;for(inti0;i32;i){if((xi)1)sum;//x不断右移动i个位置跟1按位与}returnsum;}示例int x 13; // 二进制1101int sum 0;int i 0;// 检查第0位if((13 0) 1) sum; // (1101 1) 1sum变为1// 检查第1位if((13 1) 1) sum; // (0110 1) 0sum不变// 检查第2位if((13 2) 1) sum; // (0011 1) 1sum变为2// 检查第3位if((13 3) 1) sum; // (0001 1) 1sum变为3所以13的二进制表达中有3个1.