[leetcode] 401. Binary Watch

[leetcode] 401. Binary Watch

Description

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 = 1Return: ["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”.

分析一

题目的意思是： 给你一个非负整数，代表手表的亮的灯的数目，返回所有可能的时间点的组合。

这道题还是easy题目，但是我感觉不容易做不出来，还是backtrack方法，暴力出所有可能的组合。代码看似复杂，其实很简单。

代码一

class Solution {public: vector readBinaryWatch(int num) { vector res; vector hour{8,4,2,1},minute{32,16,8,4,2,1}; for(int i=0;i<=num;i++){ vector hours=generate(hour,i); vector minutes=generate(minute,num-i); for(int h:hours){ if(h>11) continue; for(int m:minutes){ if(m>59) continue; res.push_back(to_string(h)+(m<10 ? ":0":":")+to_string(m)); } } } return res; } vector generate(vector nums,int cnt){ vector res; solve(res,cnt,0,0,nums); return res; } void solve(vector& res,int cnt,int start,int out,vector nums){ if(cnt==0){ res.push_back(out); return ; } for(int i=start;i

参考文献

​​[LeetCode] Binary Watch 二进制表​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。