?前言?

开更五月集训专题，由浅入深，深入浅出，飞向大厂！

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?全文大约阅读时间： 20min

全文目录

?前言?
191. 位1的个数
461. 汉明距离
136. 只出现一次的数字
137. 只出现一次的数字 II
写在最后

191. 位1的个数

解题思路

有个有用的小结论，就是 $n\&(n-1)$ 就可以消除n的最低位的1，可以试一试，利用这个方法进行统计就好了。

代码

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
        while(n){
            ++ans;
            n &= (n-1);
        }
        return ans;
    }
};

注意的点

得统计，好像省不了了。。。

461. 汉明距离

解题思路

比上面的更进一步，用一用异或，简单来说就是同0异1，所以x^y就是不同的位置，统计一下就好了。

代码

class Solution {
public:
    int hammingDistance(int x, int y) {
        unsigned int tmp = x ^ y;
        int ans = 0;
        for(;tmp;++ans) tmp &= (tmp-1);
        return ans;
    }
};

注意的点

没啥注意的

136. 只出现一次的数字

解题思路

继续利用异或的性质，就可以得到最终的结果。两个相同的数字异或结果一定是全0，全0和任何数异或就是那个数本身，并且异或与顺序无关，就可以得到了。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto num : nums)    ans ^= num;
        return ans;
    }
};

注意的点

c++的auto真香，学着用用。

137. 只出现一次的数字 II

解题思路

根据每一位进行统计就好了。然后最终每一位的个数必然是3的倍数或者3的倍数余1

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> count(32);
        for(auto num : nums)
            for(int i = 0;i < 32;++i)
                if(num &((unsigned int)1 << i)) ++count[i];
        unsigned int ans = 0;
        for(int i = 0;i < 32;++i)
            if(count[i] % 3)  ans |= ((unsigned int)1 << i);
        return ans;
    
    }
};