简单题学打表法

简介: 简单题学打表法

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 401. 二进制手表 ,难度为 简单


Tag : 「打表」、「二进制」


二进制手表顶部有 4 个 LED 代表 小时(0-11),底部的 6 个 LED 代表 分钟(0-59)。


每个 LED 代表一个 0 或 1,最低位在右侧。


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


网络异常,图片无法展示
|


(图源:WikiMedia - Binary clock samui moon.jpg ,许可协议:Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) )


给你一个整数 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


打表



具体的,我们可以创建一个 静态数据结构 来存储打表信息(需确保全局唯一,即使存在多组测试数据只生成一次打表数据)。


然后在返回数据的时候直接 O(1)O(1) 查表返回。


PS. 如果打表逻辑计算量接近 10^7107 上限,可以考虑放到本地去做,这里数据量较少,直接放到 static 代码块去做即可。


代码:


class Solution {    
    // 打表逻辑,也可以放到本地做
    // 注意使用 static 修饰,确保打表数据只会被生成一次
    static Map<Integer, List<String>> map = new HashMap<>();
    static {
        for (int h = 0; h <= 11; h++) {
            for (int m = 0; m <= 59; m++) {
                int tot = getCnt(h) + getCnt(m);
                List<String> list = map.getOrDefault(tot, new ArrayList<String>());
                list.add(h + ":" + (m <= 9 ? "0" + m : m));
                map.put(tot, list);
            }
        }
    }
    static int getCnt(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans++;
        return ans;
    }
    static int lowbit(int x) {
        return x & -x;
    }
    public List<String> readBinaryWatch(int t) {
        return map.getOrDefault(t, new ArrayList<>());
    }
}
复制代码


  • 时间复杂度:O(1)O(1)
  • 空间复杂度:O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.401 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
负载均衡 算法 5G
m基于5G通信的超密集网络多连接负载均衡和资源分配算法matlab仿真
m基于5G通信的超密集网络多连接负载均衡和资源分配算法matlab仿真
409 4
|
存储 安全 API
【嵌入式系统】DMA工作原理与常用函数解析
【嵌入式系统】DMA工作原理与常用函数解析
1160 0
【嵌入式系统】DMA工作原理与常用函数解析
|
SQL 分布式计算 Hadoop
Azkaban【基础 01】核心概念+特点+Web界面+架构+Job类型(一篇即可入门Azkaban工作流调度系统)
【2月更文挑战第6天】Azkaban【基础 01】核心概念+特点+Web界面+架构+Job类型(一篇即可入门Azkaban工作流调度系统)
1039 0
|
10月前
|
移动开发 前端开发 Java
Java最新图形化界面开发技术——JavaFx教程(含UI控件用法介绍、属性绑定、事件监听、FXML)
JavaFX是Java的下一代图形用户界面工具包。JavaFX是一组图形和媒体API,我们可以用它们来创建和部署富客户端应用程序。 JavaFX允许开发人员快速构建丰富的跨平台应用程序,允许开发人员在单个编程接口中组合图形,动画和UI控件。本文详细介绍了JavaFx的常见用法,相信读完本教程你一定有所收获!
8985 5
Java最新图形化界面开发技术——JavaFx教程(含UI控件用法介绍、属性绑定、事件监听、FXML)
|
机器学习/深度学习
从RMSE和MSE到更多选择:探索机器学习模型性能指标
从RMSE和MSE到更多选择:探索机器学习模型性能指标
|
Linux 开发工具 Anolis
手把手教学直播:如何提交 PR 成为龙蜥社区贡献者? | 龙蜥大讲堂第 23 期
零基础了解如何提交 PR,以及如何提交 issue、bug、comment 等流程。
手把手教学直播:如何提交 PR 成为龙蜥社区贡献者? | 龙蜥大讲堂第 23 期
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
9天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
404 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话