【Day 48 】2021-10-27 - 401. 二进制手表

[azl397985856]

401. 二进制手表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/binary-watch/

前置知识

暂无

题目描述

二进制手表顶部有 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”。
超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 "13:00", "0:61" 等时间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yanglr]

思路:

题意: 这个手表能表示12小时制的 小时:分钟格式时间。

虽然n的范围是 0 =< n <= 10, 不算大, 但有些情形下的排列组合的数量还是挺多的, 故暴力枚举可能不适合用~

由于题目是"二进制"手表, 那我们试试位运算吧~

方法: 位运算

问题转换 -> 位运算

我们经常用二进制的1表示灯泡💡亮了, 而用0表示灯泡没亮, 这个电子手表同理。

于是问题可以转变为: 找 00:00 -> 11:59 范围内的数, 使得刚好小时位和分钟位的二进制表示中1的总数为输入的数 turnedOn。

位运算中如何统计整数n的二进制表示中1的个数?

位运算中有个常用的技巧: 迭代执行 n = n&(n-1) 直到全0 就可以统计出数n 的二进制表示中1的个数, 因为每迭代一次，其效果是将最右侧存有1的bit的值置为0。(举几个例子就明白了。)

进行两层循环即可做到, 循环变量依次为 h, m (h: 小时, m: 分钟), 最后将结果放入动态数组(比如, C++中是vector)中。

最后需要注意的是, 分钟数字＜10时需要在":"与该数之间补0, 而小时位<10时不用在前面补0, 是多少就输出多少。

代码

实现语言: C++

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        // h: 小时, m: 分钟. 00:00 -> 11:59
        vector<string> res = {};
        for (int h = 0; h < 12; h++)
        {
            for (int m = 0; m < 60; m++)
            {
                if (count1(h) + count1(m) == turnedOn) 
                {
                    string mStr = m < 10 ? "0" + to_string(m) : to_string(m);
                    res.push_back(to_string(h) + ":" + mStr);
                }                
            }            
        }
        return res;
    }

    int count1(int n)
    {
        int count = 0;
        while (n > 0)
        {
            n = n & (n - 1);
            count++;
        }

        return count;
    }
};

复杂度分析

• 时间复杂度: O(12*60)
• 空间复杂度: O(1)

[cicihou]

from itertools import combinations

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        '''
        利用 combinations 将所有的可能性进行非重复的排练组合，聪明的解法

        因为时针有 4 个点 [1,2,3,8]，时钟的亮灯次数只能对应[0,1,2,3]，如果四盏灯全亮会超过 12
        因此不管亮灯数有多少，按照时针的可能性来推排列组合的可能性，时针的可能性有且只有四种
        因此在时针处的循环是 min(4, turnedOn + 1)

        这个问题本身是常数级别的问题，因为时间的有穷性

        这道题还可以用 bit manipulation
        https://leetcode-solution.cn/solutionDetail?type=3&id=40&max_id=2
        https://leetcode.com/problems/binary-watch/discuss/302787/Python-20ms
        '''
        res = set()

        def possible_numbers(count, minute=False):
            if count == 0:
                return [0]
            if minute:
                return filter(lambda x: x < 60, map(sum, combinations([1,2,4,8,16,32], count)))
            return filter(lambda x: x < 12, map(sum, combinations([1,2,4,8], count)))

        for i in range(min(4, turnedOn + 1)):
            hours = possible_numbers(i)
            for a in hours:
                minutes = possible_numbers(turnedOn-i, True)
                for b in minutes:
                    res.add(str(a) + '%02d' % str(b))
        return res

[st2yang]

思路

• 枚举
• bin count

代码

• python

  class Solution:
  def readBinaryWatch(self, turnedOn: int) -> List[str]:
      res = []
      for h in range(12):
          for m in range(60):
              if bin(h).count('1') + bin(m).count('1') == turnedOn:
                  res.append(f"{h}:{m:02d}")
      return res

复杂度

• 时间: O(1)
• 空间: O(1)

[zjsuper]

Idea: itertools.combinations and dfs, time: O(1)

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans = []
        # how many on hour, how many on min
        #if turnedOn == 0 or turnedOn >9:
        #    return []
        def dfs(ans,hour,num):
            if hour > num:
                return
            for h in itertools.combinations([1,2,4,8],hour):
                if sum(h)>11:
                    continue
                for m in itertools.combinations([1,2,4,8,16,32],num-hour):
                    if sum(m)>59:
                        continue
                    time = "%d:%02d" % (sum(h),sum(m))
                    ans.append(time)
            dfs(ans,hour+1,num)
        dfs(ans,0,turnedOn)
        return ans

[JiangyanLiNEU]

Idea

• h is the number of lighted number in hour, m is the number of lighted number in minute
• h+m == turnedOn, and h<=3, m <=5
• use backtracking to get all the possible combination of hour and minute separately, note that BT return a set of sum of all the lighted number
• hour < 12 and minute <60, and we combine hour and minute to string, note that we need to add '0' if minute < 10
• runtime = O(1), space = O(1)

  Python Code

  class Solution(object):
  def readBinaryWatch(self, turnedOn):
      choice = {'hour':[1,2,4,8],'minute':[1,2,4,8,16,32]}
      max_hour = 3
      max_min = 5
      # Edge Cases
      if turnedOn ==0 :
          return ["0:00"]
      if turnedOn > 8:
          return []
      # Backtracking to find all the combination
      def BT(cur, result, array, left, index):
          if index == len(array):
              if left == 0:
                  if sum(cur) not in result:
                      result.add(sum(cur))
          else:
              if left == 0:
                  if sum(cur) not in result:
                      result.add(sum(cur))
              else:
                  BT(cur+[array[index]], result, array, left-1, index+1)
                  BT(cur, result, array, left, index+1)
      def get_hour(num):
          result = set([])
          BT([], result, choice['hour'], num, 1)
          BT([choice['hour'][0]],result, choice['hour'], num-1, 1)
          return result
      def get_min(num):
          result = set([])
          BT([], result, choice['minute'], num, 1)
          BT([choice['minute'][0]],result, choice['minute'], num-1, 1)
          return result
      result = set([])
      # distribute number to hour and minute
      for ho in range(max_hour+1):
          for mi in range(max_min+1): 
              if ho+mi == turnedOn:
                  minute = get_min(mi)
                  hour = get_hour(ho)
                  for h in hour:
                      if h >= 12:
                          continue
                      else:
                          h = str(h)
                      for m in minute:
                          if m >= 60:
                              continue
                          elif m < 10:
                              m = '0'+str(m)
                          else:
                              m = str(m)
                          result.add(h+":"+m)
      return [ele for ele in result]

[zliu1413]

class Solution(object): def readBinaryWatch(self, turnedOn): """ :type turnedOn: int :rtype: List[str] """ ans = list() for h in range(12): for m in range(60): if bin(h)[2:].count('1') + bin(m)[2:].count('1') == turnedOn: ans.append(str(h) + ':%02d' % m) return ans

[yachtcoder]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        candies = [8*60, 4*60, 2*60, 60, 32, 16,8, 4, 2, 1][::-1]
        if turnedOn == 0: return ["0:00"]
        ##### enumerate beat 72%
        def enumerate():
            ret = []
            cnt1 = {i:Counter(bin(i))['1'] for i in range(60)}
            for h in range(12):
                for m in range(60):
                    if cnt1[h] + cnt1[m] == turnedOn:
                        ret.append(str(h).zfill(1) + ":" + str(m).zfill(2))
            return ret
        return enumerate()
        def min2s(mins):
            h, m = divmod(mins, 60)
            return str(h).zfill(1) +":"+ str(m).zfill(2)
        ##### functools combination + pruning, beat 90%
        def combi():
            ret = []
            for c in combinations(candies, turnedOn):
                idx = bisect_left(c, 60)
                if sum(c[:idx]) >= 60: continue
                mins = sum(c)
                if mins >= 720: continue
                ret.append(min2s(mins))
            return ret
        return combi()
        ##### homemade subset with backtracking, beat 72%
        ret = []
        N = len(candies)
        def dfs(used, m, h, idx):
            if used == turnedOn: 
                ret.append(m+h)
                return
            for i in range(idx, N):
                c = candies[i]
                if c < 60 and m + c >= 60: continue
                if c >= 60 and h + c >= 720: continue
                if h+m+c >= 720: break
                dfs(used+1, m + (c if c < 60 else 0), h+ (c if c >= 60 else 0), i+1)
        dfs(0, 0, 0, 0)
        return [min2s(t) for t in sorted(list(ret))]

[yingliucreates]

link:

https://leetcode.com/problems/binary-watch/

代码 Javascript

const readBinaryWatch = function (num) {
  var hour,
    minutes,
    numBits,
    result = [],
    hourFormat = '';

  for (hour = 0; hour <= 11; hour++) {
    for (minutes = 0; minutes <= 59; minutes++) {
      // Count the number of 'one' bits in each number
      numBits = hour.toString(2).split(1).length - 1;
      numBits += minutes.toString(2).split(1).length - 1;

      // If the number of bits in the hour is the same as the requested number add it to the results
      if (numBits === num) {
        // Format the output, if the minutes are less than 10 add a zero at the beggining of the string
        hourFormat =
          hour.toString() +
          ':' +
          (minutes < 10 ? '0' + minutes.toString() : minutes.toString());
        result.push(hourFormat);
      }
    }
  }

  return result;
};

[zhangzhengNeu]

\401. Binary Watch

思路

1. calculate h ,m == num;
2. transfer the, into time format

代码

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:%02d", h, m));
    return times;        
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[Daniel-Zheng]

思路

回溯法。

代码(C++)

class Solution {
public:
    void dfs(int turnedOn, int index, int hours, int mins, vector<int>& nums, vector<string>& res) {
        if (turnedOn == 0) {
            string minStr;
            if (mins < 10) minStr = '0' + to_string(mins);
            else minStr = to_string(mins);
            res.push_back(to_string(hours) + ':' + minStr);
            return;
        }
        for (int i = index; i < nums.size(); i++) {
            if (i < 4 && hours + nums[i] <= 11) dfs(turnedOn - 1, i + 1, hours + nums[i], mins, nums, res);
            if (i >= 4 && mins + nums[i] <= 59) dfs(turnedOn - 1, i + 1, hours, mins + nums[i], nums, res);
        }
    }

    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> res;
        int index = 0, hours = 0, mins = 0;
        vector<int> nums = {8, 4, 2, 1, 32, 16, 8, 4, 2, 1};
        dfs(turnedOn, index, hours, mins, nums, res);
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[kidexp]

thoughts

可以用回溯法，先枚举可能的hour，然后找到对应的可能的minutes

看了别人的解法，可以用bit来做

code

from typing import List

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        hour_bit_list = [1, 2, 4, 8]
        minute_bit_list = [1, 2, 4, 8, 16, 32]
        result = []

        def dfs(
            iterate_list,
            iterate_index,
            value,
            max_value,
            remaining_count,
            need_down_to_zero,
            result_list,
        ):
            if need_down_to_zero:
                if remaining_count == 0:
                    result_list.append((value, remaining_count))
            else:
                result_list.append((value, remaining_count))
            if remaining_count > 0:
                for i in range(iterate_index, len(iterate_list)):
                    new_value = value + iterate_list[i]
                    if new_value < max_value:
                        dfs(
                            iterate_list,
                            i + 1,
                            new_value,
                            max_value,
                            remaining_count - 1,
                            need_down_to_zero,
                            result_list,
                        )

        hour_list = []
        dfs(hour_bit_list, 0, 0, 12, turnedOn, False, hour_list)
        for hour, remaining_count in hour_list:
            minute_list = []
            dfs(minute_bit_list, 0, 0, 60, remaining_count, True, minute_list)
            for minute, _ in minute_list:
                result.append(
                    str(hour)
                    + ":"
                    + (str(minute) if minute > 9 else ("0" + str(minute)))
                )
        return result

    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        """
        bit manipulation
        """
        result = []
        for hour in range(12):
            for minute in range(60):
                if bin(hour).count("1") + bin(minute).count("1") == turnedOn:
                    result.append(
                        str(hour)
                        + ":"
                        + (str(minute) if minute > 9 else ("0" + str(minute)))
                    )
        return result

complexity

Time 回溯法最多 O(4!+6!) 而bit O(11(hour)60(minute)16(double count)) = O(1)

Space也是类似 O(1）

[wangzehan123]

题目地址(401. 二进制手表)

https://leetcode-cn.com/problems/binary-watch/

题目描述

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

例如，下面的二进制手表读取 "3:25" 。

（图源：WikiMedia - Binary clock samui moon.jpg ，许可协议：Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) ）

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：

例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

 

示例 1：

输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

示例 2：

输入：turnedOn = 9
输出：[]

 

提示：

0 <= turnedOn <= 10

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public List<String> readBinaryWatch(int num) {
        int led[]=new int[]{1,2,4,8,1,2,4,8,16,32};
        List<String> ans=new ArrayList<>();
        for(int i=0;i<1024;i++){            
            if(hasNumBits(i,num)){
                int k=i;
                int minute=0;
                int hour=0;
                for(int j=0;j<10;j++){
                    if(k%2==1){
                        if(j<4){hour+=led[j];}
                        else{minute+=led[j];}
                    }
                    k/=2;                    
                }
                if(hour<=11&&minute<=59){
                    ans.add(hour+":"+(minute<10?("0"+minute):(minute+"")));
                }
            }           
        }
        return ans;
    }
    public boolean hasNumBits(int m,int num){
        //n的二进制是否有num个1
        int ans=0;
        int n=m;
        while(n>0){
            ans+=n%2;
            n/=2;
        }
        return ans==num;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[mmboxmm]

思路

• 分别找hour和mintue
• 计算0-60的二进制1的个数

代码

class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> result = new ArrayList<>();
        if (num == 0) {
            result.add("0:00");
            return result;
        }

        for (int i = 0; i <= num; i++) {
            Set<Integer> hours = helper(i, 12);
            Set<Integer> mins = helper(num - i, 60);

            for (Integer h : hours) {
                for (Integer m : mins) {
                    if (m < 10) {
                        result.add(String.valueOf(h) + ":0" + String.valueOf(m));
                    } else {
                        result.add(String.valueOf(h) + ":" + String.valueOf(m));
                    }
                }
            }
        }

        return result;
    }

    Set<Integer> helper(int n, int scope) {
        Set<Integer> ans = new HashSet<Integer>();

        for (int i = 0; i < scope; i++) {
            if (ones(i) == n) {
                ans.add(i);
            }
        }
        return ans;
    }

    private int ones(int n) {
        int num = 0;
        while(n != 0) {
            num++;
            n = n & (n - 1);
        }
        return num;
    }

}

[mixtureve]

思路

backtrack

代码

• 语言支持：Java

Java Code:

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        // 从 第一行 选 x 个，第二行选 turnedOn - x 个，可以组合起来 从十个状态里选 turnedOn 个亮灯
        List<String> ret = new ArrayList<>();
        if (turnedOn > 8) {
            return ret;
        }

        int[] first = new int[]{1, 2, 4, 8}; // 第一行 对应 hour
        int[] second = new int[]{1, 2, 4, 8, 16, 32}; // 第二行 对应 min
        backtrack(turnedOn, 0, first, second, 0, 0, ret);
        return ret;

    }

    private void backtrack(int n, int index, int[] first, int[] second, int hour, int min, List<String> ret) {
        if (hour > 11 || min > 59) {
            return ;   // 剪枝
        }
        // base case
        if (n == 0) {  // 注意 base case 条件，每回点亮一个等，剩余余额就小一直到变成 0
            // %02d means an integer, left padded with zeros up to 2 digits.
            ret.add(String.format("%d:%02d", hour, min));
        }

        // 总共 n 层， 每层 10个状态，前四个状态是 hour， 后6个状态是 min, 在选状态时候看 i < 4, 则加到 hour 上，反之 加到 min 上
        for (int i = index; i < 10; i++) {
            if (i > 3) {
                backtrack(n - 1, i + 1, first, second, hour, min + second[i - 4], ret);
            } else {
                backtrack(n - 1, i + 1, first, second, hour + first[i], min, ret);
            }
            // implicitly backtrack， 因为 hour 和 min 回弹时候直接变回前一层的值
        }

    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(C(n, 10))$
• 空间复杂度：$O(n)$

[Menglin-l]

看了题解才知道bitCount()的用法，这里先用DFS来做。

---

代码部分：

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new LinkedList<>();
        dfsSearch(turnedOn, 0, 0, 1, 1, new LinkedList<Integer>(), new LinkedList<Integer>(), ans);
        return ans;
    }

    public void dfsSearch(int turnedOn, int h, int m, int hBegin, int mBegin, LinkedList<Integer> hours, LinkedList<Integer> minutes, List<String> ans) {
        // 选中的小时数 + 选中的分钟数
        if (hours.size() + minutes.size() == turnedOn) {
            // 剪枝
            if (h < 12 && m < 60) {
                ans.add(String.format("%d:%02d", h, m));
            }
            return;
        }
        // 从给定的起点开始遍历小时    
        for (int i = hBegin; i <= 8; i <<= 1) {
            hours.addLast(i);
            dfsSearch(turnedOn, h + i, m, i << 1, mBegin, hours, minutes, ans);
            hours.removeLast();
        }
        // 从给定的起点开始遍历分钟  
        for (int j = mBegin; j <= 32; j <<= 1) {
            minutes.addLast(j);
            dfsSearch(turnedOn, h, m + j, 15, j << 1, hours, minutes, ans);
            minutes.removeLast();
        }
    }
}

---

复杂度：

Time: O(C(N, 10))，N为turnedOn

Space: O(N)，N为turnedOn

[chenming-cao]

解题思路

枚举。按照题意，对于有效的时间，小时的取值范围是0-11，分钟的取值范围是0-59。总共720种可能。我们对这720种可能组合逐一判定，看是否满足亮灯个数要求。如果满足要求，则按照字符串要求格式存入数组中。最后返回数组即可。判断亮灯个数是要看小时和分钟的数字二进制格式中1的个数，这里调用Integer.bitCount(int num)函数，可以直接得到1的个数。

代码

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(i);
                    sb.append(":");
                    if (j < 10) sb.append(0);
                    sb.append(j);
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(1)，双层循环总共运行720次，为常数
• 空间复杂度：O(1)

[florenzliu]

Explanation

• approach 1: permutation problem using dfs/backtracking
• bit manipulation: hr < 12, minute < 60

Python

# Approach 1
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        group = [8, 4, 2, 1, 32, 16, 8, 4, 2, 1]
        res = []

        def dfs(hour, minute, n, index, group):
            # base case:
            if hour >= 12 or minute >= 60:
                return
            if n == 0:
                zero = "0" if minute < 10 else ""
                time = str(hour) + ":" + zero + str(minute)
                res.append(time)
                return

            if index < len(group):
                if index <= 3: # handle hours
                    dfs(hour + group[index], minute, n-1, index+1, group)
                else: # handle minutes
                    dfs(hour, minute + group[index], n-1, index+1, group)
                dfs(hour, minute, n, index+1, group)

        dfs(0, 0, turnedOn, 0, group)

        return res

# Approach 2
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res = []
        for h in range(12):
            for m in range(60):
                if (bin(h) + bin(m)).count("1") == turnedOn:
                    zero = "0" if m < 10 else ""
                    time = str(h) + ":" + zero + str(m)
                    res.append(time)
        return res

[james20141606]

Day 48: 401. Binary Watch (backtracking, cartesian product)

• Problem Link

  • 401. Binary Watch

• Ideas

  • Backtracking means we just need to enumerate all the possible hours and minutes combinations given turned on. It is a classic cartesian product.
  • Another way is use binary to solve the problem. We just need to make sure that the 1 position of sum of hour and minute is equal to turnedOn.

• Complexity: hash table and bucket

  • Time: O(N)
  • Space: O(N)

• Code

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res = []
        for i in range(12):
            for j in range(60):
                if (bin(i) + bin(j)).count('1') == turnedOn:
                    res.append('{}:{:02d}'.format(i, j))
        return res

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        def possible_number(count, minute=False):
            if count == 0: return [0]
            if minute:
                #print ('minute', count, combinations([1, 2, 4, 8, 16, 32], count), list(map(sum, combinations([1, 2, 4, 8, 16, 32], count))), list(filter(lambda a: a < 60, map(sum, combinations([1, 2, 4, 8, 16, 32], count)))))
                return filter(lambda a: a < 60, map(sum, combinations([1, 2, 4, 8, 16, 32], count)))

            return filter(lambda a: a < 12, map(sum, combinations([1, 2, 4, 8], count)))
        ans = []
        for i in range(min(4, num + 1)):
            for a in possible_number(i):
                for b in possible_number(num - i, True):
                    ans.append('{}:{:02d}'.format(a, b))
        return  ans 

• other resources:

[xieyj17]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:

        bases = [2**i for i in range(4)] + [2**i for i in range(6)]
        res = []

        def dfs(n, depth, h, m, bases):
            if h >= 12 or m >= 60:
                return
            if n == 0:
                if m < 10:
                    time = str(h) + ":0" + str(m)
                else:
                    time = str(h) + ":" + str(m)
                res.append(time)
                return

            if depth < len(bases):
                dfs(n, depth+1, h, m, bases)
                if depth <= 3:
                    dfs(n-1, depth+1, h+bases[depth], m, bases)
                else:
                    dfs(n-1, depth+1, h, m+bases[depth], bases)
            else:
                return

        dfs(turnedOn, 0, 0, 0, bases)

        return res

Imagine a binary tree with each layer representing a possible value that can be added to hour or minutes. Use DFS to find the nodes with turnedON right branches.

Time: O(1)

Space: O(1)

[laofuWF]

class Solution:
    def readBinaryWatch(self, n):

        def dfs(n, hours, mins, idx):
            if hours >= 12 or mins > 59: return
            if not n:
                res.append("{}:{:02}".format(hours, mins))
                return
            for i in range(idx, 10):
                if i < 4: 
                    dfs(n - 1, hours | (1 << i), mins, i + 1)
                else:
                    k = i - 4
                    dfs(n - 1, hours, mins | (1 << k), i + 1)

        res = []
        dfs(n, 0, 0, 0)

        return res

[freedom0123]

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        char str[10];
        for (int i = 0; i < 1 << 10; i ++ ) {
            int s = 0;
            for (int j = 0; j < 10; j ++ )
                if (i >> j & 1)
                    s ++ ;
            if (s == num) {
                int a = i >> 6, b = i & 63;
                if (a < 12 && b < 60) {
                    sprintf(str, "%d:%02d", a, b);
                    res.push_back(str);
                }
            }
        }
        return res;
    }
};

[wangyifan2018]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans = list()
        for h in range(12):
            for m in range(60):
                if bin(h).count("1") + bin(m).count("1") == turnedOn:
                    ans.append(f"{h}:{m:02d}")
        return ans

[freesan44]

思路

通过回溯法，遍历有可能出现的可能性

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        hours = [1,2,4,8,0,0,0,0,0,0]
        minutes = [0,0,0,0,1,2,4,8,16,32]
        res = set()
        #通过枚举遍历有可能出现的可能性
        def possible_number(remindNums,index,hour,minute):
            if hour >11 or minute > 59:
                return
            if remindNums == 0:
                resStr = "%d:%02d"% (hour,minute)
                res.add(resStr)
                return
            for i in range(index,10):
                # print("i",i)
                possible_number(remindNums-1,i+1,hour + hours[i],minute+minutes[i])
        possible_number(turnedOn,0,0,0)
        return list(res)

if __name__ == '__main__':
    # turnedOn = 1
    turnedOn = 2
    res = Solution().readBinaryWatch(turnedOn)
    print(res)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[shawncvv]

思路

枚举

代码

JavaScript Code

var readBinaryWatch = function(turnedOn) {
    const ans = [];
    for (let h = 0; h < 12; ++h) {
        for (let m = 0; m < 60; ++m) {
            if (h.toString(2).split('0').join('').length + m.toString(2).split('0').join('').length === turnedOn) {
                ans.push(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
    }
    return ans;
};

复杂度

• 时间复杂度：O(1)
• 空间复杂度：O(1)

[tongxw]

思路

用回溯法的话，类似77求组合。就是从10个代表小时和分钟的数字中，选取n个数字，如果组成的时间是合法的（hour < 12 && minutes < 60），就记录答案。

代码

class Solution {
    int[] hours = new int[] {8, 4, 2, 1, 0, 0, 0, 0, 0, 0};
    int[] minutes = new int[] {0, 0, 0, 0, 32, 16, 8, 4, 2, 1};

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<>();
        backTracking(ans, 0, turnedOn, 0, 0);
        return ans;
    }

    private void backTracking(List<String> ans, int start, int total, int hour, int minute) {
        if (total == 0) {
            ans.add(String.format("%d:%02d", hour, minute));
        }

        for (int i=start; i<10; i++) {
            int newHour = hour + hours[i];
            int newMinutes = minute + minutes[i];
            if (newHour >= 12 || newMinutes >= 60) {
                // prune
                continue;
            }

            backTracking(ans, i+1, total - 1, hour + hours[i], minute + minutes[i]);
        }
    }
}

TC: 10选n的组合数，因为n有限，= O(1) SC: O(n) = O(1)

[ZacheryCao]

Idea:

Backtracking.

Code:

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res = set()
        if turnedOn >= 9:
            return res
        H = [8, 4, 2, 1]
        M = [32, 16, 8, 4, 2, 1]
        h = set()
        m = set()

        def backtrack(turnedOn):
            if turnedOn == 0:
                if sum(m) < 10:
                    res.add(str(sum(h))+":0"+str(sum(m)))
                else:
                    res.add(str(sum(h))+":"+str(sum(m)))
                return
            for i in H:
                if i not in h and i + sum(h) < 12:
                    h.add(i)
                    backtrack(turnedOn - 1)
                    h.remove(i)
            for i in M:
                if i not in m and i + sum(m) < 60:
                    m.add(i)
                    backtrack(turnedOn - 1)
                    m.remove(i)
        backtrack(turnedOn)
        return res

Complexity:

Time: O(n!). n = turnedOn Space: O(n).

[BpointA]

思路

因为一共也就12*60个可能性，所以直接按照空间和时间分别计算亮灯数，构成两个哈希表，再根据最终亮灯数的组合将哈希表内容两两组合即可

Python3代码

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        minutes=defaultdict(list)
        for i in range(60):
            mi=i
            cnt=0
            while mi>0:
                if mi%2==1:
                    cnt+=1
                mi=mi//2
            minutes[cnt].append(i)
        hours=defaultdict(list)
        for i in range(12):
            h=i
            cnt=0
            while h>0:
                if h%2==1:
                    cnt+=1
                h=h//2
            hours[cnt].append(i)
        res=[]
        for h in range(turnedOn+1):
            m=turnedOn-h
            if len(hours[h])!=0 and len(minutes[m])!=0:
                for x in hours[h]:
                    for y in minutes[m]:
                        if y<10:
                            res.append(str(x)+":0"+str(y))
                        else:
                            res.append(str(x)+":"+str(y))
        return res

复杂度

时间：O(1)

空间：O(1)

[mannnn6]

代码

class Solution {    
    static Map<Integer, List<String>> map = new HashMap<>();
    static {
        for (int h = 0; h <= 11; h++) {
            for (int m = 0; m <= 59; m++) {
                int tot = getCnt(h) + getCnt(m);
                List<String> list = map.getOrDefault(tot, new ArrayList<String>());
                list.add(h + ":" + (m <= 9 ? "0" + m : m));
                map.put(tot, list);
            }
        }
    }
    static int getCnt(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans++;
        return ans;
    }
    static int lowbit(int x) {
        return x & -x;
    }
    public List<String> readBinaryWatch(int t) {
        return map.getOrDefault(t, new ArrayList<>());
    }
}

复杂度

时间复杂度：O(1) 空间复杂度: O(N)

[yan0327]

不太会做枚举题目，找找感觉

import "fmt"
func readBinaryWatch(turnedOn int) []string {
    out := []string{}
    for h:= uint8(0);h < 12;h++{
        for m := uint8(0);m<60;m++{
            if count(h) + count(m) == turnedOn{
                out = append(out, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return out
}
func count(n uint8) int { //求位数
    res := 0
    for n != 0 {
        n = n & (n - 1)
        res++
    }
    return res
}

时间复杂度：O（1）枚举 空间复杂度：O（1）

[okbug]

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        char str[10];
        for (int i = 0; i < 1 << 10; i ++ ) {
            int s = 0;
            for (int j = 0; j < 10; j ++ )
                if (i >> j & 1)
                    s ++ ;
            if (s == num) {
                int a = i >> 6, b = i & 63;
                if (a < 12 && b < 60) {
                    sprintf(str, "%d:%02d", a, b);
                    res.push_back(str);
                }
            }
        }
        return res;
    }
};

[zszs97]

开始刷题

题目简介

【Day 48 】2021-10-27 - 401. 二进制手表

题目思路

• 枚举

题目代码

代码块

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        return ans;
    }
};

复杂度

• 时间复杂度 O(1)
• 空间复杂度 O(1)

[Francis-xsc]

思路

思路一：枚举，可以计算数字二进制中1的个数 思路二：回溯

代码

思路一：

class Solution {
private:
    int BitCount(int n){
        int c=0;
        while(n){
            n&=(n-1);
            c++;
        }
        return c;
    }
public:
    vector<string> readBinaryWatch(int turnedOn) {
        int ans=0;
        vector<string> res;
        for(int i=0;i<=11;i++){
            for(int j=0;j<=59;j++){
                if(BitCount(i)+BitCount(j)==turnedOn){
                    string s=""+to_string(i)+":"+(j<10?"0"+to_string(j):to_string(j));
                    res.push_back(s);
                }
            }
        }
        return res;
    }
};

思路二：

class Solution {
private:
    vector<string>ans;
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<int>a(11,0);
        dfs(a,0,0,turnedOn);
        return ans;
    }

    void dfs(vector<int>a, int pos,int cnt,int turnedOn){
        if(pos==11){
            return;
        }
        if(cnt==turnedOn){
            int h=0,m=0;
            for(int i=0;i<4;i++){
                if(a[i]){
                    h+=(1<<(3-i));
                }
            }
            for(int i=0;i<6;i++){
                if(a[i+4]){
                    m+=(1<<(5-i));
                }
            }
            if(h<=11&&m<=59)
                ans.push_back(to_string(h)+":"+(m<10?"0"+to_string(m):to_string(m)));
            return;
        }
        dfs(a,pos+1,cnt,turnedOn);
        a[pos]=1;
        dfs(a,pos+1,cnt+1,turnedOn);
    }
};

复杂度分析 思路一：

• 时间复杂度：O(1)
• 空间复杂度：O(1) 思路二：
• 时间复杂度：O(N)
• 空间复杂度：O(N)

[siyuelee]

枚举

class Solution(object):
    def readBinaryWatch(self, turnedOn):
        res = []
        for i in range(12):
            for j in range(60):
                if bin(i).count("1") + bin(j).count("1") == turnedOn:
                    res.append('{}:{:02d}'.format(i, j))
        return res

T: O1. 循环次数与输入值无关 S: O1

[littlemoon-zh]

day 48

401. Binary Watch

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        def dfs(left, start, cur, digit, bound, res):
            if cur > bound: return
            if left == 0:
                if cur <= bound:
                    res.append(cur)
                return
            for i in range(start, digit):
                dfs(left - 1, i + 1, cur + 2 ** i, digit, bound, res)

        def getH(i):
            res = []
            dfs(i, 0, 0, 4, 11, res)
            return res
        def getM(i):
            res = []
            dfs(i, 0, 0, 6, 59, res)
            return res

        ans = []

        for i in range(turnedOn + 1):
            hs = getH(i)
            ms = getM(turnedOn - i)

            for h in hs:
                for m in ms:
                    ans.append('%d:%02d' % (h, m))
        return ans

[JK1452470209]

思路

枚举时 分的二进制位数，相加等于输入值添加进答案

代码

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    ans.add(h + ":" + (m < 10 ? "0" : "") + m);
                }
            }
        }
        return ans;
    }
}

复杂度

时间复杂度：O(1)

空间复杂度：O(1)

[muimi]

思路

枚举、暴力解法

代码

class Solution {
  public List<String> readBinaryWatch(int turnedOn) {
    List<String> res = new ArrayList<>();
    for (int i = 0; i < 1024; i++) {
      int h = i >> 6, m = i % 64; // m = i & 63
      if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
        res.add(h + ":" + (m < 10 ? "0" : "") + m);
        // res.add(String.format("%d:%02d", h, m));
      }
    }
    return res;
  }
}

复杂度

• 时间复杂度：O(1)
• 空间复杂度：O(1)

[shamworld]

思路

枚举

代码

var readBinaryWatch = function(turnedOn) {
    let res = [];
    for(let i = 0;i < 12;i++){
        for(let j = 0;j < 60;j++){
            if(i.toString(2).split('0').join('').length+j.toString(2).split('0').join('').length===turnedOn){
                res.push(i+':'+(j<10?'0':'')+j);
            }
        }
    }
    return res;
};

[JinMing-Gu]

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        return ans;
    }
};

[jiahui-z]

思路: use the idea of backtracking, explore all possible combination of hour and minute digits, given the total number of turned-on LEDs

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();

        int[] hours = new int[]{8, 4, 2, 1};
        int[] minutes = new int[]{32, 16, 8, 4, 2, 1};

        for (int i = 0; i <= turnedOn; i++) {
            int hourDigits = i;
            int minuteDigits = turnedOn - i;

            List<Integer> hourOptions = buildOptions(hours, hourDigits);  
            List<Integer> minuteOptions = buildOptions(minutes, minuteDigits);

            for (int hour : hourOptions) {
                if (hour >= 12) continue;
                for (int minute : minuteOptions) {
                    if (minute >= 60) continue;
                    String minuteStr = minute <= 9 ? String.format("0%d", minute) : String.valueOf(minute);
                    result.add(String.format("%d:%s", hour, minuteStr));
                }
            }
        }

        return result;
    }

    private List<Integer> buildOptions(int[] nums, int numOfDigits) {
        List<Integer> options = new ArrayList<>();
        backtrack(nums, numOfDigits, options, 0, 0);
        return options;
    }

    private void backtrack(int[] nums, int availableDigits, List<Integer> options, int start, int sum) {
        if (availableDigits == 0) {
            options.add(sum);
        }
        for (int i = start; i < nums.length; i++) {
            backtrack(nums, availableDigits - 1, options, i + 1, sum + nums[i]);
        }
    }
}

Time complexity: O(n!) n is turnedON Space complexity: O(n)

[L-SUI]

var readBinaryWatch = function (num) { const timeList = []; function dfs(time, n, index) { const hour = time >> 6, minute = time & 0b111111; if (hour > 11 || minute > 59) return; if (n === 0) { timeList.push(${hour}:${minute < 10 ? "0" + minute : minute}); return; } const end = 10 - n; while (index <= end) { dfs(time | (1 << index), n - 1, ++index); } } dfs(0, num, 0); return timeList; };

[ychen8777]

思路

遍历可能出现的小时 h 、分钟 m，用 Integer.bitCount() 反推二进制数量

代码

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {

        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) == turnedOn) {
                    String time = h + ":" + (m < 10 ? "0" : "") + m;
                    res.add(time);
                }

            }

        }

        return res;
    }
}

复杂度

时间: O(1) \ 空间: O(n)

[doveshnnqkl]

思路

回溯，copy 人家的 在10个灯中选num个灯点亮，如果选择的灯所组成的时间已不合理（小时超过11，分钟超过59）就进行剪枝 也就是从0到10先选一个灯亮，再选当前灯的后面的灯亮，再选后面的灯的后面的灯亮，一直到num个灯点满 链接：https://leetcode-cn.com/problems/binary-watch/solution/401-er-jin-zhi-shou-biao-hui-su-java0ms-xroa6/

代码

class Solution {
    int[] hours = new int[]{1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
    int[] minutes = new int[]{0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
    List<String> res = new ArrayList<>();

    public List<String> readBinaryWatch(int num) {
        backtrack(num, 0, 0, 0);
        return res;
    }

    public void backtrack(int num, int index, int hour, int minute){
        if(hour > 11 || minute > 59) 
            return;
        if(num == 0){
            StringBuilder sb = new StringBuilder();
            sb.append(hour).append(':');
            if (minute < 10) {
                sb.append('0');
            }
            sb.append(minute);
            res.add(sb.toString());
            return;
        }
        for(int i = index; i < 10; i++){
            backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }  
    }
}

复杂度

时间复杂度：O(C 10，num)从10个选num个 空间复杂度：O(num)

[xjlgod]

class Solution {

    private boolean[] on = new boolean[10];
    private int[] times = new int[]{1, 2, 4, 8, 1, 2, 4, 8, 16, 32};

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        dfs(res, turnedOn, 0, 0, 0);
        return res;
    }

    public void dfs(List<String> res, int count, int index, int hour, int minute) {
        // 添加进结果
        if (count == 0) {
            String m = String.valueOf(minute);
            if (minute < 10) {
                m = "0" + m;
            }
            res.add(hour + ":" + m);
        }
        // 继续向下深搜遍历
        for (int i = index; i < 10; i++) {
            if (i < 4) {
                int newhour = hour + times[i];
                if (newhour > 11) {
                    continue;
                }
                dfs(res, count - 1, i + 1, newhour, minute);
            } else {
                int newMinute = minute + times[i];
                if (newMinute > 59) {
                    continue;
                }
                dfs(res, count - 1, i + 1, hour, newMinute);
            }
        }
    }
}

[ysy0707]

思路：回溯

class Solution {

    //为了方便计算，分别设置了小时数组和分钟数组
    int[] hours = new int[]{1,2,4,8,0,0,0,0,0,0};
    int[] minutes = new int[]{0,0,0,0,1,2,4,8,16,32};
    List<String> res = new ArrayList<>();

    public List<String> readBinaryWatch(int num) {
        //递归的四个参数分别代表：
        //剩余需要点亮的灯数量，从索引index开始往后点亮灯，当前小时数，当前分钟数
        backtrack(num, 0, 0, 0);
        return res;
    }

    public void backtrack(int num, int index, int hour, int minute){
        //每次进入递归后，先判断当前小时数和分钟数是否符合要求，不符合直接return
        if(hour > 11 || minute > 59)
            return;
        if(num == 0){
            StringBuilder sb = new StringBuilder();
            sb.append(hour).append(':');
            if(minute < 10){
                sb.append('0');
            }
            sb.append(minute);
            res.add(sb.toString());
            return;
        }
        //for循环枚举点亮灯的情况，从index枚举到10，每次枚举，
        //减少一个需要点亮的灯数量num - 1
        //从当前已点亮的灯后面选取下一个要点亮的灯 i + 1
        //在hour中增加当前点亮灯的小时数，如果i大于3，当前灯是分钟灯而不是小时灯，则加上0个小时
        //在minute中增加当前点亮灯的分钟数，如果i没有大于3，当前灯是小时灯而不是分钟灯，则加上0分钟
        for(int i = index; i < 10; i++){
            backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }
    }
}

[hwpanda]

var readBinaryWatch = function(turnedOn) {
  const countBits = (num) => num === 0 ? 0 : countBits(num >> 1) + (num & 1);
  const convertToText = (h, m) => h + ':' + String(m).padStart(2, '0');
  const results = [];

  const hourBits = [];
  const minuteBits = [];
  for (let h = 0; h < 12; h++)
      hourBits[h] = countBits(h);

  for (let m = 0; m < 60; m++)
      minuteBits[m] = countBits(m);

  for (let h = 0; h < 12; h++) {
      for (let m = 0; m < 60; m++) {
          if (hourBits[h] + minuteBits[m] === turnedOn)
              results.push(convertToText(h, m));
      }
  }

  return results;
};

[biancaone]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res = []
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    res.append(f"{h}:{m:02d}")
        return res

[ghost]

题目

401. Binary Watch

思路

DFS

代码

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res = []
        hours = [8,4,2,1]
        minutes = [32,16,8,4,2,1]

        for i in range(0,turnedOn+1):
            hour = set()
            self.get_combinations(hours, i, 0, 0, hour)
            minute = set()
            self.get_combinations(minutes, turnedOn-i, 0, 0, minute)

            for h in hour:
                if h>11 : continue
                for m in minute:
                    if m>59 : continue

                    if m<10:
                        res.append(str(h)+':0'+ str(m))
                    else:
                        res.append(str(h)+':'+ str(m))
        return res

    def get_combinations(self, nums, n, start, curr_sum, res):
        if n == 0:
            res.add(curr_sum)
            return 

        for i in range(start, len(nums)):
            self.get_combinations( nums, n-1, i+1, curr_sum+nums[i], res)

[lilyzhaoyilu]

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for(int h = 0; h < 12; h++){
            for(int m = 0; m < 60; m++){
                if(__builtin_popcount(h) + __builtin_popcount(m) == turnedOn){
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }

        return ans;
    }
};

[m-z-w]

var readBinaryWatch = function(turnedOn) {
    let res = []
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            if (h.toString(2).split('0').join('').length + m.toString(2).split('0').join('').length === turnedOn) {
                res.push(h + ':' + (m < 10 ? '0' : '') + m)
            }
        }
    }
    return res
};

时间：O(1) 空间：O(1)

[liuyangqiQAQ]

回溯递归

class Solution {

    int n;

    List<String> res = new ArrayList<>();
    public List<String> readBinaryWatch(int turnedOn) {
        this.n = turnedOn;
        dfs(0, -1, 0, 0);
        return res;
    }

    public void dfs(int cur, int point, int hour, int min) {
        if(point >= 0) {
            if(point > 5) hour += 1 << (point - 6);
            else min += 1 << point;
            if(hour > 11 || min > 59) return;
        }
        if(cur == n) {
            res.add(hour + ":" + String.format("%02d", min));
            return;
        }
        for (int i = point + 1; i < 10; i++) {
            dfs(cur + 1, i, hour, min);
        }
    }
}

时间度分析:O(2^n) n = 手表的灯总数量。算的也不知道准不准

空间复杂度: O(n)? 递归占用的栈空间不太懂算

二进制暴力

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        //手表只有10个灯。
        int sum = 1 << 10;
        for (int i = 0; i < sum; i++) {
            if(Integer.bitCount(i) != turnedOn) continue;
            //取高四位.所以是10-4
            int hour = i >> 6;
            //低6位
            int min = i & ((1 << 6) - 1);
            if(hour < 12 && min < 60) {
                res.add(String.format("%d:%02d", hour, min));
            }
        }
        return res;
    }
}

时间复杂度: 由于手表的灯数量固定。所以是2^10次幂.O(1)

空间复杂度: O(1)