azl397985856 commented 2 years ago

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

ray-hr commented 2 years ago

代码

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

zwx0641 commented 2 years ago

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

    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j < 60; ++j) {
            if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                ans.add(i + ":" + (j < 10 ? "0" : "") + j);
            }
        }
    }
    return ans;
}

}

wangzehan123 commented 2 years ago

题目地址(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)$

feifan-bai commented 2 years ago

思路

二进制

代码

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans = list()
        for i in range(1024):
            # 用位运算取高4位和低6位
            h, m = i >> 6, i & 0x3f
            if h < 12 and m < 60 and bin(i).count('1') == turnedOn:
                ans.append(f"{h}:{m:02d}")
        return ans

复杂度分析

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

laofuWF commented 2 years ago

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

zhy3213 commented 2 years ago

思路

排列组合

代码

    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res=[]
        for i in combinations(range(10),turnedOn):
            h,m=0,0
            for j in i:
                if j<4:
                    h+=1<<j
                else:
                    m+=1<<(j-4)
            if h<=11 and m<=59:
                res.append(str(h)+':'+(str(m) if m>9 else '0'+str(m)))
        return res

ZacheryCao commented 2 years ago

Idea

Backtrcking

Code

class Solution {
public:
    vector<int> hours = {1, 2, 4, 8};
    vector<int> minutes = {1, 2, 4, 8, 16, 32};
    vector<string> ans;
    vector<string> readBinaryWatch(int turnedOn) {
        backtracking(turnedOn, make_pair(0, 0), 0);
        return ans;
    }
    void backtracking(int turnedOn, pair<int, int> cur, int start){
        if(turnedOn == 0){
            ans.push_back(to_string(cur.first) + (cur.second < 10 ?  ":0" : ":") + to_string(cur.second));
            return;
        }
        for(int i = start; i<hours.size()+minutes.size(); i++){
            if(i < hours.size()){
                cur.first += hours[i];
                if(cur.first < 12) backtracking(turnedOn - 1, cur, i+1);
                cur.first -= hours[i];
            }else{
                cur.second += minutes[i - hours.size()];
                if(cur.second < 60) backtracking(turnedOn - 1, cur, i+1);
                cur.second -= minutes[i - hours.size()];
            }
        }
    }
};

Complexity:

Time: (10!/(k!(10-k)!) Space: (10!/(k!(10-k)!)

zhangzz2015 commented 2 years ago

思路

采用回溯方法，对所有灯的情况进行遍历，建立遍历树，树的高度为灯的个数。通过level控制，同时更新hour和min。对于满足条件的情况进行输出。时间复杂度为O(2^n)，空间复杂度O(n)，此处n为level的高度。

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
    //  
        vector<int>  num={1,2,4, 8, 1, 2 ,4, 8, 16, 32};         
        vector<string> ret;         
        int min =0; 
        int hour =0; 
        dfs(0, num, min, hour, 0,  turnedOn, ret);         
        return ret; 
    }

    void dfs(int start, vector<int>& num, int& min, int& hour,  int level, int turnedOn,  vector<string>& ret)
    {
        if(level == turnedOn) // we find one result.  
        {
            string tmp; 
            ret.push_back(timeToS(hour, min)); 
            return;     
        }
        for(int i=start; i<num.size(); i++)
        {
            if(i<=3) // hour
                hour += num[i];
            else
                min += num[i]; 
            if(hour<12 && min<60)
                dfs(i+1, num, min, hour, level+1, turnedOn, ret); 
            if(i<=3)
                hour -=num[i];
            else
                min -=num[i]; 
        }                
    }
    string timeToS(int hour, int min)
    {
        string tmp; 
        tmp +=to_string(hour); 
        tmp +=':'; 
        if(min<10)
        {
            tmp +='0'; 
            tmp +=to_string(min); 
        }
        else
            tmp +=to_string(min);                 
        return tmp; 
    }
};

rzhao010 commented 2 years ago

Thoughts DFS+ backtrack

Code


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

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

    private void dfs(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++) {
            dfs(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }
    }
}

Complexity Time: O(C10num) Space: O(n)

mannnn6 commented 2 years ago

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

ZhangNN2018 commented 2 years ago

class Solution(object):
    def readBinaryWatch(self, turnedOn):
        """
        :type turnedOn: int
        :rtype: List[str]
        """
        table = {0:[],1:[],2:[],3:[],4:[],5:[],6:[]}
        ret = []
        for i in range(60):
            table[bin(i).count('1')].append(i)
        for hour in range(12):
            key = turnedOn-bin(hour).count('1')
            if key < 0 or key > 6 : continue
            for minute in table[key]:
                ret.append(str(hour)+':'+('0' if minute<10 else '')+ str(minute))
        return ret

CoreJa commented 2 years ago

思路

老题，给二进制手表亮灯个数，求当前可能的时间，思路就两种，根据钟面时间搜索；遍历$60*12$的空间(每一分钟)

遍历：遍历所有可能的时间，分别算时和分的二进制中有多少个1，个数符合turnedOn就是一个答案。复杂度$O(60121)=O(1)$。
遍历：思路同上，一行搞定。
built-in组合：列出时钟的刻度，排列组合，校验结果是否符合要求。复杂度$O(C_{10}^n)=O(1)$。
回溯：列出时钟刻度，递归搜索刻度，递归参数要传入深度、当前下标，小时和分钟。复杂度$O(C_{10}^n)=O(1)$

代码

class Solution:
    def readBinaryWatch1(self, turnedOn: int) -> List[str]:
        def number(n):
            cnt = 0
            while n:
                n &= n - 1
                cnt += 1
                return cnt

        ans = []
        for i in range(0, 12):
            for j in range(0, 60):
                if number(i) + number(j) == turnedOn:
                    ans += ["{}:{:02}".format(i, j)]
        return ans

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

    def readBinaryWatch3(self, turnedOn: int) -> List[str]:
        nums = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]
        ans = []
        for idxs in combinations(range(10), turnedOn):
            h, m = 0, 0
            for idx in idxs:
                if idx < 4:
                    h += nums[idx]
                else:
                    m += nums[idx]
            if 0 <= h < 12 and 0 <= m < 60:
                ans += ["{}:{:02}".format(h, m)]
        return ans

    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        nums = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]
        ans = []

        def search(dep, i, h, m):
            if dep == 0:
                if 0 <= h < 12 and 0 <= m < 60:
                    ans.append("{}:{:02}".format(h, m))
            else:
                for idx in range(i, 10):
                    if idx < 4:
                        search(dep - 1, idx + 1, h + nums[idx], m)
                    else:
                        search(dep - 1, idx + 1, h, m + nums[idx])

        search(turnedOn, 0, 0, 0)
        return ans

xinhaoyi commented 2 years ago

401. 二进制手表

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

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

小时不会以零开头：

例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。分钟必须由两位数组成，可能会以零开头：

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

思路一

直接暴力循环求出所有时间对应的灯数，建立一张静态表，把灯数作为key值，存起来要用的时候直接取出来就好

代码

class Solution {    
    // 暴力循环
    // 同时建一张静态表去存各个灯数对应的时间串
    // 注意使用 static 修饰，确保打表数据只会被生成一次
    static Map<Integer, List<String>> map = new HashMap<>();
    static {
        for (int h = 0; h <= 11; h++) {
            for (int m = 0; m <= 59; m++) {
                //手动写一个求对应二进制有多少个1 的函数或者用Integer.bitCount()也行
                int totalBitOne = 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);
            }
        }
    }
    //方法参考https://leetcode-cn.com/problems/binary-watch/solution/gong-shui-san-xie-jian-dan-ti-xue-da-bia-gwn2/
    //求1的位数
    static int getCnt(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)){
            ans++;  
        } 
        return ans;
    }
   //x 与 -x 按位取与，求得x最低位1的值
    static int lowbit(int x) {
        return x & -x;
    }
    public List<String> readBinaryWatch(int t) {
        return map.getOrDefault(t, new ArrayList<>());
    }
}

复杂度分析

时间复杂度：O(1)

空间复杂度：O(n)

a244629128 commented 2 years ago


var readBinaryWatch = function(num) {
  const times = [];
  for (let h = 0; h < 12; h++) {
    for (let m = 0; m < 60; m++) {
      const hOnes = h ? h.toString(2).match(/1/g).length : 0;
      const mOnes = m ? m.toString(2).match(/1/g).length : 0;
      if (hOnes + mOnes === num) {
        times.push(`${h}:${m < 10 ? `0${m}` : m}`);
      }
    }
  }
  return times;
};

hdyhdy commented 2 years ago

思路 bit 运算: 把时分的灯放在一起 10个灯中选择num个(回溯算法来实现) 选择结果中在过滤 fmt.Sprintf() 拼装结果

func readBinaryWatch(num int) []string {
    res := []string{}
    // 假想 10个 bit 灯 index  --->       h1=>0   h2=>1   h4=>2   h8=>3   m1=>4   m2=>5   m4=>6   m8=>7   m16=>8   m32=>9
    //start = 0 回溯从bit 的 index = 0 开始, 10 代表时分灯的总数, 相当于10个灯中选中num个亮的灯
    backTrack(0,10,num,[]int{},&res)
    return res
}
//backTrack 回溯算法 cap 灯的总数量, target 目标亮灯的数量 path []int  亮灯的index集合(记录回溯的路径) res 指针返回结果
func backTrack(start,cap,target int,path []int,res *[]string){
    if len(path) == target { //选择亮灯的数量达到target
        min,hour := 0,0
        for _,v := range path{
            if v >= 4 { // 如果灯的下表超过3 则表示这些灯是 minute的灯
                min += 1<< (v-4)
            }else{//如果 灯的index 小于4 表示是 hour的灯亮
                hour += 1<< v
            }
        }
        if min < 60 && hour < 12 { //排除不符合规则的,判断min hour 值是否有效
            *res = append(*res,fmt.Sprintf("%d:%02d",hour,min))  //格式化拼接成字符串
        }
        path = []int{}  //重置 回溯的path
        return
    }
    for i:=start;i<cap;i++{
        path = append(path,i)
        backTrack(i+1,cap,target,path,res)//注意这里是 i+1
        path = path[:len(path)-1] //对 path 进行rollback
    }
}

Tesla-1i commented 2 years ago

class Solution {
public:
    vector<int> hours = {1, 2, 4, 8};
    vector<int> minutes = {1, 2, 4, 8, 16, 32};
    vector<string> ans;
    vector<string> readBinaryWatch(int turnedOn) {
        backtracking(turnedOn, make_pair(0, 0), 0);
        return ans;
    }
    void backtracking(int turnedOn, pair<int, int> cur, int start){
        if(turnedOn == 0){
            ans.push_back(to_string(cur.first) + (cur.second < 10 ?  ":0" : ":") + to_string(cur.second));
            return;
        }
        for(int i = start; i<hours.size()+minutes.size(); i++){
            if(i < hours.size()){
                cur.first += hours[i];
                if(cur.first < 12) backtracking(turnedOn - 1, cur, i+1);
                cur.first -= hours[i];
            }else{
                cur.second += minutes[i - hours.size()];
                if(cur.second < 60) backtracking(turnedOn - 1, cur, i+1);
                cur.second -= minutes[i - hours.size()];
            }
        }
    }
};

Toms-BigData commented 2 years ago

【Day 48】401. 二进制手表

思路

回溯

golang代码

var ans []string
var arr = []int{8, 4, 2, 1, 32, 16, 8, 4, 2, 1}

func readBinaryWatch(turnedOn int) []string {
    ans  =[]string{}
    backtrack(turnedOn, 0, 0, 0)
    return ans
}

func backtrack(turnedOn, H, M, k int) {
    if turnedOn == 0{
        Hs, Ms := strconv.Itoa(H), strconv.Itoa(M)
        if M <10{
            Ms = "0" + Ms
        }
        ans = append(ans, Hs+":"+Ms)
        return
    }
    for i:=k; i<10;i++{
        h,m:=H,M
        if i<4{
            h+=arr[i]
        }else {
            m+=arr[i]
        }

        if h < 12 && m <60{
            backtrack(turnedOn-1, h, m, i+1)
        }
    }
}

复杂度

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

watchpoints commented 2 years ago

https://leetcode-cn.com/problems/binary-watch/
class Solution {

    /**
     * 全局变量记录结果
     */
    private List<String> results = new ArrayList<>();

    /**
     * 长度为10的数组，标记元素是否选中。0表示没有选中，不亮，1表示选中，灯亮
     */
    private int[] status = new int[10];

    /**
     * 思路：
     * 1、本质是组合问题，选出turnedOn个元素；
     * 2、将选出的结果转换为字符串、
     * 实现：
     * 1、所有的灯作为一个数组：前4个元素，表示小时的1、2、4、8.后6位表示分钟的1、2、4、8、16、32。
     * 2、从数组中选出turnedOn个元素表示亮，初始默认都是未选中，用0表示。
     * 3、增加一个计数器，表示已经选择的数量。
     * 4、回溯结束条件：选中的数量等于turnedOn。
     * 5、完成数据转换，加入结果集合。
     * 注意：
     * 1、注意剪枝，剩下的数量必须满足大于等于turnedOn
     *
     * @param turnedOn 灯亮的个数
     * @return 所有的组合结果
     */
    public List<String> readBinaryWatch(int turnedOn) {
        dfs(0, 0, turnedOn,0,0);
        return results;
    }

    /**
     * 从包含startIndex开始的范围，选取turnedOn个元素。回溯获取所有的结果。
     *
     * @param selectedNum 已经选择的数量
     * @param startIndex  开始选中的索引
     * @param turnedOn    目标选择的数量
     */
    private void dfs(int selectedNum, int startIndex, int turnedOn,int hours,int minus) {
        if (selectedNum >= turnedOn) {
            String temp = getTimeString();
            if (!temp.isEmpty() && !results.contains(temp)) {
                results.add(temp);
            }
            return;
        }

        for (int i = startIndex; i <= status.length - (turnedOn - selectedNum); i++) {
            status[i] = 1;
            int hoursTemp = 0;
            int minusTemp = 0;
            if (i <= 3) {
                hoursTemp = (int) Math.pow(2, i);
            }else {
                minusTemp = (int)Math.pow(2, i - 4);
            }
            if (hours+hoursTemp > 11 || minus+minusTemp > 59){
                status[i] = 0;
                continue;
            }
            dfs(selectedNum + 1, i + 1, turnedOn, hours+hoursTemp, minus+minusTemp);
            status[i] = 0;
        }
    }

    /**
     * 将选中的状态转换为时间的字符显示
     *
     * @return 选中的状态转换为时间的字符显示
     */
    private String getTimeString() {
        int hours = 0;
        int minus = 0;

        for (int i = 0; i <= 3; i++) {
            if (status[i] == 1) {
                hours += Math.pow(2, i);
            }
        }
        for (int i = 4; i <= 9; i++) {
            if (status[i] == 1) {
                minus += Math.pow(2, i - 4);
            }
        }

        if (hours > 11 || minus > 59) {
            return "";
        }

        String minusString;
        if (minus < 10) {
            minusString = "0" + minus;
        } else {
            minusString = String.valueOf(minus);
        }

        return hours + ":" + minusString;
    }
}

c++

https://leetcode-solution.cn/91?tab=sign
class Solution {
public:
vector<string> readBinaryWatch(int turnedOn) {
//  
    vector<int>  num={1,2,4, 8, 1, 2 ,4, 8, 16, 32};         
    vector<string> ret;         
    int min =0; 
    int hour =0; 
    dfs(0, num, min, hour, 0,  turnedOn, ret);         
    return ret; 
}

void dfs(int start, vector<int>& num, int& min, int& hour,  int level, int turnedOn,  vector<string>& ret)
{
    if(level == turnedOn) // we find one result.  
    {
        string tmp; 
        ret.push_back(timeToS(hour, min)); 
        return;     
    }
    for(int i=start; i<num.size(); i++)
    {
        if(i<=3) // hour
            hour += num[i];
        else
            min += num[i]; 
        if(hour<12 && min<60)
            dfs(i+1, num, min, hour, level+1, turnedOn, ret); 
        if(i<=3)
            hour -=num[i];
        else
            min -=num[i]; 
    }                
}
string timeToS(int hour, int min)
{
    string tmp; 
    tmp +=to_string(hour); 
    tmp +=':'; 
    if(min<10)
    {
        tmp +='0'; 
        tmp +=to_string(min); 
    }
    else
        tmp +=to_string(min);                 
    return tmp; 
}
};

zwmanman commented 2 years ago

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]

Flower-F commented 2 years ago

解题思路

枚举

代码

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

复杂度

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

freesan44 commented 2 years ago

思路

通过枚举遍历有可能出现的可能性

关键点

代码

语言支持：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)$

tongxw commented 2 years ago

思路

模拟

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<>();
        for (int hour = 0; hour <= 11; hour++) {
            for (int minute = 0; minute <= 59; minute++) {
                int leds = (hour << 6) | minute;
                if (turnedOn == Integer.bitCount(leds)) {
                    ans.add(String.format("%d:%02d", hour, minute));
                }
            }
        }

        return ans;
    }
}

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

wxj783428795 commented 2 years ago

思路

枚举所有可能

代码

var readBinaryWatch = function (turnedOn) {
    let times = [];
    const countNumberOfOne = (number) => {
        return number.toString(2).split('').filter(char => char === '1').length;
    }
    for (let i = 0; i < 12; i++) {
        for (let j = 0; j < 60; j++) {
            let hourCount = countNumberOfOne(i);
            let minuteCount = countNumberOfOne(j);
            if (hourCount + minuteCount === turnedOn) {
                let time = `${i}:${j.toString().padStart(2, '0')}`
                times.push(time)
            }
        }
    }
    return times;
};

复杂度分析：

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

Zhang6260 commented 2 years ago

JAVA版本

主要使用dfs的方式进行搜索。

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> list = new ArrayList<>();
        fun(turnedOn,new StringBuffer(""),list);
        return list;
    }

     //这里规定分钟部分为前6个  小时为前4个
    public  void fun(int n,StringBuffer index,List<String> list){
        if(n>=9||n<0||index.length()>10){
            return;
        }
        if(n==0){
//            System.out.println(index);
            //这里还要进行赛选一部分
            StringBuffer sb = new StringBuffer(index.toString());
            for(int i=sb.length();i<10;i++){
                sb.append('0');
            }

            String min =sb.substring(0,6);
            String hour = sb.substring(6);
            int m = get(min);
            int h = get(hour);
            if(m>=60||h>=12){
                return;
            }
            if(m<10){
                list.add(h+":0"+m);
            }else{
                list.add(h+":"+m);
            }

            return;
        }
        index.append("1");
        int temp = index.length();
        fun(n-1,index,list);

        index.deleteCharAt(temp-1);
        index.append('0');
        fun(n,index,list);
        index.deleteCharAt(temp-1);

    }

    public  int get(String t){
        int res =0;
        for(int i=0;i<t.length();i++){
            if(t.charAt(i)=='1'){
                res+=Math.pow(2,i);
            }
        }
        return  res;
    }
}

junbuer commented 2 years ago

思路

二进制枚举
- 手表总共有10个LED灯可以用，10为2进制码表示灯的亮灭情况，即有 $2^{10}=1024$ 种可能
- 枚举所有可能，统计10位二进制中1的数量。将等于 turnedOn 的二进制，取出高四位作为小时数h，取出低六位作为分钟数m，检查h和m是否合法

代码

class Solution(object):
    def readBinaryWatch(self, turnedOn):
        """
        :type turnedOn: int
        :rtype: List[str]
        """
        ans = []
        for i in range(1024):
            h, m = i >> 6, i & 63
            if h < 12 and m < 60 and bin(i).count("1") == turnedOn:
                ans.append("%d:%02d" % (h, m))
        return ans

复杂度分析

时间复杂度：$O(1)$，每次运行次数与输入无关
空间复杂度：$O(1)$

L-SUI commented 2 years ago


/**
 * @param {number} num
 * @return {string[]}
 */
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;
};

HWFrankFung commented 2 years ago

Codes

var readBinaryWatch = function(num) {
  const arr = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]
  const result = []
  backTrace(arr, num, 0, [0, 0], result)
  return result
};

var backTrace = function(arr, num, start, temp, result) {
  if (temp[0] >= 12 || temp[1] >= 60) return
  if (num === 0) {
    result.push(`${temp[0]}:${padding(temp[1])}`)
    return
  }

  for (let i = start; i < arr.length; i++) {
    if (i <= 3) {
      temp[0] = temp[0] + arr[i]
    } else {
      temp[1] = temp[1] + arr[i]
    }
    num = num - 1
    backTrace(arr, num, i + 1, temp, result)
    if (i <= 3) {
      temp[0] = temp[0] - arr[i]
    } else {
      temp[1] = temp[1] - arr[i]
    }
    num = num + 1
  }
}

var padding = function(num) {
  return num < 10 ? `0${num}` : num
}

AlduinLeung commented 2 years ago

const count1 = n => {
    let count = 0;
    while (n !== 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
};

const readBinaryWatch = turnedOn => {
    const res = [];
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            if (count1(h) + count1(m) === turnedOn) {
                res.push(`${h}:${m < 10 ? '0' : ''}${m}`);
            }
        }
    }
    return res;
};

zjsuper commented 2 years ago

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

LannyX commented 2 years ago

思路

backtrack

代码


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 turnedOn) {
        backtrack(0, 0, 0, turnedOn);
        return res;
    }

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

Today-fine commented 2 years ago

枚举每时每分都二进制数来获得结果


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; // 用位运算取出高 4 位和低 6 位
            if (h < 12 && m < 60 && __builtin_popcount(i) == turnedOn) {
                ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
            }
        }
        return ans;
    }
};

yan0327 commented 2 years ago

思路：暴力枚举

func readBinaryWatch(turnedOn int) []string {
    out := []string{}
    for i:=uint8(0);i<12;i++{
        for j:=uint8(0);j<60;j++{
            if bits.OnesCount8(i) + bits.OnesCount8(j) == turnedOn{
                out = append(out,fmt.Sprintf("%d:%02d",i,j))
            }
        }
    }
    return out
}

时间复杂度O（N*M）空间复杂度O（1）

callmeerika commented 2 years ago

思路

枚举

代码

var readBinaryWatch = function (turnedOn) {
    let arr = [];
    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) {
          arr.push(i + ':' + (j < 10 ? '0' + j : j));
        }
      }
    }
    return arr;
  };

复杂度

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

Tao-Mao commented 2 years ago

Code

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

falconruo commented 2 years ago

思路: 穷举时针和分针，当时针的LED的个数 + 分针的LED的个数等于给定的led数目turnedOn时，满足条件

复杂度分析:

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

代码(C++):

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 (count(i) + count(j) == turnedOn) {
                    string s = "";
                    convert(i, s, 0);
                    s.push_back(':');
                    convert(j, s, 1);
                    res.push_back(s);
                }
            }

        return res;
    }
private:
    int count(int n) {
        int num = 0;
        vector<int>leds = {32, 16, 8, 4, 2, 1};

        int i = 0;
        for (auto i : leds)
            if (n >= i) {
                n -= i;
                ++num;
            }
        return num;
    }

    void convert(int n, string& s, int flag) {
        if (n < 10) {
            if (flag)
                s.push_back('0');
            s.push_back('0' + n);
        } else {
            s.push_back('0' + n / 10);
            s.push_back('0' + n % 10);
        }
    }
};

didiyang4759 commented 2 years ago

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

luhnn120 commented 2 years ago

思路

枚举

代码

var new21Game = function(N, K, W) {
    let dp = new Array(N+1).fill(0);
    let sumArr = new Array(N+1).fill(0);
    dp[0]=1;
    for(let n=1;n<=N;n++){
        let left = Math.max(0,n-W);
        let right = Math.min(n-1,K-1);
        let p=0
        for(let i=left;i<=right;i++){
            p+=dp[i]/W;
        }
        dp[n]=p;
        sumArr[n]=sumArr[n-1]+p;
    }
    let result = 0;
    for(let i=K;i<=N;i++){
        result+=dp[i]
    }
    return result;
};

复杂度

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

kbfx1234 commented 2 years ago

401. 二进制手表

// 1-28 cpp
class Solution {
private:
    int h[10] = {1,2,4,8,0,0,0,0,0};
    int m[10] = {0,0,0,0,1,2,4,8,16,32};

    void dfs(vector<string>& res, int lighton, int idx, int hour, int minute) {
        if (hour > 11 || minute > 59){
            return;
        }
        else if (lighton == 0) {
            // "10:2应该改成10:02"
            string cur = to_string(hour) + ":" + (minute < 10 ? "0" + to_string(minute) : to_string(minute));
            res.push_back(cur);
            return;
        }
        for (int i = idx; i < 10; i++) {
            dfs (res, lighton - 1, i + 1, hour + h[i], minute + m[i]);
        }
    }

public:
    vector<string> readBinaryWatch(int turnedOn) {
        if (turnedOn >= 9) return {};
        if (turnedOn <= 0) return {"0:00"};
        vector<string> ans;
        dfs(ans, turnedOn, 0, 0, 0);
        return ans;
    }
};

ywang525 commented 2 years ago

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

JudyZhou95 commented 2 years ago

代码

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

xuhzyy commented 2 years ago

思路

回溯

代码

class Solution(object):
    def readBinaryWatch(self, turnedOn):
        """
        :type turnedOn: int
        :rtype: List[str]
        """
        if turnedOn == 0:
            return ['0:00']

        if turnedOn > 8:
            return []

        hour = [1, 2, 4, 8]
        minute = [1, 2, 4, 8, 16, 32]
        res = []

        def backtrack(res, path, start, n, nums, maxvalue):
            if n == 0:
                if sum(path) <= maxvalue:
                    res.append(sum(path))
                return res

            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(res, path, i+1, n-1, nums, maxvalue)
                path.pop()

            return res

        for i in range(min(4, turnedOn+1)):
            j = turnedOn - i
            res1 = backtrack([], [], 0, i, hour, 11)
            res2 = backtrack([], [], 0, j, minute, 59)
            for num1 in res1:
                for num2 in res2:
                    res.append('{}:{:02d}'.format(num1, num2))

        return res

复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(n)

charlestang commented 2 years ago

思路

回溯，把灯按照可能的位置，一个个摆上去。

时间复杂度，代表小时的灯，有3个可以点亮的位置，代表分钟的灯，最多点亮 5 个。全部遍历完，最多 10^8 次。

代码

class Solution:
    def __init__(self):
        self.result = []
        self.possible = [1,2,4,8,1,2,4,8,16,32]

    def readBinaryWatch(self, num: int) -> List[str]:
        self.num = num
        self.dfs(0, 0, 0, 0)
        return self.result

    def dfs(self, step: int, start: int, hour: int, minute: int):
        if step == self.num:
            time = str(hour) + ":" + ("0" if minute < 10 else "") + str(minute)
            self.result.append( time )
        else:
            for i in range( start, 10 ):
                if i < 4 and self.possible[i] + hour < 12:
                    self.dfs(step+1, i+1, hour + self.possible[i], minute)
                if i > 3 and self.possible[i] + minute < 60:
                    self.dfs(step+1, i+1, hour, minute + self.possible[i])

1149004121 commented 2 years ago

二进制手表

思路

枚举

代码

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

复杂度分析

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

jiaqiliu37 commented 2 years ago

class Solution:
    def readBinaryWatch(self, num: 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, num + 1)):
            for a in possible_number(i):
                for b in possible_number(num - i, True):
                    ans.add(str(a) + ":" + str(b).rjust(2, '0'))
        return list(ans)

Myleswork commented 2 years ago

思路

位运算，遍历0：00-11：59的所有时间，将二进制中1的个数和位turnedOn的组合输出

回溯？等我再思考思考

代码

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

    int count1(int i){
        int count = 0;
        while(i>0){
            if(i%2) count++;
            i>>=1;
        }
        return count;
    }
};

复杂度分析

时间复杂度:O(1)

空间复杂度:O(1)

stackvoid commented 2 years ago

思路

枚举

代码

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)

tangjy149 commented 2 years ago

代码

class Solution {
private:
    vector<string> res;
    vector<int> mins;
    void dfs(int st, int sum, int cnt, bool flag) {
        if (cnt == 0) {
            if (flag) {
                mins.push_back(sum);
            } else {
                if (!mins.empty()) {
                    for (int m : mins) {
                        char time[6];
                        sprintf(time, "%d:%02d", sum, m);
                        res.emplace_back(string{ time });
                        // res.push_back(time);
                    }
                }
            }
            return;
        }

        for (int i = st; i < flag ? 6 : 4; i++) {
            int temp = pow(2, i);
            if (flag && sum + temp >= 60 || !flag && sum + temp >= 12) {
                break;
            }
            dfs(i + 1, sum + temp, cnt - 1, flag);
        }
    }
public:
    vector<string> readBinaryWatch(int num) {
        for (int i = 0; i < 6 && num >= i; i++) {
            dfs(0, 0, i, true);
            dfs(0, 0, num - i, false);
            mins.clear();
        }

        return res;
    }
};

Aobasyp commented 2 years ago

思路笛卡尔积

class Solution: def readBinaryWatch(self, num: 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, num + 1)): for a in possible_number(i): for b in possible_number(num - i, True): ans.add(str(a) + ":" + str(b).rjust(2, '0')) return list(ans)

z1ggy-o commented 2 years ago

思路

暴力枚举。

枚举出 12 小时和 59 分钟的所有不同组合。看哪个组合的二进制表达式中的 1 的个数和 turnedOn 相等。

代码

CPP

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(nm), n 是时范围，m为分范围
空间：O(1)

shamworld commented 2 years ago

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

leetcode-pp / 91alg-6-daily-check

【Day 48 】2022-01-28 - 401. 二进制手表 #58

401. 二进制手表

入选理由

题目地址

前置知识

题目描述

代码

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

题目描述

前置知识

公司

思路

关键点

代码

思路

代码

Idea

Code

Complexity:

思路

关键点

代码

思路

代码

401. 二进制手表

思路一

代码

复杂度分析

【Day 48】401. 二进制手表

思路

golang代码

复杂度

解题思路

代码

复杂度

思路

关键点

代码

思路

思路

代码

复杂度分析：

JAVA版本

思路

代码

复杂度分析

Codes

how many on hour, how many on min

思路

代码

思路

代码

复杂度

Code

思路

代码

复杂度

401. 二进制手表

代码

思路

代码

思路

代码

思路

代码

思路

代码

复杂度分析

代码

思路

代码