C++ count bits


  • 0
    B

    hard code all combinations would definitely fail the interview.

    instead of find all combinations of n bits, we can have a function to count the 1 bit in the number from 1 to 59, and store the result in array.

    class Solution {
    public:
        int getOne( int n)
        {
            int ans = 0;
            while(n > 0)
            {
                if(n%2 == 1) ans++;
                n = n >> 1;
            }
            return ans;
        }
    
        vector<string> readBinaryWatch(int num) {
            vector<vector<string>>hr(4, vector<string>());
            vector<vector<string>>mi(6, vector<string>());
            hr[0].push_back("0");
            mi[0].push_back("00");
            int i = 1;
            for(;i<60;i++)
            {
                int j = getOne(i);
                string s = to_string(i);
                if(i < 12) hr[j].push_back(s);
                if(s.length() == 1) s = "0" + s;
                mi[j].push_back(s);
            }
            
            vector<string> ans;
            for(int i = 0; i < 4; i++)
            {
                if(num-i < 0 || num-i > 5) continue;
                for(auto e : hr[i])
                    for(auto f : mi[num-i])
                        ans.push_back(e+":"+f);
            }
            return ans;
        }
    };

Log in to reply
 

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