东莞市建设规划局网站首页,辽宁自助网站建设价格,psd素材免费下载网站,免费企业网站制作文章目录一、求1的个数二、另类加法三、数组中出现一次的数字四、数组中出现一次的数字变形一、求1的个数
二进制中1的个数 法一#xff1a;逐位判断 根据与运算 n10#xff0c;说明n的最右边一位为0 n11#xff0c;说明n的最右边一位为1 所以思路就是…
文章目录一、求1的个数二、另类加法三、数组中出现一次的数字四、数组中出现一次的数字变形一、求1的个数
二进制中1的个数 法一逐位判断 根据与运算 n10说明n的最右边一位为0 n11说明n的最右边一位为1 所以思路就是将n右移再与1按位与 class Solution {
public:int hammingWeight(uint32_t n) {int count0;while(n){if((n1)1) count;nn1;}return count;}
};时间复杂度O(logn) 逐位判断需循环log2n次其中log2n代表数字n最高位1的所在位数例如log2 4 2,log2 16 4) 右移一位的操作相当于除2 空间复杂度O(1) 法二利用n(n-1)
class Solution {
public:int hammingWeight(uint32_t n) {int count0;while(n){nnn-1;count;}return count;}
};时间复杂度O(m) m为二进制中1的个数 空间复杂度O(1)
二、另类加法
不用加减号的加法 与同时为1才为1 异或相同为0相异为1
class Solution {
public:int add(int a, int b) {
//因为不允许用号所以求出异或部分和进位部分依然不能用 号所以只能循环到没有进位为止 while(b!0){
//保存进位值下次循环用int c(unsigned int)(ab)1;//C中负数不支持左移位因为结果是不定的
//保存不进位值下次循环用a^b;
//如果还有进位再循环如果没有则直接输出没有进位部分即可。bc; }return a;}
};/*
把ab转换成非进位和进位由于不能用加法因此要一直转换直到第二个加数变成0。
用递归的写法比循环更容易一下子看懂
*/
class Solution {public int add(int a, int b) {if (b 0) {return a;}// 转换成非进位和 进位return add(a ^ b, (a b) 1);}
};三、数组中出现一次的数字
传送门
class Solution {
public:vectorint singleNumbers(vectorint nums) {int res0;//相同取0相异取1因此0^00,0^11,0异或任何数都为本身可理解为没影响for (int n: nums) {res ^n;//假设两个只出现一次的数分别为a和b获得a异或b的结果}//找到ab第一个不相同的二进制位用位与操作两个都为1才为1其余为0因此可理解0和任何数相与都还是本身//理解位与就是0可以掩盖掉所有数字0遇0为0遇1还为0子网掩码//通过1的位置变化找出首个不一样的二进制位int m1;while((mres)0){//m000001当第一位不是1时结果为0则m左移一位000010类推直到找出m1;}//找到m以后用m划分数组两个相同的数字在m位一定相同即其与m位与的结果一定是相同的因此按mn0划分就一定能保证//1原来相同的元素还在一组//2不同的两个元素被分到了不同组int a0,b0;for (int n:nums) {if ((nm)0) a^n;else b^n;}return {a,b};}
};四、数组中出现一次的数字变形
传送门 法一哈西最简单的方法
class Solution {
public:int singleNumber(vectorint nums) {mapint,int m;for(auto e: nums){m[e];}for(auto e: m){if(e.second1) return e.first;}return 0;}
};法二位运算 7 : 0B0111 7 : 0B01117 : 0B0111^^^|||出现数 333 // 从上向下可以发现[3个7]每位都出次了 3 次那这样时再增加一个数。7 : 0B0111 7 : 0B01117 : 0B01114 : 0B0100^^^|||出现数 433 // 从上向下只有第 3位bit 出现了 4次%%%333 // 接下来把现各个位出现的次数按 3取余‖‖‖100 // 取余结果刚好100对应的就是4class Solution {
public:int singleNumber(vectorint nums) {int res 0;for (int i 0, sub 0; i 32; i, sub 0) {for (auto n : nums) sub ((n i) 1);if (sub % 3) res | (1 i);}return res;}
};
