【Day 48 】2023-04-02 - 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[joemonkeylee]

思路

代码

          public IList<string> ReadBinaryWatch(int turnedOn)
        {
            var result = new List<string>();
            for (int hour = 0; hour < 12; hour++)
            {
                for (int minute = 0; minute < 60; minute++)
                {
                    if (CountBits(hour) + CountBits(minute) == turnedOn)
                    {
                        result.Add($"{hour}:{minute:00}");
                    }
                }
            }
            return result;
        }

        public int CountBits(int n)
        {
            int count = 0;
            while (n > 0)
            {
                count += n & 1;
                n >>= 1;
            }
            return count;
        }

复杂度分析

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

[tzuikuo]

思路

回溯

代码

class Solution {
public:
    int hour=0,min=0;
    vector<string> re;
    vector<int> rehour,remin;
    vector<string> readBinaryWatch(int turnedOn) {
        for(int i=0;i<=3;i++) rehour.push_back(0);
        for(int i=0;i<=5;i++) remin.push_back(0);
        recur(turnedOn);

        return re;
    }
    void recur(int turnedOn){
        //cout<<"led="<<turnedOn<<endl;
        if(turnedOn==0){
           string newstr="";
           int hh=hour;
           int mm=min;
           char temp;
           if(hh>=10){
               temp='0'+hh/10;
               newstr.push_back(temp);
               temp='0'+hh%10;
               newstr.push_back(temp);
           }
           else{
               temp='0'+hh%10;
               newstr.push_back(temp);
           }
           newstr.push_back(':');
           if(mm>=10){
               temp='0'+mm/10;
               newstr.push_back(temp);
               temp='0'+mm%10;
               newstr.push_back(temp);
           }
           else{
               newstr.push_back('0');
               temp='0'+mm%10;
               newstr.push_back(temp);
           }
           if(find(re.begin(),re.end(),newstr)==re.end()) re.push_back(newstr);
           //cout<<newstr<<endl;
           return; 
        }
        else{
            for(int i=0;i<=3;i++){
                if(rehour[i]==1) continue;
                hour+=pow(2,i);
                if(hour>=12){
                    hour-=pow(2,i);
                    break;
                }
                else{
                    rehour[i]=1;
                    recur(turnedOn-1);
                    hour-=pow(2,i);
                    rehour[i]=0;
                }
            }
            for(int i=0;i<=5;i++){
                if(remin[i]==1) continue;
                min+=pow(2,i);
                if(min>=60){
                    min-=pow(2,i);
                    break;
                }
                else{
                    remin[i]=1;
                    recur(turnedOn-1);
                    min-=pow(2,i);
                    remin[i]=0;
                }

            }
        }
        return;

    }
};

复杂度分析 -时间 O(N!) N<=10

[aoxiangw]

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

O(1), O(1)

[yingchehu]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        hour = collections.defaultdict(list)
        mins = collections.defaultdict(list)

        for i in range(12):
            h, sum =i, 0
            for n in range(3, -1, -1):
                if h >= 2 ** n:
                    h -= 2 ** n
                    sum += 1
            hour[sum].append("%d" % i)

        for i in range(60):
            m, sum =i, 0
            for n in range(5, -1, -1):
                if m >= 2 ** n:
                    m -= 2 ** n
                    sum += 1
            mins[sum].append("%02d" % i)

        ans = []
        for n in range(turnedOn+1):
            for h in hour[n]:
                for m in mins[turnedOn - n]:
                    ans.append(h + ":" + m)
        return ans

[FlipN9]

/**
    Approach 1: 枚举所有的 h 和 m, 计算他们的 bitCount, 看位数和是否等于 turnedOn
                12 * 60 = 720 种组合
    TC: O(1)    SC: O(1)
*/
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) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(h).append(":");
                    sb.append(m < 10 ? "0" : "").append(m);
                    res.add(new String(sb));
                }
            }
        }
        return res;
    }
}

/**
    Approach 2: 枚举 2^10 = 1024 种灯的开闭组合
                高 4 位: 小时     低 6 位: 分钟, 
                若小时和分钟的值 均在合规范围内, 并且 二进制中 1 的个数为 turnedOn, 加入 res
    TC: O(1)    SC: O(1)            
*/
class Solution1 {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 1024; i++) {
            int h = i >> 6, m = i & 63;
            if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
                StringBuilder sb = new StringBuilder();
                sb.append(h).append(":");
                sb.append(m < 10 ? "0" : "").append(m);
                res.add(new String(sb));
            }
        }
        return res;
    }
}

[NorthSeacoder]

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    const res = [];
    const time = new Array(10).fill(0); // 初始化表示时间的数组
    const dfs = (nums, ons) => { 
        if (nums === 0) {   // 如果灯的数量已经全部确定
            // 计算小时数和分钟数
            const hour = time[0] + 2 * time[1] + 4 * time[2] + 8 * time[3];
            const min = time[4] + 2 * time[5] + 4 * time[6] + 8 * time[7] + 16 * time[8] + 32 * time[9];
            // 判断是否合法，是则将时间字符串推入结果数组
            if (hour < 12 && min < 60) {
                res.push(`${hour}:${min < 10 ? '0' + min : min}`);
            }
        }
        // 否则，继续搜索
        for (let i = ons; i < time.length; i++) {
            time[i] = 1;    // 将灯的状态置为已量
            dfs(nums - 1, i + 1);   // 递归搜索剩余灯数，从下一个未量的灯开始
            time[i] = 0;    // 清空当前灯的状态，回溯到上一层
        }
    };
    dfs(turnedOn, 0);   // 从 0 开始搜索，搜索的灯数为 turnedOn 个
    return res;
};

• TC:O(1)
• SC:O(1)

[zol013]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        def possible_number(count, minute = False):
            if count == 0:
                return [0]
            if minute:
                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 = set()
        for i in range(min(4, turnedOn + 1)):
            for a in possible_number(i):
                for b in possible_number(turnedOn - i, True):
                    ans.add(str(a)+':'+str(b).rjust(2,"0"))
        return list(ans)

[csthaha]

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    // 枚举所有时间转成二进制、然后 计算符合条件的 1个数 === turnedOn
    const ans = [];
    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
            ) {
                ans.push(i + ":" + (j < 10 ? "0" : "") + j);
            }
        }
    }
    return ans;
};

[Abby-xu]

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

[kangliqi1]

class Solution: def readBinaryWatch(self, num: int) -> List[str]: return [str(a) + ":" + str(b).rjust(2, '0') for a in range(12) for b in range(60) if (bin(a)+bin(b)).count('1') == num]

[linlizzz]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        def possible_number(count, minute=False):
            if count == 0: return [0]
            if minute:
                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 = set()
        for i in range(min(4, turnedOn + 1)):
            for a in possible_number(i):
                for b in possible_number(turnedOn - i, True):
                    ans.add(str(a) + ":" + str(b).rjust(2, '0'))
        return list(ans)

[harperz24]

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(str(h) + ':' + ("0" if m < 10 else "") + str(m))
        return res

        # enumeration
        # time: O(1) 12*60
        # space: O(1)

[Hughlin07]

public class Solution {

public List<String> readBinaryWatch(int num) {
    List<String> res = new ArrayList<>();
    int[] nums1 = new int[]{8, 4, 2, 1}, nums2 = new int[]{32, 16, 8, 4, 2, 1};
    for(int i = 0; i <= num; i++) {
        List<Integer> list1 = generateDigit(nums1, i);
        List<Integer> list2 = generateDigit(nums2, num - i);
        for(int num1: list1) {
            if(num1 >= 12) continue;
            for(int num2: list2) {
                if(num2 >= 60) continue;
                res.add(num1 + ":" + (num2 < 10 ? "0" + num2 : num2));
            }
        }
    }
    return res;
}

private List<Integer> generateDigit(int[] nums, int count) {
    List<Integer> res = new ArrayList<>();
    generateDigitHelper(nums, count, 0, 0, res);
    return res;
}

private void generateDigitHelper(int[] nums, int count, int pos, int sum, List<Integer> res) {
    if(count == 0) {
        res.add(sum);
        return;
    }

    for(int i = pos; i < nums.length; i++) {
        generateDigitHelper(nums, count - 1, i + 1, sum + nums[i], res);    
    }
}

}

[snmyj]

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

[Lydia61]

401. 二进制手表

思路

暴力搜索

代码

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

复杂度分析

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

[wangzh0114]

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

• TC:O(1)
• SC:O(1)

[bookyue]

TC: O(24*60)
OC: O(1)

    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 (bitCount(i) + bitCount(j) == turnedOn)
                    res.add(i + ":" + (j <= 9 ? "0" + j : j));
        }

        return res;
    }

    private int bitCount(int num) {
        int cnt = 0;
        while (num != 0) {
            num = num & (num - 1);
            cnt++;
        }

        return cnt;
    }

[chocolate-emperor]

class Solution {
public:
    vector<string>res;
    int led[10]={1,2,4,8,1,2,4,8,16,32};//10个中拿turendOn个，求组合数
    void recursion(int hour,int minute,int index,int turnedOn){
        if(turnedOn==0){
            string m = to_string(minute);
            if(m.length()==1)  m = "0" + m;
            res.emplace_back(to_string(hour) +":"+m);
            //printf("%d %d \n",hour,minute);
            return;
        }
        //index之后才是可选择的范围，之前是已选择的范围
        for(int i=index;i<10;i++){
            if(i<4){
                if(hour+led[i]<=11){
                    hour+=led[i];
                    recursion(hour,minute,i+1,turnedOn-1);
                    hour-=led[i];
                }
            }else{
                if(minute+led[i]<=59){
                    minute+=led[i];
                    recursion(hour,minute,i+1,turnedOn-1);
                    minute-=led[i];
                }
            }

        }
    }
    vector<string> readBinaryWatch(int turnedOn) {
        if(turnedOn<9) {
            bool vis[10] ={false};
            recursion(0,0,0,turnedOn);
        }

        return res;
    }
};
``

[RestlessBreeze]

code

class Solution {
public:

    int cnt(int num)
    {
        int res = 0;
        while (num != 0)
        {
            num = num & (num - 1);
            res++;
        }
        return res;
    }

    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> res;
        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 60; j++)
            {
                if (cnt(i) + cnt(j) == turnedOn)
                {
                    res.push_back(to_string(i) + ":" + (j < 10 ? "0" + to_string(j) : to_string(j)));
                }
            }
        }
        return res;
    }
};

[X1AOX1A]

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        return [str(a) + ":" + str(b).rjust(2, '0')   \
        for a in range(12) for b in range(60) \
        if (bin(a)+bin(b)).count('1') == num]

[liuajingliu]

401. 二进制手表

解题思路

枚举时分

代码实现

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)$

[JasonQiu]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        def dfs(turnedOn, hours, result):
            if hours > turnedOn:
                return
            for h in combinations([1, 2, 4, 8], hours):
                hour = sum(h)
                if hour < 12:
                    for m in combinations([1, 2, 4, 8, 16, 32], turnedOn - hours):
                        minute = sum(m)
                        if minute < 60:
                            result.append("%d:%02d" % (hour, minute))
            dfs(turnedOn, hours + 1, result)

        result = []
        dfs(turnedOn, 0, result)
        return result

Time: O(1) Space: O(1)

[FireHaoSky]

思路：回溯法

代码：python

def getCnt(x):
    ans,i=0,x
    while i >0:
        ans += 1
        i -= lowbit(i)
    return ans

def lowbit(x):
    return x & -x

map = defaultdict(list)
for h in range(12):
    for m in range(60):
        tot = getCnt(h) + getCnt(m)
        map[tot].append(f"{h}:{m:02d}")

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

复杂度分析：

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

[Jetery]

class Solution {
public:

    int count(int n) {
        int ret = 0;
        while (n) {
            n = n & (n - 1);
            ret++;
        }
        return ret;
    }

    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int i = 0; i < 12; i++) 
            for (int j = 0; j < 60; j++) {
                if (count(i) + count(j) == turnedOn) {
                    string h = to_string(i);
                    string min = to_string(j);
                    string temp = h + ":" + (j < 10 ? "0" + min : min);
                    ans.push_back(temp);
                }
            }

        return ans;
    }
};

[lp1506947671]

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        return [str(a) + ":" + str(b).rjust(2, '0') for a in range(12) for b in range(60) if (bin(a)+bin(b)).count('1') == num]

[AstrKing]

代码

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;
    }
}

[Meisgithub]

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;
    }
};

[jmaStella]

思路

枚举，共2……0 = 1024种可能 hour前4位，minute后6位 check condition：

1. hour <12 && min<60
2. 时间代表的binary number的1的个数 = turnon

代码

public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();
        // 2^10 = 1024 种灯的开闭组合
        for(int i=0; i< 1024; i++){
            int hour = i>>6;
            int min = i&63;

            if(hour <12 && min <60 && Integer.bitCount(i) == turnedOn){
                if(min < 10){
                    result.add(hour+":0"+min);
                }else{
                    result.add(hour+":"+min);
                }

            }
        }
        return result;
    }

复杂度

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

[Fuku-L]

代码

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)

[chanceyliu]

代码

function readBinaryWatch(turnedOn: number): string[] {
  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)

[kofzhang]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        times = [8,4,2,1,32,16,8,4,2,1]
        res = []
        def helper(idx,h,m,cnt):
            if cnt == turnedOn:
                res.append("%d:%02d"%(h,m))
                return

            if idx==len(times):
                return
            if idx<=3:
                if h+times[idx]<=11:
                    helper(idx+1,h+times[idx],m,cnt+1)
                helper(idx+1,h,m,cnt)
            else:
                if m+times[idx]<=59:
                    helper(idx+1,h,m+times[idx],cnt+1)
                helper(idx+1,h,m,cnt)
        helper(0,0,0,0)
        return res

[JiangyanLiNEU]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        output = []
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:  # Check if the number of set bits in hours and minutes equals the target number
                    output.append(f"{h}:{m:02d}")  # Add the valid combination of hours and minutes to the output list
        return output