leetCode——二进制手表
二进制手表顶部有 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"]
思路
这题真的没感觉是 easy 难度的题型，更像是前面几个递归题目的综合考察版本。
首先拆解开来看，对于分钟和时钟，我们有一个通用的需求就是求出在剩余的亮起的点的数量在 n 时，求可能的所有排列组合。
具体点说，我们要实现的 combine 函数是这样的：时钟有 [1, 2, 4, 8] 四种可能性，在亮起点数为 1 时，它的所有求和的可能性是 [1, 2, 4, 8]，在亮起点数为 2 时，它的可能性就变成了 [1 + 2, 1 + 4, 1 + 8, 2 + 4, 2 + 8, 4 + 8] 以此类推。
假设给你的总亮点数是 2，那么：
-
你可以分配给时钟 0 个点，剩下的 2 个点就分配给分钟。也就是求
combine(hours, 0)和combine(minutes, 2)的笛卡尔积。 -
你可以分配给时钟 1 个点，剩下的 1 个点就分配给分钟。也就是求
combine(hours, 1)和combine(minutes, 1)的笛卡尔积。 -
你可以分配给时钟 2 个点，剩下的 0 个点就分配给分钟。也就是求
combine(hours, 2)和combine(minutes, 0)的笛卡尔积。
有了这个思路，其实核心部分就是实现 combine 函数了，并且注意要对时钟和分钟进行一个异常数值的校验，对分钟进行一个补零的拼接：
/**
* @param {number} num
* @return {string[]}
*/
let HOURS = [1, 2, 4, 8]
let MINUTES = [1, 2, 4, 8, 16, 32]
let readBinaryWatch = function (num) {
let res = []
let combine = (arr, num) => {
if (num === 0) {
return [0]
}
let res = []
let helper = (start, prevCount, prevSum) => {
if (prevCount === num) {
res.push(prevSum)
return
}
for (let i = start; i < arr.length; i++) {
let cur = arr[i]
helper(i + 1, prevCount + 1, prevSum + cur)
}
}
helper(0, 0, 0)
return res
}
for (let i = 0; i <= num; i++) {
let hours = combine(HOURS, i)
let minutes = combine(MINUTES, num - i)
for (let hour of hours) {
if (hour > 11) continue
for (let minute of minutes) {
if (minute > 59) {
continue
}
res.push(`${hour}:${padLeft(minute)}`)
}
}
}
return res
}
function padLeft(num) {
let str = num.toString()
if (str.length === 1) {
str = `0${str}`
}
return str
}
原文地址：https://blog.csdn.net/2301_78659329/article/details/143796588
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！