美文网首页
338. Counting Bits

338. Counting Bits

作者: a_void | 来源:发表于2016-09-18 10:56 被阅读0次

    Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

    Example: For num = 5 you should return [0,1,1,2,1,2].

    Idea: Find the pattern in this sequence

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> r = vector<int>();
            r.reserve(num+1);
            r.push_back(0); // non negative int
            if(num == 0) return r;
            r.push_back(1); 
            if(num == 1) return r;
            
            for(int p1=1,p2=2;r.size() <= num;p1*=2,p2*=2){
                for(int j=p1;j<p2 && r.size() <= num;j++) r.push_back(r[j]);
                for(int j=p1;j<p2 && r.size() <= num;j++) r.push_back(r[j] + 1);
            }
            return r;
        }
    };
    

    相关文章

      网友评论

          本文标题:338. Counting Bits

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