LeetCode 401. Binary Watch

题目

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".
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".

解析

题目还是很好理解。其中要注意的是，输入的n为灯亮的个数，即1的个数，因为每个灯亮和不亮代表1和0。
因此，输入2代表有两个灯亮，这时要考虑所有的情况。
本题的解法采用了遍历，网上有的答案是采用DFS，即深度优先遍历，再加上剪枝。由其使用C语言实现比较复杂，因此读者可以使用其它的高级语言进行实现。

代码

int countOne(int num);
char** readBinaryWatch(int num, int* returnSize) {
    if (num == 0) {
        (*returnSize) = 1;
        
        char** resultArr = (char**)calloc(1, sizeof(char*));
        
        resultArr[0] = (char*)calloc(6, sizeof(char));
        resultArr[0] = "0:00";
        
        return resultArr;
    }
    
    char** resultArr = (char**)calloc(1000, sizeof(char*));
    int hourOneNum = 0, minOneNum = 0, totalOneNum = 0;
    int count = 0;
    
    for (int i = 0; i < 12; ++i) {
        hourOneNum = countOne(i);
        
        for (int j = 0; j < 60; ++j) {
            minOneNum = countOne(j);
            totalOneNum = hourOneNum + minOneNum;
            
            if (totalOneNum == num) {
                // save
                resultArr[count] = (char*)calloc(6, sizeof(char*));
                sprintf(resultArr[count], "%d:%02d", i, j);
                ++count;
            }
        }
    }
    
    (*returnSize) = count;
    
    return resultArr;
}

int countOne(int num) {
    int oneNum = 0;
    
    while (num) {
        oneNum += num & 1;
        num >>= 1;
    }
    
    return oneNum;
}

countOne为计算遍历中i,j中含有1的个数，最终相加的结果和num相等，即灯亮的个数相等，那么该结果便是正确的。使用到了库函数sprintf，更方便一些。