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

class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        ans = []
        a1 = [1,2,4,8]
        a2 = [1,2,4,8,16,32]

        def get_comb(arr, n, i, ans):
            if n == 0:
                ans.append(-sum(k for k in arr if k<0))
                return
            if i == len(arr): return
            
            arr[i] = -arr[i]
            get_comb(arr, n-1, i+1, ans)
            arr[i] = -arr[i]            
            get_comb(arr, n, i+1, ans)
            
        for i in range(0, num+1):
            if i <= len(a1) and (num-i) <= len(a2): # valid
                hours = []
                get_comb(a1, i, 0, hours)
                minutes = []
                get_comb(a2, num-i, 0, minutes)
                ans += ["%d:%02d" % (h,m) for h in hours if h<12 for m in minutes if m<60]
        return ans                                

本质上是一道组合题目，排列组合都是DFS！上述求组合的时间复杂度是O（2^n）

下面是的是O（n！/C）时间复杂度

class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        ans = []
        a1 = [1,2,4,8]
        a2 = [1,2,4,8,16,32]

        def get_comb(arr, n, pos, ans, sum_val):
            if n == 0:
                ans.append(sum_val)
                return
            for i in range(pos, len(arr)):
                get_comb(arr, n-1, i+1, ans, sum_val+arr[i])
            
            
        for i in range(0, num+1):
            if i <= len(a1) and (num-i) <= len(a2): # valid
                hours = []
                get_comb(a1, i, 0, hours, 0)
                minutes = []
                get_comb(a2, num-i, 0, minutes, 0)
                ans += ["%d:%02d" % (h,m) for h in hours if h<12 for m in minutes if m<60]
        return ans                                

技巧解法：

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

查找表解法：

public class Solution {
    String[][] hour = {{"0"},
            {"1", "2", "4", "8"},
            {"3", "5", "6", "9", "10"},
            {"7", "11"}};
    String[][] minute = {{"00"},
            {"01", "02", "04", "08", "16", "32"},
            {"03", "05", "06", "09", "10", "12", "17", "18", "20", "24", "33", "34", "36", "40", "48"},
            {"07", "11", "13", "14", "19", "21", "22", "25", "26", "28", "35", "37", "38", "41", "42", "44", "49", "50", "52", "56"},
            {"15", "23", "27", "29", "30", "39", "43", "45", "46", "51", "53", "54", "57", "58"},
            {"31", "47", "55", "59"}};

    public List<String> readBinaryWatch(int num) {
        List<String> ret = new ArrayList();
        for (int i = 0; i <= 3 && i <= num; i++) {
            if (num - i <= 5) {
                for (String str1 : hour[i]) {
                    for (String str2 : minute[num - i]) {
                        ret.add(str1 + ":" + str2);
                    }
                }
            }
        }
        return ret;
    }
}