[leetcode]: 401. Binary Watch

淡淡的烟草味﹌ 2022-06-15 03:26 160阅读 0赞

# 1.题目 #

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.  
![这里写图片描述][Binary_clock_samui_moon.jpg]  
Example:

Input: n = 1  
Return: \[“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”\]

# 2.分析 #

有两种方法  
方法一：  
先确定小时和分钟各有多少个1，再求和计算小时和分钟。  
做排列组合求和，小时有x个1，分钟有n-x个1。然后每个1出现在哪一位做排列组合。  
方法二：  
反向思考。  
先确定小时和分钟的数字，再判断是否满足bit为1的位数为n。  
小时0-11，分钟0-59.两个for循环嵌套遍历，计算当前循环的数字bit为1的数目，如果总数刚好是n则为一个符合要求的时间。

# 3.代码 #

方法1，排列组合

vector<string> readBinaryWatch(int num,int m) {
        vector<int> hour = { 1,2,4,8 };
        vector<int> minute = { 1,2,4,8,16,32 };
        vector<string> ans;
        for (int i = 0; i <= num; i++) {
            unordered_set<int> hours = generateTime(hour, i);
            unordered_set<int> minutes = generateTime(minute, num - i);
            for (int h : hours) {
                if (h < 12) {
                    for (int m : minutes) {
                        if (m < 60)
                            ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));
                    }
                }
            }
        }
    }
    unordered_set<int> generateTime(vector<int> base, int count) {
        unordered_set<int> times;
        permutate(base, count, 0, 0, times);
        return times;
    }
    void permutate(vector<int> base, int count, int pos, int sum, unordered_set<int>& times) {
        if (count == 0) {
            times.insert(sum);
            return;
        }
        for (int i = pos; i < base.size(); i++)
            permutate(base, count - 1, i + 1, sum + base[i], times);
    }

方法2，数bit为1的位数

int bitcount(int n) {
        int count = 0;
        while (n) {
            n = n&(n - 1);
            ++count;
        }
        return count;
    }
    vector<string> readBinaryWatch(int num) {
        vector<string> ans;
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (bitcount(i*64 + j) == num)
                    ans.push_back(to_string(i) + (j < 10 ? ":0" : ":") + to_string(j));
            }
        }
        return ans;
    }

[Binary_clock_samui_moon.jpg]: https://upload.wikimedia.org/wikipedia/commons/8/8b/Binary_clock_samui_moon.jpg