C++, intuitive dp sln


  • 0
    L
    class Solution {
    public:
    vector<int> countBits(int num) 
    {
        // validate input
        vector<int> rs(num+1,0);
        rs[0] = 0;
        rs[1] = 1;
        if(num<=1) return rs;
        
        // T={2^31-1,2^30-1,.....,2^1-1};
        vector<int> T;
        for(int i = 31; i>=1; i--)
        {
            T.push_back(pow(2,i)-1);
        }
        
        // dp
        for(int i = 2; i<=num; i++)
        {
    
            int j = 0;
            // set the left most non-zero bit of i to 0 to acquire j
            for(int k = 0; k<T.size(); k++)
            {
                if(i>T[k])
                {
                    j = i&T[k];
                    break;
                }
            }
            // the number of 1s in num i equals to 1 + the number of 1s in num j
            // e.g. i = 1101, then j = 0101, thus rs[i] = 1 + rs[j]. we already solved
            // subproblem rs[j] in previous calculation (dp).
            rs[i] = 1 + rs[j];
        }
        return rs;
    }
    

    short explanation:
    For a number i = 1101, we calculate the numbers of 1s in it (rs[i]) by checking our previous calculation result rs[j] ( j= 0101, j is calculated by setting the left most non-zero bit of i to 0: [1]101 to [0]101) and +1 to that result (rs[i] = 1 + rs[j]) . Then we calculate the whole rs with initialization rs[0] = 0, and rs[1] = 1 bottom up.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.