【面试经典150 | 哈希表】快乐数
文章目录
- 写在前面
- Tag
- 题目来源
- 题目解读
- 解题思路
- 方法一:哈希集合判重
- 方法二:快慢指针判重
- 其他语言
- python3
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【哈希集合】【快慢指针】
题目来源
202. 快乐数
题目解读
判断一个数 n 是不是快乐数。
解题思路
在「快乐数」的定义中,我们需要计算整数的每个数位上数字的平方和,需要使用模运算计算每个数位上的数字来对平方和进行累加,这是数位运算的基础操作了,直接贴上代码:
int nextNum(int num) {int val = 0;while (num) {int tmp = num % 10;val += tmp * tmp;num /= 10;}return val;
}
接下来需要重复计算各个数位上数的平方和,我们使用 while() 循环来重复这一计算过程,那什么时候退出循环呢?
答:遇到计算结果为 1 的时候,或者某一计算结果在之前已经出现过了。
计算结果为 1 这个很好理解,这也是符合本题对 「快乐数」的定义。退出循环的第二个条件是这样的,如果某个计算结果重复出现了,那么说明在验证「快乐数」的过程中出现了环,那么永远也不会有平方和为 1 的情况。
判断某个计算结果有没有出现过第二次,就是判断链表中是否有环的问题,这一问题有两种解决方法:
- 哈希集合判重
- 快慢指针判重
具体原理可以参考 【面试经典150 | 循环链表】。
方法一:哈希集合判重
实现代码
class Solution {
public:int nextNum(int num) {int val = 0;while (num) {int tmp = num % 10;val += tmp * tmp;num /= 10;}return val;}bool isHappy(int n) {unordered_set<int> st;while (n != 1 && !st.count(n)) {st.insert(n);n = nextNum(n);}return n == 1;}
};
复杂度分析
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn), n n n 是输入的数。
空间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)。
方法二:快慢指针判重
实现代码
class Solution {
public:int nextNum(int num) {int val = 0;while (num) {int tmp = num % 10;val += tmp * tmp;num /= 10;}return val;}bool isHappy(int n) {int slow = n;int fast = nextNum(n);while (fast != 1 && slow != fast) {slow = nextNum(slow);fast = nextNum(nextNum(fast));}return fast == 1;}
};
复杂度分析
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn), n n n 是输入的数。
空间复杂度: O ( 1 ) O(1) O(1)。
其他语言
python3
以下两段代码来源于 官方题解。
哈希集合判重
def isHappy(self, n: int) -> bool:def get_next(n):total_sum = 0while n > 0:n, digit = divmod(n, 10)total_sum += digit ** 2return total_sumseen = set()while n != 1 and n not in seen:seen.add(n)n = get_next(n)return n == 1
快慢指针判重
def isHappy(self, n: int) -> bool: def get_next(number):total_sum = 0while number > 0:number, digit = divmod(number, 10)total_sum += digit ** 2return total_sumslow_runner = nfast_runner = get_next(n)while fast_runner != 1 and slow_runner != fast_runner:slow_runner = get_next(slow_runner)fast_runner = get_next(get_next(fast_runner))return fast_runner == 1
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。
相关文章:
【面试经典150 | 哈希表】快乐数
文章目录 写在前面Tag题目来源题目解读解题思路方法一:哈希集合判重方法二:快慢指针判重 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为…...
ETL实现实时文件监听
一、实时文件监听的作用及应用场景 实时文件监听是一种监测指定目录下的文件变化的技术,当产生新文件或者文件被修改时,可实时提醒用户并进行相应处理。这种技术广泛应用于数据备份、日志管理、文件同步和版本控制等场景,它可以帮助用户及时…...
Openssl数据安全传输平台003:Protobuf - 部署
文章目录 Github代码仓库位置一、Windows环境配置生成库文件之后—>参考3.3 配置VS1. 先将平台设置为所有平台2. 配置属性 >> C/C >> 常规 >> 附加包含目录3. 配置属性 >> C/C >> 预处理器 >> 预处理器定义,添加4. 配置属性 >> C…...
Proteus仿真--一种智能频率计的设计与制作(AVR单片机+proteus仿真)
本文介绍一种基于AVR单片机实现的一种智能频率计Proteus仿真实现(完整仿真源文件及代码见文末链接) 简介 硬件电路主要分为单片机主控模块、频率计模块、LCD1602液晶显示模块以及串口模块 (1)单片机主控模块:单片机…...
CAS是“Compare and Swap“(比较并交换)
CAS是"Compare and Swap"(比较并交换) 一,介绍 CAS是"Compare and Swap"(比较并交换)的缩写,是一种多线程同步的原子操作。它基于硬件的原子性保证,用于解决并发环境下的…...
前端数据可视化之【series、series饼图配置】配置项
目录 🌟Echarts配置项🌟series🌟饼图 type:pie🌟写在最后 🌟Echarts配置项 ECharts开源来自百度商业前端数据可视化团队,基于html5 Canvas,是一个纯Javascript图表库,提供直观&…...
03.MySQL事务及存储引擎笔记
事务 查看/设置事务 select autocommit; --查看当前数据库的事务状态,1表示开启,0表示关闭 set autocommit 0; --关闭自动事务提交采用关闭自动事务提交我们就可以手动进行事务提交,但是这种设置方式是对整个数据库起作用,一些可…...
input框输入中文时,输入未完成触发事件。Vue中文输入法不触发input事件?
前言 在做搜索输入框时,产品期待实时搜索,就是边输入边搜索,然而对于中文输入法出现的效果,不同的产品可能有不同的意见,有的觉得输入未完成也应该触发搜索。但有的却认为应该在中文输入完成后再触发搜索。我发现在vu…...
ArmSoM-RK3588编解码之mpp解码demo解析:mpi_dec_test
1. 简介 [RK3588从入门到精通] 专栏总目录 mpi_dec_test 是rockchip官方解码 demo 本篇文章进行mpi_dec_test 的代码解析,解码流程解析 2. 环境介绍 硬件环境: ArmSoM-W3 RK3588开发板 软件版本: OS:ArmSoM-W3 Debian11 3.…...
v-for列表渲染
一、v-for迭代数组 <li v-for"(e,index) in emp" :key"e.id">编号{{index1}} 名字{{e.name}} 年龄{{e.age}} </li> e 是循环数组中的每个元素的别名index 是当前循环的下表,从0开始:key 的作用: 是为了给 Vue 一个提示…...
【引流技术】最新头条全自动引流脚本,解放双手自动引流【引流脚本+技术教程】
软件功能: 评论点赞 适用于自己做头条号,去别人评论区截留,点赞,别人会收到提醒,达到回访效果 文章/视频评论 可以自己发布引流文章或视频,引导进你主页或者私信你,达到引流效果 设备需求: 安卓手机8.1及以上系统 文章分享者:Linxiaoyu…...
智能PDU的“智能”体现在哪些方面?
智能PDU是一种用于管理和监控数据中心或其他设施中的电源分配设备,通过引入以太网络、语音服务等新颖的通讯手段,增加了传统机柜PDU插座所不能提供的智能管理控制模块和控制芯片,同时兼具电源分配和管理功能。智能PDU是当今现代化IDC数据中心…...
Flutter和SwiftUI比较
0.语言 SwiftUI 毫无疑问是Swift语言编写, 在2019年正式推出,目前最新是Swift 5.9 (2023年9月),由Apple公司维护和发行; 该编程语言发明人已离职Apple。 语言官网:https://developer.apple.com/swift/ 最好用Xcode编…...
使用ngrok内网穿透后,调用相关接口报ERR_NGROK_6024 异常
header增加:ngrok-skip-browser-warning:69420即可。如下图:...
举个栗子!Alteryx 技巧(6):从 API 中提取数据
你听说过从 API 中提取数据吗?API 是指应用编程接口,是计算机之间或计算机程序之间的连接,它是一种软件接口,让不同的软件进行信息共享。对于很多数据分析师来说,他们常常需要从 API 中提取数据,那么如何快…...
算法、语言混编、分布式锁与分布式ID、IO模型
一、算法初识 数据结构和算法是程序的基石。我们使用的所有数据类型就是一种数据结构(数据的组织形式),写的程序逻辑就是算法。 算法是指用来操作数据、解决程序问题的一组方法。 对于同一个问题,使用不同的算法,也…...
代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和
前言:贪心无套路 本质: 局部最优去推导全局最优 两个极端 贪心算法的难度一般要么特别简单,要么特别困难,所以我们只能多见识多做题,记住无需数学证明,因为两道贪心基本上毫无关系,我们只需要去思考局部最优即可 贪心的小例子 比如有一堆钞票,你可以拿走十张&#x…...
【前端vue面试】TypeScript
目录 快速入门0、TypeScript简介1、TypeScript 开发环境搭建2、基本类型3、编译选项4、webpack5、Babel面向对象1、类(class)2、面向对象的特点3、接口(Interface)4、泛型(Generic)快速入门 0、TypeScript简介 TypeScript是JavaScript的超集。它对JS进行了扩展,向JS中引…...
vue-next-admin框架的认识
最近利用这个框架二开了一个后台管理系统,这里简单介绍一下,后续会进行框架的修改等文章 1:介绍 Vue-next-admin是一个基于Vue3和Element-Plus的后台管理系统框架。它提供了一套完整的、易于扩展的后台管理界面解决方案,可用于快…...
【2024秋招】2023-9-14 最右线下后端开发二面
1 OS 1.1 讲讲什么是虚拟内存,怎么实现的 虚拟内存是一种存储器管理能力,它使得一个应用程序似乎有更多的物理内存(RAM)可用,而实际上,系统使用了一部分硬盘空间来模拟额外的 RAM。通过使用虚拟内存&…...
龙芯k - 走马观碑组MPU驱动移植孟
先回顾:三次握手(建立连接)核心流程(实际版) 为了让挥手流程衔接更顺畅,咱们先快速回顾三次握手的实际核心,避免上下文脱节: 第一步(客户端→服务器)…...
电脑风扇噪音如何解决?智能温控系统全攻略
电脑风扇噪音如何解决?智能温控系统全攻略 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Trending/fa/FanControl…...
SAP MM | 物料主数据:为什么修改了“特殊采购类型”但在 MM04 查不到修改历史?
在 SAP 物料主数据(Material Master)的操作中,用户有时会修改 “特殊采购类型”(SOBSL),比如从“厂内生产”改为“从其他工厂调拨(40)”。但用户说,修改了主数据之后&…...
【技术精讲】从理论到实践:手把手教你完成DFA最小化
1. 什么是DFA最小化?为什么需要它? 想象一下你正在整理一个杂乱无章的衣柜。有些衣服你从来不穿(死状态),有些衣服功能重复(等价状态)。DFA最小化就像给衣柜做断舍离,保留所有必要的…...
2025最权威的六大AI论文网站推荐
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 在当下的学术研究环境里头,若是合理地运用AI写作工具,那么能够有效地…...
013.定时器之系统Tick实现|千篇笔记实现嵌入式全栈/裸机篇
⚠️裸机仓库:https://gitee.com/simonchina_carel_li/mini2440-bare-metal.git ⚠️Tag: 13-sys-tick 1. 为什么要系统Tick? 在前面的SDRAM测试程序中(), 我们有这样的部分, // -- TODO: 如果你有定时器…...
QEMU v8.2.4 源码深度剖析:从编译到核心模块的实战指南
1. 从零开始:编译属于你自己的QEMU v8.2.4 如果你和我一样,对虚拟化技术充满好奇,总想扒开QEMU这头“巨兽”的肚子看看里面到底是怎么运转的,那么从源码编译开始,绝对是最扎实的第一步。这不仅仅是得到一个可执行文件&…...
构建企业级统一认证中心:Spring Boot OAuth2 Server 的架构实践与深度解析
构建企业级统一认证中心:Spring Boot OAuth2 Server 的架构实践与深度解析 【免费下载链接】oauth2-server spring boot (springboot 3) oauth2 server sso 单点登录 认证中心 JWT,独立部署,用户管理 客户端管理 项目地址: https://gitcode.com/gh_mirrors/oau/oa…...
如何提高邮件营销的投资回报率
在与大量客户的长期沟通中,我发现一个非常有趣的现象,即大家对邮件营销的投资回报率出现了两极分化的评价:一部分企业认为邮件营销的效果非常一般,发着发着就不发了;而另一部分企业认为,邮件营销的投资回报…...
智能车浅谈——电机控制篇
文章目录前言运动控制系统被控对象执行机构控制器反馈环节M法测速:T法测速小结直流调速系统桥式可逆PWM变换器(1)正向运行(2)反向运行总结智能车系列文章汇总前言 之前借用自动控制原理对智能车的方向控制做了一个简单…...
