leetcode-二进制手表

二进制手表顶部有 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"]

注意事项:

输出的顺序没有要求。
小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。

思路：1，2，4，8，16进行组合。与组合总数类型的题目相似：leetcode-组合总数III（回溯）

但是数字为小时和分钟，因此通过一个k和num-k来控制小时和分钟的个数。

具体代码如下：

//思路： 通过1，2，4，8的组合获得h和m的可能性，与combination相似。每次组合的过程中，从小时中取出i个，从分钟取出num-i个。
//组合的思想为回溯： 与组合类似，取出多少个数字进行组合。
class Solution {
public:
    void dfs(vector<int>& nums,vector<int>& temp,int count,int out,int start){
        if(count==0){
            temp.push_back(out);
            return;
        }
        for(int i=start;i<nums.size();i++){
            dfs(nums,temp,count-1,out+nums[i],i+1);
        }
    }
    vector<int> help(vector<int>& nums,int count){
        vector<int> temp;
        dfs(nums,temp,count,0,0);
        return temp;
    }
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        vector<int> hours{1,2,4,8},mins{1,2,4,8,16,32};
        for(int k=0;k<=num;k++){
            vector<int> hour=help(hours,k);
            vector<int> min=help(mins,num-k);
            for(int h:hour){
                if(h>11)continue;
                for(int m:min){
                    if(m>59)continue;
                    res.push_back(to_string(h)+(m>9?":":":0")+to_string(m));
                }
            }
        }
        return res;
    }
};

奇淫技巧！！！

Java 利用String 函数的format，可以将字符串特定格式化输出！！！

bitCount

public static int bitCount(int i)

返回指定 int 值的二进制补码表示形式的 1 位的数量。比如bitCount(1) =1; (2)=1 ; (3)=2;

class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res=new ArrayList();
       for(int h=0;h<12;h++){
           for(int m=0;m<60;m++){
               if(Integer.bitCount(h)+Integer.bitCount(m)==num)
                   res.add(String.format("%d:%02d",h,m));
           }
       }
        return res;
    }
}