【Day 40 】2021-06-18 - 401. 二进制手表
题目描述
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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的回答
解法一
时空复杂度
时间复杂度：O(1) 都是全排列一遍
空间复杂度: O(1）只有一个固定 arr数组
回溯法
var readBinaryWatch = function (turnedOn) {
const result = []
const arr = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]
// nums 还剩几个空位
// i 取到第几位了
// temp [时针,分针]
const backTrace = function (nums, i, temp) {
if (temp[0] > 12 || temp[1] > 60) return
if (nums === 0) {
const minute = temp[1] < 10 ? `0${temp[1]}` : temp[1]
result.push(`${temp[0]}:${minute}`)
return
}
for (let j = i; j < arr.length; j++) {
if (j <= 3) {
temp[0] = temp[0] + arr[j]
} else {
temp[1] = temp[1] + arr[j]
}
nums = nums - 1
backTrace(nums, j + 1, temp)
nums = nums + 1
if (j <= 3) {
temp[0] = temp[0] - arr[j]
} else {
temp[1] = temp[1] - arr[j]
}
}
}
backTrace(turnedOn, 0, [0, 0])
return result
};