2020-03-08 刷题5(位运算,动态规划)

2020-03-09  本文已影响0人  nowherespyfly

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;
    }
};
上一篇下一篇

猜你喜欢

热点阅读