原题

LintCode 706. Binary Time

Description

Given a watch with a binary display time and a non-negative integer n which represents the number of 1s on a given timetable, return all possible time.

Notice

• The order of output does not matter.
• The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
• The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

Example

Given n = 1
Return ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

代码

class Solution {
public:
    /*
    * @param : the number of "1"s on a given timetable
    * @return: all possible time
    */
    vector<string> binaryTime(int num) {
        // Write your code here
        vector<string> res;
        int number[60];
        for (int i = 0; i < 60; i++) {
            int count = 0;
            int num = i;
            while (num) {
                num &= (num - 1);
                count++;
            }
            number[i] = count;
        }
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (number[i] + number[j] == num) {
                    string hour = to_string(i);
                    string minute = to_string(j);
                    if (minute.length() == 1) minute = "0" + minute;
                    res.push_back(hour + ":" + minute);
                }
            }
        }
        return res;
    }
};