【LeetCode】338. 比特位计数

题目链接:https://leetcode-cn.com/problems/counting-bits/

本题使用动态规划

根据二进制的规则,满二进一,因此,如果一个数的是二的次方数,那么该数的二进制中,1的个数一定为1

根据位运算的相关规则,在程序中将一个数左移一位,相当于将该数乘以2,由于左移一位会补0,因此二进制中1的个数不变。所以如果这个数是偶数,那么其二进制中1的个数就等于【该数/2】的二进制中1的个数。(位运算相关知识整理)

如果该数是奇数,那么其二进制中1的个数就等于【该数-1】的二进制中1的个数 + 1,因为奇数的二进制,末尾一定是1,所以,一定是【该数-1】(偶数)加一得到。

设置dp(i):i的二进制中1的个数

状态转移方程

[dp(i) = 1 2^k=i, k = 0,1,2,3,4,5...... ]

[dp(i) = dp(i/2) i 为偶数 ]

[dp(i) = dp(i-1) + 1 i为奇数 ]

代码(C++)

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ans ;
        ans.push_back(0) ;
        if (num == 0) {
            return ans ;
        }
        ans.push_back(1) ;
        if (num == 1) {
            return ans ;
        }
        int mask = 2 ;
        for (int i = 2;i <= num;i++) {
            // 判断是否为2的次方
            if (i == mask << 1) {
                ans.push_back(1) ;
                mask <<= 1 ;
            } else {
                // 判断奇偶性
                if ((i & 1) == 0) {
                    ans.push_back(ans[i >> 1]) ;
                } else {
                    ans.push_back(ans[i - 1] + 1) ;
                }
            }
        }
        return ans ;
    }
};

【LeetCode】338. 比特位计数

原文地址:https://www.cnblogs.com/Suans/p/14473457.html