We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
二进制手表顶部有 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"]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-watch 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这题真的没感觉是 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] 以此类推。
combine
[1, 2, 4, 8]
[1 + 2, 1 + 4, 1 + 8, 2 + 4, 2 + 8, 4 + 8]
假设给你的总亮点数是 2,那么:
你可以分配给时钟 0 个点,剩下的 2 个点就分配给分钟。也就是求 combine(hours, 0) 和 combine(minutes, 2) 的笛卡尔积。
combine(hours, 0)
combine(minutes, 2)
你可以分配给时钟 1 个点,剩下的 1 个点就分配给分钟。也就是求 combine(hours, 1) 和 combine(minutes, 1) 的笛卡尔积。
combine(hours, 1)
combine(minutes, 1)
你可以分配给时钟 2 个点,剩下的 0 个点就分配给分钟。也就是求 combine(hours, 2) 和 combine(minutes, 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 }
The text was updated successfully, but these errors were encountered:
回溯模板一套:
var readBinaryWatch = function (turnedOn) { const res = []; var backtracking = function (num, start, h, m) { if (num === 0) { if (h > 11 || m > 59) { return; } let hour = h.toString(); let minute = m.toString(); if (minute.length === 1) { minute = '0' + minute; } res.push(hour + ":" + minute); } for (let i = start; i <= 9; i++) { if (h > 11 || m > 59) { continue; } const store = [h, m]; // 记录状态 if (i <= 3) { h += 2 ** i; } else { m += 2 ** (i - 4); } backtracking(num - 1, i + 1, h, m);//进入下一层,注意下一层的 start 是 i+1 // 恢复状态 h = store[0]; m = store[1]; } } backtracking(turnedOn, 0, 0, 0); return res; };
Sorry, something went wrong.
var readBinaryWatch = function (turnedOn) { if (turnedOn === 9 || turnedOn === 10) return [] if(turnedOn === 0) ["0:00"] const arr = ['8', '4', '2', '1', 32, 16, 8, 4, 2, 1] const length = arr.length; const res = [] function dfs(index, path1, path2) { const hours = path1.reduce((total,cur)=>total+cur,0) if (hours > 11) return; let minutes = path2.reduce((total,cur)=>total+cur,0) if (minutes > 59) return; let len = path1.length+path2.length; if (len === turnedOn) { if (minutes.toString().length === 1) minutes = '0' + minutes res.push(hours + ':' + minutes) return } for (let i = index; i < length; i++) { if (turnedOn - len > length - index) return const item = arr[i]; if (typeof item === 'string'){ path1.push(Number(item)); }else{ path2.push(item); } dfs(i + 1, path1,path2) if (typeof item === 'string'){ path1.pop(); }else{ path2.pop(); } } } dfs(0, [],[]) return res }
No branches or pull requests
Uh oh!
There was an error while loading. Please reload this page.
二进制手表顶部有 4 个 LED 代表 小时(0-11),底部的 6 个 LED 代表 分钟(0-59)。
每个 LED 代表一个 0 或 1,最低位在右侧。
例如,上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量,返回所有可能的时间。
示例:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这题真的没感觉是 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
函数了,并且注意要对时钟和分钟进行一个异常数值的校验,对分钟进行一个补零的拼接:The text was updated successfully, but these errors were encountered: