LeetCode-401-二进制手表

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。

每个 LED 代表一个 0 或 1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

案例:

输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Code

//time complexity O(2^n)
//space complexity(kn)
class Solution {
private:
    vector<string> res;
public:
    vector<string> readBinaryWatch(int num) {
        vector<int> bitList = { 1,2,4,8,1,2,4,8,16,32 };
        //0位置存储时，1位置存储分
        vector<int> record(2, 0);
        DFS(num, 0, bitList, record);
        return res;
    }

    void DFS(int num, int start, vector<int>& bitList, vector<int>& record) {
        if (num == 0) {
            //注意小时部分超过11，或者分钟部分超过59要剪枝
            if (record[0] > 11 || record[1] > 59)
                return;
            //c++11 to_string将数字转为字符形式
            res.push_back(to_string(record[0]) + ":" + (record[1] < 10 ? "0" + to_string(record[1]) : to_string(record[1])));
            return;
        }

        for (int i = start;i < bitList.size();i++) {
            if (i <= 3)
                record[0] += bitList[i];
            else
                record[1] += bitList[i];
            DFS(num - 1, i + 1, bitList, record);
            if (i <= 3)
                record[0] -= bitList[i];
            else
                record[1] -= bitList[i];

        }
    }
};