leetcode 401. Binary Watch 一个十分经典的DFS深度优先遍历的做法 + C++的bitset的很不错使用案例

矫情吗；* 2022-06-04 07:26 161阅读 0赞

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.

For example, the above binary watch reads “3:25”.

![这里写图片描述][SouthEast]

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

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”\]  
Note:  
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”.

这道题最经典的做法就是DFS深度优先遍历的做法，我最初的想法是把时钟和分钟去分开设置，后来发现这个太麻烦了，不如按照统一处理，然后在最后做一个筛选即可，

**第一个方法是网上看的一个十分漂亮的做法，直接遍历所有的可能，也很漂亮**

第二个方法是我写的DFS深度优先遍历，

个人强烈建议使用第一种暴力解法，十分的简介漂亮

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <bitset>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<string> res;
    
        vector<string> readBinaryWatch(int num) 
        {
            for (int h = 0; h < 12; h++)
            {
                for (int m = 0; m < 60; m++)
                {
                    if (bitset<10>(h << 6 | m).count() == num)
                        res.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));
                }
            }
            return res;
        }
    
    
    
        //这是一个十分简单的DFS深度优先遍历的应用
        vector<string> readBinaryWatchByDFS(int num) 
        {
            vector<int> all(10, 0);
            getAll(0,num,num,all);
            return res;
        }
    
        void getAll(int begin,int k,int num, vector<int>& all)
        {
            if (k == 0)
            {
                int h = 0, m = 0;
                int a = 1;
                for (int i = 0; i < 4; i++)
                {
                    h = h + all[i] * a;
                    a *= 2;
                }
                a = 1;
                for (int i = 4; i < 10; i++)
                {
                    m = m + all[i] * a;
                    a *= 2;
                }
    
                if (h >= 0 && h <= 11 && m >= 0 && m <= 59)
                {
                    string one = to_string(h) + ":";
                    one = one + (m < 10 ? "0" + to_string(m) : to_string(m));
                    res.push_back(one);
                }
            }
            else if (begin >= all.size())
                return;
            else
            {
                //不设置当前Index
                getAll(begin + 1, k, num, all);
    
                //设置当前Index
                all[begin] = 1;
                getAll(begin +1,k - 1,num, all);
                all[begin] = 0;
            }
        }
    };

[SouthEast]: /images/20220604/de6be2fdda8d4dbb844850ff01d087b1.png