直接采用回溯暴搜的方法很复杂
int hours[] = {1,2,4,8}; int minutes[] = {1,2,4,8,16,32}; class Solution { public: set<string> res; bool visited_hours[4]={false}; bool visited_minutes[6]={false}; //int hours[] = {1,2,4,8}; //int minutes[] = {1,2,4,8,16,32}; unordered_set<int> HashTime; vector<string> readBinaryWatch(int num) { dfs(num,0,0); vector<string> ans; for(auto s:res) ans.push_back(s); return ans; } void dfs(int num, int hour, int minute){ if(hour>=12||minute>=60) return; if(num==0){ string minute_string = (minute<10)?"0"+to_string(minute):to_string(minute); string time = to_string(hour) + ":" + minute_string; res.insert(time); return; } for(int i=0;i<4;i++){ if(visited_hours[i]) continue; visited_hours[i] = true; dfs(num-1,hour+hours[i],minute); visited_hours[i] = false; } for(int i=0;i<6;i++){ if(visited_minutes[i]) continue; visited_minutes[i] = true; dfs(num-1,hour,minute+minutes[i]); visited_minutes[i] = false; } } };
这里最优的做法是枚举所有时间，判断这些时间的二进制表示是否符号要求，如果符合，就加入到答案。
class Solution { public List<String> readBinaryWatch(int num) { List<String> times = new ArrayList<>(); for (int h=0; h<12; h++) for (int m=0; m<60; m++) if (Integer.bitCount(h * 64 + m) == num) times.add(String.format("%d:d", h, m)); return times; } }
