leetcode401：二进制手表（binary-watch）

carloscn commented 1 year ago

问题描述

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

例如，下面的二进制手表读取 "3:25" 。

给你一个整数 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 输出：[]

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/binary-watch

carloscn commented 1 year ago

问题分析

不要被二进制显示忽悠了，本质还是手表。从0:00-> 11:59 直接判断小时位出现的1个数+分秒位出现的1个数：

static char str_result[] = "00:00";
static char* gen_str(int32_t hou, int32_t min)
{
    if (min < 10) {
        sprintf(str_result, "%d:0%d", hou, min);
    } else {
        sprintf(str_result, "%d:%d", hou, min);
    }
    return str_result;
}

static size_t count1(size_t n)
{
    size_t res = 0;

    while (n != 0) {
        n = n & (n - 1);
        res ++;
    }
    return res;
}

static int32_t binary_watch(size_t turn_on, STRLIST_T *list)
{
    int32_t ret = 0;
    size_t i = 0, j = 0;

    UTILS_CHECK_PTR(list);

    if (0 == turn_on) {
        strlist_add(list, gen_str(0, 0));
        goto finish;
    }

    for (i = 0; i < 12; i ++) {
        for (j = 0; j < 60; j ++) {
            if (count1(i) + count1(j) == turn_on) {
                strlist_add(list, gen_str(i, j));
            }
        }
    }

finish:
    return ret;
}

carloscn commented 1 year ago

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/str/23_binary-watch_401.c

carloscn / structstudy