401.二进制手表

链接：401.二进制手表
难度：Easy
标签：位运算、回溯
简介：二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

题解 1 - typescript

• 编辑时间：2021-06-21
• 执行用时：96ms
• 内存消耗：42.2MB
• 编程语言：typescript
• 解法介绍：全排列。

const getTime = (hour: number, minute: number): string =>
  `${hour}:${minute < 10 ? '0' + minute : minute}`;
const getList = (count: number, data: number[], maxNumber) => {
  const ans: Set<number> = new Set();
  if (count >= data.length) return ans;
  if (count === 0) {
    ans.add(0);
    return ans;
  }
  for (let i = 0, len = data.length; i < len; i++) {
    const num = 1 << data[i];
    const list = getList(count - 1, [...data.slice(0, i), ...data.slice(i + 1)], maxNumber);
    if (list.size === 0) ans.add(num);
    else {
      list.forEach(v => {
        const item = v | num;
        item <= maxNumber && ans.add(item);
      });
    }
  }
  return ans;
};
const getHourList = (count: number) =>
  getList(
    count,
    new Array(4).fill(0).map((_, i) => i),
    11
  );
const getMinuteList = (count: number) =>
  getList(
    count,
    new Array(6).fill(0).map((_, i) => i),
    59
  );
function readBinaryWatch(turnedOn: number): string[] {
  if (turnedOn >= 9) return [];
  if (turnedOn === 0) return ['0:00'];
  return new Array(Math.min(4, turnedOn) + 1)
    .fill(0)
    .map((_, i) => {
      return [i, turnedOn - i];
    })
    .map(([hour, minute]) => {
      const ans: string[] = [];
      const hourList = getHourList(hour);
      const minuteList = getMinuteList(minute);
      if (hourList.size === 0 || minuteList.size === 0) return ans;
      for (const hour of hourList) {
        for (const minute of minuteList) {
          ans.push(getTime(hour, minute));
        }
      }
      return ans;
    })
    .flat();
}