leetcode 401. 二进制手表

[xxleyi]

题：

二进制手表顶部有 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”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：

又是一道典型的回溯算法题，并可以使用位计算提高效率。

本题解使用了部分位计算。

在「回溯」算法中，那个「循环不变式」是什么呢？说实话，不是很明显：使用递归枚举所有可能性，并在单次递归结束，回退之前清理现场。同时，还有两点很关键：

• 终止条件
• 尽可能的剪枝

var readBinaryWatch = function(num) {
  const hourBit = 512 + 256 + 128 + 64
  const minuteBit = 63
  let watch = Array(10).fill(0)
  let all = []

  // 辅助函数：解析有效时间
  function parseWatch() {
    if (watch.reduce((a, b) => a + b) !== num) return
    const watchBit = parseInt(watch.join(''), 2)
    const hour = (watchBit & hourBit) >> 6
    const minute = (watchBit & minuteBit)
    if (hour < 12 && minute < 60) {
      all.push(`${hour}:${(minute + '').padStart(2, '0')}`)
    }
  }

  function backtrack(n = num, idx = 0) {
    // 剪枝
    if (idx + n > 10) return
    // 递归终止，尝试生成有效时间
    else if (n === 0) parseWatch()
    // 回溯：递归 + reset before back
    else {
      // idx 不亮
      backtrack(n, idx + 1)
      // 递归结束，回退前不必做操作

      // idx 亮
      watch[idx] = 1
      backtrack(n - 1, idx + 1)
      // 递归结束，回退前需让 idx 复归原状
      watch[idx] = 0
    }
  }

  backtrack()
  return all
};

进阶：可把上述代码中更多的部分使用位计算实现

var readBinaryWatch = function(num) {
  const hourBit = 512 + 256 + 128 + 64
  const minuteBit = 63
  let watch = 0
  let all = []

  // 辅助函数：解析有效时间
  function parseWatch(on, bit) {
    const hour = (watch & hourBit) >> 6
    const minute = (watch & minuteBit)
    if (hour < 12 && minute < 60) {
      all.push(`${hour}:${(minute + '').padStart(2, '0')}`)
    }
  }

  function backtrack(n = num, bit = 1, on = 0) {
    // 递归终止，尝试生成有效时间
    if (bit > 512) {
      if (n === 0 && on === num) parseWatch(on, bit)
    }
    // 回溯：递归 + reset before back
    else {
      // bit 不亮
      backtrack(n, bit << 1, on)
      // 递归结束，回溯前不必做操作

      // bit 亮
      watch ^= bit
      backtrack(n - 1, bit << 1, on + 1)
      // 递归结束，回溯前让 bit 复归原状
      watch ^= bit
    }
  }

  backtrack()
  return all
};