美文网首页动态规划动态规划
[DP]LeetCode338. Counting Bits

[DP]LeetCode338. Counting Bits

作者: wshxj123 | 来源:发表于2017-07-13 11:16 被阅读23次

    使用dp思想,dp[n] = dp[n /2] (最后一位是0)或者 dp[n /2] + 1(最后一位是1)

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> result;
            if(num >= 0)
                result.push_back(0);
            if(num >= 1)
                result.push_back(1);
            if(num >= 2) {
                for(int i = 2; i <= num; i++) {
                    int onetimes = i % 2 == 0 ? result[i / 2] : result[i / 2] + 1;
                    result.push_back(onetimes);
                }
            }
            
            return result;
        }
    };
    

    相关文章

      网友评论

        本文标题:[DP]LeetCode338. Counting Bits

        本文链接:https://www.haomeiwen.com/subject/scrwhxtx.html