Description

sl1673495

opened on Jun 13, 2020

Issue body actions

二进制手表顶部有 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] 以此类推。

假设给你的总亮点数是 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
}

Activity

1. sl1673495

   added

   例题详解每个分类下会挑出几道题目进行精讲，其他的同类题目会默认拥有这些前置知识而简略讲解。每个分类下会挑出几道题目进行精讲，其他的同类题目会默认拥有这些前置知识而简略讲解。

   递归与回溯

   on Jun 13, 2020
2. vortesnail commented on Aug 17, 2021

   

   vortesnail

   on Aug 17, 2021

   More actions

   回溯模板一套：

   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;
   };
3. daomingQian commented on Oct 28, 2021

   

   daomingQian

   on Oct 28, 2021

   More actions

   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
       }
   

Issue actions