【LeetCode每日一题】——401.二进制手表

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【题目提示】
  • 七【解题思路】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 回溯

二【题目难度】

  • 简单

三【题目编号】

  • 401.二进制手表

四【题目描述】

  • 二进制手表顶部有 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

七【解题思路】

  • 该题目很容易想到使用回溯+剪枝来解决
  • 我们需要在10个灯中选择n个灯点亮,并计算其时间和,需要注意要判断该时间和是否合理,如果不合理(小时超过11,分钟超过59)需要进行剪枝
  • 上面提到“选择n个灯点亮”,我们肯定不能一起全部点亮,所以需要用到回溯,一个一个选择,还可以进行不同的组合
  • 为了实现“选择n个灯点亮”,我们可以设置小时数组和分钟数组,长度为10,不足10位补零,目的是使用这两个数组来模拟小时和分钟的亮灯情况(数组索引选中的值即为亮的灯)
  • 具体实现可以参考下面的代码,最后按照回溯+剪枝的方法将结果计算出并返回即可

八【时间频度】

  • 时间复杂度: O ( C 10 n ) O(C_{10}^{n}) O(C10n) n n n为传入的参数值
  • 空间复杂度: O ( n ) O(n) O(n) n n n为传入的参数值

九【代码实现】

  1. Java语言版
class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        // 定义时间数组
        int[] hours = {1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
        int[] minutes = {0, 0, 0, 0, 1, 2, 4, 8, 16, 32};

        // 定义结果列表
        List<String> res = new ArrayList<>();

        // 回溯计算可能的时间组合
        backtrack(turnedOn, 0, 0, 0, res, hours, minutes);

        // 返回结果
        return res;
    }

    private void backtrack(int count, int index, int hour, int minute, List<String> res, int[] hours, int[] minutes) {
        if (hour > 11 || minute > 59) {
            return;
        }
        if (count == 0) {
            res.add(String.format("%d:%02d", hour, minute));
        }
        for (int i = index; i < 10; i++) {
            backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i], res, hours, minutes);
        }
    }
}
  1. Python语言版
class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # 定义时间数组
        hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]
        minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]

        # 定义结果列表
        res = []

        # 回溯计算可能的时间组合
        def backtrack(count, index, hour, minute):
            if hour > 11 or minute > 59:
                return
            if count == 0:
                res.append("%d:%02d" % (hour, minute))
                return
            for i in range(index, 10):
                backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i])
        backtrack(turnedOn, 0, 0, 0)

        # 返回结果
        return res
  1. C语言版
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define MAX_RES_SIZE 256

// 定义回调函数来递归查找所有可能的时间组合
void backtrack(int count, int index, int hour, int minute, char res[MAX_RES_SIZE][6], int *returnSize, int * hours, int *minutes)
{
    if (hour > 11 || minute > 59)
    {
        return;
    }
    if (count == 0)
    {
        sprintf(res[*returnSize], "%d:%02d", hour, minute);
        (*returnSize)++;
        return;
    }
    for (int i = index; i < 10; i++)
    {
        backtrack(count - 1, i + 1, hour + hours[i], minute + minutes[i], res, returnSize, hours, minutes);
    }
}

char** readBinaryWatch(int turnedOn, int* returnSize)
{
    // 定义时间数组
    int hours[] = {1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
    int minutes[] = {0, 0, 0, 0, 1, 2, 4, 8, 16, 32};

    // 分配空间用于存储结果
    char (*res)[6] = malloc(MAX_RES_SIZE * sizeof(*res));
    *returnSize = 0;

    // 开始递归
    backtrack(turnedOn, 0, 0, 0, res, returnSize, hours, minutes);

    // 转换为char**返回
    char** finRes = malloc(*returnSize * sizeof(char*));
    for (int i = 0; i < *returnSize; i++)
    {
        finRes[i] = res[i];
    }
    return finRes;
}

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. Python语言版
    在这里插入图片描述

  3. C语言版
    在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/881093.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

4.提升客户服务体验:ChatGPT在客服中的应用(4/10)

本文大纲旨在指导撰写一篇全面探讨ChatGPT如何通过优化客户服务流程、提供实际应用案例和用户反馈&#xff0c;以提升客户服务体验的深入博客文章。 引言 在当今竞争激烈的商业环境中&#xff0c;客户服务已成为企业成功的关键因素。优质的客户服务不仅能够增强客户满意度和忠…

Docker 进入容器并运行命令的方法

目录 理解 Docker 容器的基本概念 使用 docker exec 进入运行中的容器 基本用法 常用选项解析 选项详解 实际案例演示 1. 进入容器的交互式 Shell 2. 在容器中运行单个命令 3. 以指定用户运行命令 4. 设置环境变量并运行命令 5. 指定工作目录 使用 docker attach 附…

数据结构-线性表顺序单项链表双向链表循环链表

1数据结构概述 数据结构是计算机组织、存储数据的方式。是思想层面的东西&#xff0c;和具体的计算机编程语言没有关系。可以用任何计算机编程语言去实现这些思想。 1.1 数据逻辑结构 反映数据逻辑之间的逻辑关系&#xff0c;这些逻辑关系和他们咱在计算机中的存储位置无关。…

原生+jquery写自动消失的提示框

<!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>自动消失消息提示</title> <style>/…

使用scp命令从本地往服务器传输文件失败

解决办法&#xff1a; 找到这个文件&#xff0c;打开&#xff0c;将里面的服务器ip对应的一行数据删掉即可。

6.C_数据结构_查询_哈希表

概述 哈希表的查询是通过计算的方式获取数据的地址&#xff0c;而不是依次比较。在哈希表中&#xff0c;有一个键值key&#xff0c;通过一些函数转换为哈希表的索引值。 其中&#xff1a;这个函数被称为哈希函数、散列函数、杂凑函数&#xff0c;记为&#xff1a;H(key) 哈希…

Java知识点小结3:内存回收

文章目录 对象引用强引用软引用&#xff08;SoftReference&#xff09;弱引用&#xff08;WeakReference&#xff09;考一考 虚引用&#xff08;PhantomReference&#xff09;总结 垃圾回收新生代老年代永生代 内存管理小技巧尽量使用直接量使用StringBuilder和StringBuffer进行…

7--SpringBoot-后端开发、原理详解(面试高频提问点)

目录 SpringBoot原理 起步依赖 自动配置 配置优先级 Bean设置 获取Bean 第三方Bean SpringBoot原理 内容偏向于底层的原理分析 基于Spring框架进行项目的开发有两个不足的地方&#xff1a; 在pom.xml中依赖配置比较繁琐&#xff0c;在项目开发时&#xff0c;需要自己去找…

最新编程语言排行榜:Python创新高!

2024年编程语言排行榜又迎来了令人惊喜的变化&#xff01;Python&#xff0c;这门因简单易学而受到广大程序员青睐的语言&#xff0c;再次突破历史记录&#xff0c;稳居排行榜前列。无论是数据分析、机器学习&#xff0c;还是Web开发&#xff0c;Python都展现出了强大的生命力和…

828华为云征文 | 使用Flexus云服务器X实例部署GLPI资产管理系统

828华为云征文 | 使用Flexus云服务器X实例部署GLPI资产管理系统 1. 部署环境说明2. 部署基础环境2.1. 操作系统基本配置2.2. 部署Nginx2.3. 部署MySQL2.4. 部署PHP 3. 部署GLPI资产管理系统 1. 部署环境说明 本次环境选择使用华为云Flexus云服务器X实例&#xff0c;因为其具有高…

无人机之AI跟踪篇

无人机的AI识别技术依托于计算机视觉和深度学习技术&#xff0c;实现了对目标的快速精准识别&#xff0c;在多个领域展现出了巨大的应用潜力和价值。以下是对无人机AI识别技术的详细解析&#xff1a; 一、无人机AI识别算法的基础原理 无人机AI识别算法主要基于先进的计算机视觉…

【刷题日记】15. 三数之和

15. 三数之和 两数之和可以用巧思也可以用map 三数之和会更加复杂一点&#xff0c;且这道题还需要考虑避免重复答案&#xff01; 思路&#xff1a; 特判&#xff1a;检如果nums 为 null 或长度小于 3直接返回空数组。排序&#xff1a;使用 sort对数组进行升序排序。就变成了…

JS实现树形结构数据中特定节点及其子节点显示属性设置的技巧(可用于树形节点过滤筛选)

大家好&#xff0c;今天我要分享的是如何在树形结构的数据中&#xff0c;根据特定条件设置节点及其所有子节点的显示属性。在实际项目中&#xff0c;这种需求非常常见&#xff0c;特别是在需要动态展示和隐藏节点的情况下。下面我将通过一个具体的示例来讲解实现过程。 需求分析…

Web开发:ABP框架3——入门级别的接口增删改查实现原理

一、上节回顾 运用了ABP框架&#xff0c;使用了EFcore进行增删改查 二、程序的入口 代码解说&#xff1a; public class Program // 定义程序主类 {public async static Task<int> Main(string[] args) // 主方法&#xff0c;返回状态码{// 配置Serilog日志Log.Logger…

【QT】定时器使用

文章目录 关于 Qt 定时器使用的注意细节总结实例-检查工具使用周期时间是否合理UI设计头文件 remind.h源文件 remind.cpp实现效果 关于 Qt 定时器使用的注意细节总结 一、创建与初始化 使用 QTimer 类来创建定时器。可以在构造函数中指定父对象&#xff0c;确保定时器在正确的…

【C++】STL----list常见用法

&#x1f525;个人主页&#x1f525;&#xff1a;孤寂大仙V &#x1f308;收录专栏&#x1f308;&#xff1a;C从小白到高手 &#x1f339;往期回顾&#x1f339;&#xff1a;[C]vector常见用法 &#x1f516; 流水不争&#xff0c;争的是滔滔不息。 文章目录 一、list的介绍li…

【网络通信基础与实践第二讲】包括互联网概述、互联网发展的三个阶段、互联网的组成、计算机网络的体系结构

一、互联网概述 计算机网络是由若干节点&#xff08;node&#xff09;和连接这些节点的链路&#xff08;link&#xff09;组成。 网络之间还可以通过路由器互联起来&#xff0c;这就构成了一个覆盖范围更大的计算机网络。这样的网络称为互联网。 网络把许多计算机连接在一起…

SpringCloud-04 OpenFeign服务调用与负载均衡

OpenFeign是一个声明式、模板化的HTTP客户端&#xff0c;它简化了在Java应用程序中调用RESTful API的过程。OpenFeign是Netflix开发的一个开源项目&#xff0c;它构建在Feign的基础上&#xff0c;为开发者提供了更加简单、灵活的方式来实现HTTP请求。OpenFeign的特点包括&#…

计算机网络:概述 - 性能指标

目录 一. 速率 二. 带宽 三. 吞吐量 四. 时延 五. 时延带宽积 六. 往返时间RTT 七. 利用率 八. 丢包率 此博客介绍计算机网络中的性能指标&#xff0c;性能指标从不同的角度来度量计算机网络的性能。下面介绍几个常用的性能指标&#xff1a; 一. 速率…

服务器非法关闭后MySQL服务启动失败

在写这篇文章前&#xff0c;我弄好了&#xff0c;写完之后把成功安装的几个MySQL都删除了&#xff0c;只留了最后测试成功的服务“mysql-test” ,然后点击运行&#xff0c;发现又出现上图的错误。心态炸了。 本以为定位到问题了&#xff0c;但是这个错误让我迷茫了。我只能临时…