LeetCode #401: Binary Watch

Problem

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 Watch

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

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:

1. The order of output does not matter.
2. The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
3. 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".

题意

如图所示，有一块Binary Watch，小时用{8, 4, 2, 1}四个数码灯的亮和灭来指示，分钟用{32, 16, 8, 4, 2, 1}六个数码灯的亮和灭来指示。
上图中，小时位置，1和2亮着，所以小时是3(= 1 + 2)；分钟位置，16、8、1亮着，所以分钟是25(= 16 + 8 + 1)，所示时间是3:25.
问题的输入是亮灯的个数，要求计算出所有可能的时间。

分析

本题被放在了回溯问题分类下面，自然考虑用回溯的思想来解决这个问题。
对于本题而言，每个灯有两种状态（亮和灭），对应在回溯法里就是两个分支。亮的时候，当前灯代表的数字就应该被加在当前的小时/分钟总数上；而当前灯代表的数字是跟递归的深度有关的，可以在递归函数中增加一个指示深度的参数来实现这一点。
而问题又被分为了两个部分，小时和分钟是分开计算的，这就得出了两种可能的解法：

1. 只维护一棵递归树，从小时或分钟任意一部分的最低位开始递归；同时我们又要求小时和分钟分开计算，可以借助当前深度来判断现在应该计算小时还是分钟。这里给出一个函数头，具体的实现就不展开了。

void _foo(int curHour, int curMin, int depth);

2. 对小时和分钟分别维护一棵递归树，两棵递归树的最大高度和恒等于亮灯的总位数，这样比较方便操作。笔者下面贴出的第一份代码就实现了这个思路。

非回溯解法

该解法是笔者在写完回溯解法后，在该题的Solution中受大神的启发，通过计算某个时间的亮灯位数是否和当前给定的亮灯位数匹配，来判断该时间是否是一个解，这里也贴上自己实现的代码。

Code

两棵递归树

//Runtime: 3ms
class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        maxBit = num;
        _dfs();
        return result;
    }
private:
    vector<string> result;
    vector<int> minBuf;
    vector<int> hourBuf;
    int maxBit;
    void _minDfs(int remainBits, int curMin, int height){
        //如果当前剩余可以亮的灯数比还未判断的（包括当前位）的灯的数量还多的话，不可能满足，故return
        if (remainBits > 6 - height || curMin > 59)  return;
        if (remainBits == 0){
            minBuf.push_back(curMin);
            return;
        }
        _minDfs(remainBits - 1, curMin + pow(2, height), height + 1);
        _minDfs(remainBits, curMin, height + 1);
    }
    void _hourDfs(int remainBits, int curHour, int height){
        //如果当前剩余可以亮的灯数比还未判断的（包括当前位）的灯的数量还多的话，不可能满足，故return
        if (remainBits > 4 - height || curHour > 11)  return;
        if (remainBits == 0){
            hourBuf.push_back(curHour);
            return;
        }
        _hourDfs(remainBits - 1, curHour + pow(2, height), height + 1);
        _hourDfs(remainBits, curHour, height + 1);  
    }
    void _dfs(){
        for (int i = 0, j = maxBit - i; i <= maxBit && i <= 4; i++, j--){
            minBuf.clear();
            hourBuf.clear();
            _hourDfs(i, 0, 0);
            _minDfs(j, 0, 0);
            _combineHourAndMin();
        }
        return;
    }
    void _combineHourAndMin(){
        sort(hourBuf.begin(), hourBuf.end());
        sort(minBuf.begin(), minBuf.end());
        for (int i = 0; i < hourBuf.size(); i++)
            for (int j = 0; j < minBuf.size(); j++)
                result.push_back(string(_tranInt2Str(hourBuf[i], minBuf[j])));
        return;
    }
    string _tranInt2Str(int curHour, int curMin){
        string curTime;
        char buf[10];
        sprintf(buf, "%d", curHour);
        curTime = buf;
        curTime += ":";
        if (curMin < 10)
            curTime += "0";
        sprintf(buf, "%d", curMin);
        curTime += buf;

        return curTime;
    }
};

BitsCount法

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        for (int h = 0; h < 12; h++)
            for (int m = 0; m < 60; m++)
                if (_bitCount(h, m) == num)
                    result.push_back(string(_tranInt2Str(h, m)));
        
        return result;
    }
private:
    vector<string> result;
    int _bitCount(int hour, int min){
        int hBit = 0;
        int mBit = 0;
        for (int i = 8; i >= 0; i /= 2){
            if (hour == 0)  break;
            if (hour % i != hour){
                hBit++;
                hour %= i;
            }
        }
        for (int i = 32; i >= 0; i /= 2){
            if (min == 0)   break;
            if (min % i != min){
                mBit++;
                min %= i;
            }
        }
        return hBit + mBit;
    }
    string _tranInt2Str(int curHour, int curMin){
        string curTime;
        char buf[10];
        sprintf(buf, "%d", curHour);
        curTime = buf;
        curTime += ":";
        if (curMin < 10)
            curTime += "0";
        sprintf(buf, "%d", curMin);
        curTime += buf;

        return curTime;
    }   
};

怀疑自己智商之神级代码系列

最后再贴一份来自Solution的神级代码，又是让人怀疑自己智商系列。
可以看到该作者对C++内的数据结构和方法了解得比较多，其实也不是真的说自己智商低吧···主要还是C++的底子太差，代码经验少。

vector<string> readBinaryWatch(int num) {
    vector<string> rs;
    for (int h = 0; h < 12; h++)
    for (int m = 0; m < 60; m++)
        if (bitset<10>(h << 6 | m).count() == num)
            rs.emplace_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));
    return rs;
}