Question

401. 二进制手表

English Version

题目描述

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

• 例如，下面的二进制手表读取 "4:51" 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

• 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：

• 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

 

示例 1：

输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

示例 2：

输入：turnedOn = 9
输出：[]

 

提示：

• 0 <= turnedOn <= 10

解法

方法一：枚举组合

题目可转换为求 i(i∈[0,12)) 和 j(j∈[0,60)) 所有可能的组合。

合法组合需要满足的条件是：i 的二进制形式中 1 的个数加上 j 的二进制形式中 1 的个数，结果等于 turnedOn。

class Solution:
  def readBinaryWatch(self, turnedOn: int) -> List[str]:
    return [
      '{:d}:{:02d}'.format(i, j)
      for i in range(12)
      for j in range(60)
      if (bin(i) + bin(j)).count('1') == turnedOn
    ]

class Solution {
  public List<String> readBinaryWatch(int turnedOn) {
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < 12; ++i) {
      for (int j = 0; j < 60; ++j) {
        if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
          ans.add(String.format("%d:%02d", i, j));
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> readBinaryWatch(int turnedOn) {
    vector<string> ans;
    for (int i = 0; i < 12; ++i) {
      for (int j = 0; j < 60; ++j) {
        if (__builtin_popcount(i) + __builtin_popcount(j) == turnedOn) {
          ans.push_back(to_string(i) + ":" + (j < 10 ? "0" : "") + to_string(j));
        }
      }
    }
    return ans;
  }
};

func readBinaryWatch(turnedOn int) []string {
  var ans []string
  for i := 0; i < 12; i++ {
    for j := 0; j < 60; j++ {
      if bits.OnesCount(uint(i))+bits.OnesCount(uint(j)) == turnedOn {
        ans = append(ans, fmt.Sprintf("%d:%02d", i, j))
      }
    }
  }
  return ans
}

function readBinaryWatch(turnedOn: number): string[] {
  if (turnedOn === 0) {
    return ['0:00'];
  }
  const n = 10;
  const res = [];
  const bitArr = new Array(10).fill(false);
  const createTime = () => {
    return [
      bitArr.slice(0, 4).reduce((p, v) => (p << 1) | Number(v), 0),
      bitArr.slice(4).reduce((p, v) => (p << 1) | Number(v), 0),
    ];
  };
  const helper = (i: number, count: number) => {
    if (i + count > n || count === 0) {
      return;
    }
    bitArr[i] = true;
    if (count === 1) {
      const [h, m] = createTime();
      if (h < 12 && m < 60) {
        res.push(`${h}:${m < 10 ? '0' + m : m}`);
      }
    }
    helper(i + 1, count - 1);
    bitArr[i] = false;
    helper(i + 1, count);
  };
  helper(0, turnedOn);
  return res;
}

impl Solution {
  fn create_time(bit_arr: &[bool; 10]) -> (i32, i32) {
    let mut h = 0;
    let mut m = 0;
    for i in 0..4 {
      h <<= 1;
      h |= if bit_arr[i] { 1 } else { 0 };
    }
    for i in 4..10 {
      m <<= 1;
      m |= if bit_arr[i] { 1 } else { 0 };
    }

    (h, m)
  }

  fn helper(res: &mut Vec<String>, bit_arr: &mut [bool; 10], i: usize, count: usize) {
    if i + count > 10 || count == 0 {
      return;
    }
    bit_arr[i] = true;
    if count == 1 {
      let (h, m) = Self::create_time(bit_arr);
      if h < 12 && m < 60 {
        if m < 10 {
          res.push(format!("{}:0{}", h, m));
        } else {
          res.push(format!("{}:{}", h, m));
        }
      }
    }
    Self::helper(res, bit_arr, i + 1, count - 1);
    bit_arr[i] = false;
    Self::helper(res, bit_arr, i + 1, count);
  }

  pub fn read_binary_watch(turned_on: i32) -> Vec<String> {
    if turned_on == 0 {
      return vec![String::from("0:00")];
    }
    let mut res = vec![];
    let mut bit_arr = [false; 10];
    Self::helper(&mut res, &mut bit_arr, 0, turned_on as usize);
    res
  }
}

方法二：二进制枚举

利用 10 个二进制位表示手表，其中前 4 位代表小时，后 6 位代表分钟。枚举 [0, 1 << 10) 的所有数，找出合法的数。

class Solution:
  def readBinaryWatch(self, turnedOn: int) -> List[str]:
    ans = []
    for i in range(1 << 10):
      h, m = i >> 6, i & 0b111111
      if h < 12 and m < 60 and i.bit_count() == turnedOn:
        ans.append('{:d}:{:02d}'.format(h, m))
    return ans

class Solution {
  public List<String> readBinaryWatch(int turnedOn) {
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < 1 << 10; ++i) {
      int h = i >> 6, m = i & 0b111111;
      if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
        ans.add(String.format("%d:%02d", h, m));
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> readBinaryWatch(int turnedOn) {
    vector<string> ans;
    for (int i = 0; i < 1 << 10; ++i) {
      int h = i >> 6, m = i & 0b111111;
      if (h < 12 && m < 60 && __builtin_popcount(i) == turnedOn) {
        ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
      }
    }
    return ans;
  }
};

func readBinaryWatch(turnedOn int) []string {
  var ans []string
  for i := 0; i < 1<<10; i++ {
    h, m := i>>6, i&0b111111
    if h < 12 && m < 60 && bits.OnesCount(uint(i)) == turnedOn {
      ans = append(ans, fmt.Sprintf("%d:%02d", h, m))
    }
  }
  return ans
}