algorithms/401-binary-watch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "right-abortion",
   "metadata": {},
   "source": [
    "### [二进制手表](https://leetcode-cn.com/problems/binary-watch/)\n",
    "\n",
    "二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。\n",
    "\n",
    "```\n",
    "0  0  1  1\n",
    "0 1 1 0 0 1\n",
    "```\n",
    "\n",
    "每个 LED 代表一个 0 或 1，最低位在右侧。\n",
    "\n",
    "例如，上面的二进制手表读取 “3:25”。\n",
    "\n",
    "给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。\n",
    "\n",
    "#### 示例：\n",
    "```\n",
    "输入: n = 1\n",
    "返回: [\"1:00\", \"2:00\", \"4:00\", \"8:00\", \"0:01\", \"0:02\", \"0:04\", \"0:08\", \"0:16\", \"0:32\"]\n",
    "```\n",
    "\n",
    "#### 提示：\n",
    "- 输出的顺序没有要求。\n",
    "- 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。\n",
    "- 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。\n",
    "- 超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 \"13:00\", \"0:61\" 等时间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "hawaiian-software",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "def readBinaryWatch(num: int) -> List[str]:\n",
    "    def minutes(s: str) -> str:\n",
    "        ret, n = 0, len(s)\n",
    "        for i in reversed(range(n)):\n",
    "            if s[i] == '1':\n",
    "                ret += 2 ** i\n",
    "        if ret >= 60:\n",
    "            return None\n",
    "        else:\n",
    "            return \"%02d\" % ret\n",
    "    \n",
    "    def hours(s: str) -> str:\n",
    "        ret, n = 0, len(s)\n",
    "        for i in reversed(range(n)):\n",
    "            if s[i] == '1':\n",
    "                ret += 2 ** i\n",
    "        if ret >= 12:\n",
    "            return None\n",
    "        else:\n",
    "            return str(ret % 12)\n",
    "    \n",
    "    i, candidates = 0, []\n",
    "    while i < 1024:\n",
    "        s = \"{:010b}\".format(i)\n",
    "        if s.count('1') == num:\n",
    "            h, m = hours(s[:4]), minutes(s[-6:])\n",
    "            if h is not None and m is not None:\n",
    "                candidates.append(\"{}:{}\".format(h, m))\n",
    "        i += 1\n",
    "        \n",
    "    return candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "scenic-constitution",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "working-dividend",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0:32',\n",
       " '0:16',\n",
       " '0:08',\n",
       " '0:04',\n",
       " '0:02',\n",
       " '0:01',\n",
       " '8:00',\n",
       " '4:00',\n",
       " '2:00',\n",
       " '1:00']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "fifty-prefix",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0:00']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "going-wildlife",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0:48',\n",
       " '0:40',\n",
       " '0:24',\n",
       " '0:36',\n",
       " '0:20',\n",
       " '0:12',\n",
       " '0:34',\n",
       " '0:18',\n",
       " '0:10',\n",
       " '0:06',\n",
       " '0:33',\n",
       " '0:17',\n",
       " '0:09',\n",
       " '0:05',\n",
       " '0:03',\n",
       " '8:32',\n",
       " '8:16',\n",
       " '8:08',\n",
       " '8:04',\n",
       " '8:02',\n",
       " '8:01',\n",
       " '4:32',\n",
       " '4:16',\n",
       " '4:08',\n",
       " '4:04',\n",
       " '4:02',\n",
       " '4:01',\n",
       " '2:32',\n",
       " '2:16',\n",
       " '2:08',\n",
       " '2:04',\n",
       " '2:02',\n",
       " '2:01',\n",
       " '10:00',\n",
       " '6:00',\n",
       " '1:32',\n",
       " '1:16',\n",
       " '1:08',\n",
       " '1:04',\n",
       " '1:02',\n",
       " '1:01',\n",
       " '9:00',\n",
       " '5:00',\n",
       " '3:00']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "narrative-brain",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0:58',\n",
       " '0:54',\n",
       " '0:46',\n",
       " '0:30',\n",
       " '0:57',\n",
       " '0:53',\n",
       " '0:45',\n",
       " '0:29',\n",
       " '0:51',\n",
       " '0:43',\n",
       " '0:27',\n",
       " '0:39',\n",
       " '0:23',\n",
       " '0:15',\n",
       " '8:56',\n",
       " '8:52',\n",
       " '8:44',\n",
       " '8:28',\n",
       " '8:50',\n",
       " '8:42',\n",
       " '8:26',\n",
       " '8:38',\n",
       " '8:22',\n",
       " '8:14',\n",
       " '8:49',\n",
       " '8:41',\n",
       " '8:25',\n",
       " '8:37',\n",
       " '8:21',\n",
       " '8:13',\n",
       " '8:35',\n",
       " '8:19',\n",
       " '8:11',\n",
       " '8:07',\n",
       " '4:56',\n",
       " '4:52',\n",
       " '4:44',\n",
       " '4:28',\n",
       " '4:50',\n",
       " '4:42',\n",
       " '4:26',\n",
       " '4:38',\n",
       " '4:22',\n",
       " '4:14',\n",
       " '4:49',\n",
       " '4:41',\n",
       " '4:25',\n",
       " '4:37',\n",
       " '4:21',\n",
       " '4:13',\n",
       " '4:35',\n",
       " '4:19',\n",
       " '4:11',\n",
       " '4:07',\n",
       " '2:56',\n",
       " '2:52',\n",
       " '2:44',\n",
       " '2:28',\n",
       " '2:50',\n",
       " '2:42',\n",
       " '2:26',\n",
       " '2:38',\n",
       " '2:22',\n",
       " '2:14',\n",
       " '2:49',\n",
       " '2:41',\n",
       " '2:25',\n",
       " '2:37',\n",
       " '2:21',\n",
       " '2:13',\n",
       " '2:35',\n",
       " '2:19',\n",
       " '2:11',\n",
       " '2:07',\n",
       " '10:48',\n",
       " '10:40',\n",
       " '10:24',\n",
       " '10:36',\n",
       " '10:20',\n",
       " '10:12',\n",
       " '10:34',\n",
       " '10:18',\n",
       " '10:10',\n",
       " '10:06',\n",
       " '10:33',\n",
       " '10:17',\n",
       " '10:09',\n",
       " '10:05',\n",
       " '10:03',\n",
       " '6:48',\n",
       " '6:40',\n",
       " '6:24',\n",
       " '6:36',\n",
       " '6:20',\n",
       " '6:12',\n",
       " '6:34',\n",
       " '6:18',\n",
       " '6:10',\n",
       " '6:06',\n",
       " '6:33',\n",
       " '6:17',\n",
       " '6:09',\n",
       " '6:05',\n",
       " '6:03',\n",
       " '1:56',\n",
       " '1:52',\n",
       " '1:44',\n",
       " '1:28',\n",
       " '1:50',\n",
       " '1:42',\n",
       " '1:26',\n",
       " '1:38',\n",
       " '1:22',\n",
       " '1:14',\n",
       " '1:49',\n",
       " '1:41',\n",
       " '1:25',\n",
       " '1:37',\n",
       " '1:21',\n",
       " '1:13',\n",
       " '1:35',\n",
       " '1:19',\n",
       " '1:11',\n",
       " '1:07',\n",
       " '9:48',\n",
       " '9:40',\n",
       " '9:24',\n",
       " '9:36',\n",
       " '9:20',\n",
       " '9:12',\n",
       " '9:34',\n",
       " '9:18',\n",
       " '9:10',\n",
       " '9:06',\n",
       " '9:33',\n",
       " '9:17',\n",
       " '9:09',\n",
       " '9:05',\n",
       " '9:03',\n",
       " '5:48',\n",
       " '5:40',\n",
       " '5:24',\n",
       " '5:36',\n",
       " '5:20',\n",
       " '5:12',\n",
       " '5:34',\n",
       " '5:18',\n",
       " '5:10',\n",
       " '5:06',\n",
       " '5:33',\n",
       " '5:17',\n",
       " '5:09',\n",
       " '5:05',\n",
       " '5:03',\n",
       " '3:48',\n",
       " '3:40',\n",
       " '3:24',\n",
       " '3:36',\n",
       " '3:20',\n",
       " '3:12',\n",
       " '3:34',\n",
       " '3:18',\n",
       " '3:10',\n",
       " '3:06',\n",
       " '3:33',\n",
       " '3:17',\n",
       " '3:09',\n",
       " '3:05',\n",
       " '3:03',\n",
       " '11:32',\n",
       " '11:16',\n",
       " '11:08',\n",
       " '11:04',\n",
       " '11:02',\n",
       " '11:01',\n",
       " '7:32',\n",
       " '7:16',\n",
       " '7:08',\n",
       " '7:04',\n",
       " '7:02',\n",
       " '7:01']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "married-thriller",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0:56',\n",
       " '0:52',\n",
       " '0:44',\n",
       " '0:28',\n",
       " '0:50',\n",
       " '0:42',\n",
       " '0:26',\n",
       " '0:38',\n",
       " '0:22',\n",
       " '0:14',\n",
       " '0:49',\n",
       " '0:41',\n",
       " '0:25',\n",
       " '0:37',\n",
       " '0:21',\n",
       " '0:13',\n",
       " '0:35',\n",
       " '0:19',\n",
       " '0:11',\n",
       " '0:07',\n",
       " '8:48',\n",
       " '8:40',\n",
       " '8:24',\n",
       " '8:36',\n",
       " '8:20',\n",
       " '8:12',\n",
       " '8:34',\n",
       " '8:18',\n",
       " '8:10',\n",
       " '8:06',\n",
       " '8:33',\n",
       " '8:17',\n",
       " '8:09',\n",
       " '8:05',\n",
       " '8:03',\n",
       " '4:48',\n",
       " '4:40',\n",
       " '4:24',\n",
       " '4:36',\n",
       " '4:20',\n",
       " '4:12',\n",
       " '4:34',\n",
       " '4:18',\n",
       " '4:10',\n",
       " '4:06',\n",
       " '4:33',\n",
       " '4:17',\n",
       " '4:09',\n",
       " '4:05',\n",
       " '4:03',\n",
       " '2:48',\n",
       " '2:40',\n",
       " '2:24',\n",
       " '2:36',\n",
       " '2:20',\n",
       " '2:12',\n",
       " '2:34',\n",
       " '2:18',\n",
       " '2:10',\n",
       " '2:06',\n",
       " '2:33',\n",
       " '2:17',\n",
       " '2:09',\n",
       " '2:05',\n",
       " '2:03',\n",
       " '10:32',\n",
       " '10:16',\n",
       " '10:08',\n",
       " '10:04',\n",
       " '10:02',\n",
       " '10:01',\n",
       " '6:32',\n",
       " '6:16',\n",
       " '6:08',\n",
       " '6:04',\n",
       " '6:02',\n",
       " '6:01',\n",
       " '1:48',\n",
       " '1:40',\n",
       " '1:24',\n",
       " '1:36',\n",
       " '1:20',\n",
       " '1:12',\n",
       " '1:34',\n",
       " '1:18',\n",
       " '1:10',\n",
       " '1:06',\n",
       " '1:33',\n",
       " '1:17',\n",
       " '1:09',\n",
       " '1:05',\n",
       " '1:03',\n",
       " '9:32',\n",
       " '9:16',\n",
       " '9:08',\n",
       " '9:04',\n",
       " '9:02',\n",
       " '9:01',\n",
       " '5:32',\n",
       " '5:16',\n",
       " '5:08',\n",
       " '5:04',\n",
       " '5:02',\n",
       " '5:01',\n",
       " '3:32',\n",
       " '3:16',\n",
       " '3:08',\n",
       " '3:04',\n",
       " '3:02',\n",
       " '3:01',\n",
       " '11:00',\n",
       " '7:00']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "killing-breach",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['10:59',\n",
       " '10:55',\n",
       " '10:47',\n",
       " '10:31',\n",
       " '6:59',\n",
       " '6:55',\n",
       " '6:47',\n",
       " '6:31',\n",
       " '9:59',\n",
       " '9:55',\n",
       " '9:47',\n",
       " '9:31',\n",
       " '5:59',\n",
       " '5:55',\n",
       " '5:47',\n",
       " '5:31',\n",
       " '3:59',\n",
       " '3:55',\n",
       " '3:47',\n",
       " '3:31',\n",
       " '11:58',\n",
       " '11:54',\n",
       " '11:46',\n",
       " '11:30',\n",
       " '11:57',\n",
       " '11:53',\n",
       " '11:45',\n",
       " '11:29',\n",
       " '11:51',\n",
       " '11:43',\n",
       " '11:27',\n",
       " '11:39',\n",
       " '11:23',\n",
       " '11:15',\n",
       " '7:58',\n",
       " '7:54',\n",
       " '7:46',\n",
       " '7:30',\n",
       " '7:57',\n",
       " '7:53',\n",
       " '7:45',\n",
       " '7:29',\n",
       " '7:51',\n",
       " '7:43',\n",
       " '7:27',\n",
       " '7:39',\n",
       " '7:23',\n",
       " '7:15']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "readBinaryWatch(7)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}