2020-03-08 刷题5（位运算，动态规划）

191 位1的个数

标签：位运算
最简单的逐位统计法：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n > 0){
            cnt += n % 2;
            n = n >> 1;
        }
        return cnt;
    }
};

这种做法需要循环n的有效位数遍，即使在中间有0，也会占用一次循环。

一个更加tricky的做法，是利用n和n-1的性质，因为n最低位的1，对应到n-1一定是0，所以n&n-1 就可以把n最低位的1消去。重复数次，n就可以变成0.这种做法循环的次数等于n中1的位数，平均情况下，比第一种做法要好一些。

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

我发现我写代码越来越简洁了哈～～～～～

---

461 汉明距离

标签：位运算
这个题就是上一题的增强版，多了一步计算两个数异或的操作。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int dis = 0;
        x = x ^ y;
        while(x){
            dis++;
            x = x & (x - 1);
        }
        return dis;
    }
};

---

322 零钱兑换

这是个很典型的动态规划问题，当金额为n时，

dp(n) = min(dp(n - c_k)) + 1.
dp(0) = 0.

递推公式很好想，但是代码不好写，采用递归的做法，递归太深时占用栈空间过多，而且会有很多重复计算。所以采用迭代的写法，自底向上依次计算。

两层循环是肯定的，一层循环次数为金额，另一层为硬币种类，第一种做法是将金额设为外层循环，硬币种类为内层循环，内层循环停止条件受外层金额影响；第二种做法是将硬币种类为外层循环，金额为内层循环，内层循环起始条件受外层硬币面值影响。两种做法都可以保证唯一性。这里采用第二种做法。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount){
        int *dp = new int[amount+1];
        for(int i = 1; i <= amount; i++)
            *(dp + i) = INT_MAX;
        *dp = 0;
        for(int i = 0; i < coins.size(); i++){
            for(int j = coins[i]; j < amount + 1; j++){
                if(*(dp + j - coins[i]) < *(dp + j) - 1){
                    *(dp + j) = *(dp + j - coins[i]) + 1;
                }
            }
        }
        if(*(dp + amount) != INT_MAX) return *(dp + amount);
        return -1;
    }
};

时间复杂度：O(MN), 空间复杂度：O(M)
M是总金额，N为硬币种类。

---

190 颠倒二进制位

标签：位运算
采用逐位左移的操作，最低位左移31位放到最高位，然后n整体右移一位后当前最低位左移30位，依次操作直到n变为0.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int ans = 0;
        for(int i = 31; i >=0; i--){
            ans += (n & 1) << i;
            n = n >> 1;
            if(n == 0) break;
        }
        return ans;
    }
};

---

268 缺失的数字

标签：位运算
这个题目其实跟之前做过的重复数字是一样的道理，利用了自己异或自己为0。先从0到n异或一遍，然后把数组里的数字依次异或一遍，最后得到的就是只异或过一次，也就是缺失的那个数字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = 0;
        for(int i = 0; i <= nums.size(); i++){
            n = n ^ i;
        }
        for(int i = 0; i <  nums.size(); i++){
            n = n ^ nums[i];
        }
        return n;
    }
};