公众号:offer多多

V1

2022/01/28阅读:54主题:橙心

Day 48】401. 二进制手表

【Day 45】438. 找到字符串中所有字母异位词

一.读题目

入选理由

搜索篇的题目为: 回溯 -> BFS/DFS(BFS 和 DFS 不做区分,因为基本上能用 DFS 的,也能用 BFS,互通的) ,先从简单的回溯开始。 大家注意画图哦

标签

回溯

难度

简单

题目描述


二进制手表顶部有 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。



前置知识

笛卡尔积

回溯

二、思路

采用回溯方法,对所有灯的情况进行遍历,建立遍历树,树的高度为灯的个数。

通过level控制,同时更新hour和min。

对于满足条件的情况进行输出。

时间复杂度为O(2^n),空间复杂度O(n),此处n为level的高度。

假设n=2,即选两盏灯亮

三、关键点

  • 本质是组合问题,选出turnedOn个元素 https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/

四、算法描述

五、代码

组合问题

  1. 暴力破解 -golang
func readBinaryWatch(turnedOn int) (ans []string) {
    for h := uint8(0); h < 12; h++ {
        for m := uint8(0); m < 60; m++ {
            if bits.OnesCount8(h)+bits.OnesCount8(m) == turnedOn {
                ans = append(ans, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-watch/solution/er-jin-zhi-shou-biao-by-leetcode-solutio-3559/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
  • 递归--java
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; 
    }
};
欢迎关注
欢迎关注

分类:

后端

标签:

后端

作者介绍

公众号:offer多多
V1