力扣(6/21每日一题)二进制手表
2021/6/22 0:00:04
本文主要是介绍力扣(6/21每日一题)二进制手表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
401. 二进制手表
二进制手表顶部有 4 个 LED 代表 小时(0-11),底部的 6 个 LED 代表 分钟(0-59)。每个 LED 代表一个 0 或 1,最低位在右侧。
例如,下面的二进制手表读取 "3:25" 。
给你一个整数 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:用深搜的方法,递归的层数来决定遍历到哪个灯,对每个灯它亮或者不亮,当亮的灯的数目符合turnedOn的个数时把结果保存到res中。
class Solution { vector<string> res; public: void dfs(int turnedOn, int hour, int minute, int idx){ if(hour > 11 || minute > 59) return ; //深搜边界一:深搜累积的结果溢出,剪枝 if(turnedOn == 0){ //深搜边界二:记录turnedOn的其中一种结果 string temp; temp += to_string(hour); temp += ":"; if(minute < 10) temp += "0"; temp += to_string(minute); res.push_back(temp); //记录该结果 return ; //返回上一层 } if(idx > 9) return; //深搜边界三:九个位置遍历完,返回 //本层的灯遍历亮或者不亮两种情况 dfs(turnedOn, hour, minute, idx + 1); //不亮 if(idx < 4) dfs(turnedOn - 1, hour + (1 << (3 - idx)), minute, idx + 1); //亮hour灯 else dfs(turnedOn - 1, hour, minute + (1 << (9 - idx)), idx + 1); //亮minute灯 } vector<string> readBinaryWatch(int turnedOn){ if(turnedOn >= 9) return res; //满载或者灯数多于9剪枝 dfs(turnedOn, 0, 0, 0); //深搜 return res; //返回结果 } };
运行结果如下:
这篇关于力扣(6/21每日一题)二进制手表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现