date: 2020/02/03


基本概念


191位1的个数(简单)

https://leetcode-cn.com/problems/number-of-1-bits

移位计数


231二的幂(简单)

https://leetcode-cn.com/problems/power-of-two

二进制数只有一位为1,其余为0


338比特位计数(中等)

https://leetcode-cn.com/problems/counting-bits


"051N皇后(困难)

DFS中用位图记录状态减少内存开销

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#ocRrB


"037解数独(困难)

DFS中用位图记录状态减少内存开销

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#BeiRC


面试题56 数组中数字出现的次数I(中等)

两个数只出现一次,其他数出现两次

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

vector<int> singleNumbers(vector<int>& nums) {
    // 第一次遍历:得到t=a^b
    int t = 0;
    for(int i = 0; i < nums.size(); i++)
        t ^= nums[i];

    // 找到t中某一个位1,作为分组依据
    // 1. t=a^b某一位为1,说明a、b在这一位上是不同的,可以确保a、b分到不同组
    // 2. 相同数的二进制串必定是相同的,那么可以确保相同的数会被分到相同组
    int g;
    for(g = 1; (t & g) == 0; g <<= 1);

    // 第二次遍历:按照分组进行异或,得到a和b
    int t1 = 0, t2 = 0;
    for(int i = 0; i < nums.size(); i++){
        if(g & nums[i])
            t1 ^= nums[i];
        else
            t2 ^= nums[i];
    }
    vector<int> res = {t1, t2};
    return res;
}


面试题56 数组中数字出现的次数II(中等)

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof

一个数只出现一次,其他数出现三次

int singleNumber(vector<int>& nums) {
    // 位计数
    int count[31] = {0};
    for(int i = 0; i < nums.size(); i++){
        for(int j = 0; j < 31; j++){
            if(nums[i] & (1 << j))
                count[j]++;
        }
    }
    // 按位求模得到结果
    int res = 0;
    for(int i = 0; i < 31; i++){
        if(count[i] % 3)
            res += (1 << i);
    }
    return res;
}

计数过程可以用状态机优化并转化为更高效的位运算形式,具体可以参考题解 


面试题65 不用加减乘除做加法(简单)

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

异或实现不进位的求和,位与运算获得进位符

int add(int a, int b) {
    if(a == 0) return b;
    if(b == 0) return a;
    long c = (unsigned int)(a & b) << 1;  // 获取进位(强转为ui,因为c++中负数不能左移位)
    long s = a ^ b;         // 不进位求和(即异或)
    return add(s, c);
}
int add(int a, int b) {
    while(b != 0){
        int c = (unsigned int)(a & b) << 1;
        a ^= b;
        b = c;
    }
    return a;
}