【面试经典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。通过使用虚拟内存&…...
20个核心AI概念拆解:小白也能轻松入门大模型,收藏这份学习秘籍!
本文以通俗易懂的方式,拆解了20个AI领域的核心概念,涵盖神经网络、迁移学习、Transformer架构、大语言模型等。通过比喻和实例,帮助读者理解AI底层逻辑,消除学习AI的障碍。文章强调AI并非高不可攀,只要掌握基本原理&am…...
Cosmos-Reason1-7B作品集:覆盖IMO/CMO/AMC等国际数学竞赛真题解析
Cosmos-Reason1-7B作品集:覆盖IMO/CMO/AMC等国际数学竞赛真题解析本文展示Cosmos-Reason1-7B在数学竞赛真题解析中的实际效果,所有案例均基于真实题目生成1. 工具简介:你的本地数学竞赛解题助手 Cosmos-Reason1-7B是一款专门针对推理任务优化…...
Flutter 三方库结合鸿蒙6.0+(API20+)开发实践案例教程
欢迎加入开源鸿蒙跨平台社区:https://openharmonycrossplatform.csdn.net 本文面向鸿蒙新手开发者,结合具体项目案例,详细讲解如何使用 Flutter 开发鸿蒙6.0以上(API20及以上)应用,并集成常用三方库实现核…...
终极指南:如何免费让Figma界面全中文,设计师工作效率提升秘籍
终极指南:如何免费让Figma界面全中文,设计师工作效率提升秘籍 【免费下载链接】figmaCN 中文 Figma 插件,设计师人工翻译校验 项目地址: https://gitcode.com/gh_mirrors/fi/figmaCN FigmaCN是一款专为中文用户打造的免费本地化插件&a…...
绩效考核软件避坑实录:为什么你觉得绩效考核软件”不好用”
好用的绩效考核软件应该具备灵活的考核模板配置、自动化流程推进、多维度数据分析三大核心能力。 2026年主流绩效考核软件已普遍集成AI能力,可将绩效评估周期从平均2周压缩到3天,同时减少70%以上的人为评分偏差。选择时重点关注系统的配置灵活度、与现有…...
向量嵌入性能骤降70%?EF Core 10 + ANN索引配置错误全解析,含官方未文档化AsVectorSearch()调用约束
第一章:向量嵌入性能骤降70%?EF Core 10 ANN索引配置错误全解析,含官方未文档化AsVectorSearch()调用约束当升级至 EF Core 10 并启用向量相似性搜索时,大量开发者报告 AsVectorSearch() 查询响应时间激增、QPS 下跌近 70%&#…...
短剧小程序系统选型指南:为什么1%加密+99%开源是最优解?
最近半年,短剧赛道持续火爆,不少开发者和创业者找我咨询短剧小程序的源码选型问题。我自己带团队从零到一搭建了一套日活过万的短剧平台,期间踩过SaaS的坑、全加密的坑、所谓“全开源”的坑,最终落地了一套1%核心加密99%全开源的方…...
使用钉钉远程操作你的claude code拘
先回顾:三次握手(建立连接)核心流程(实际版) 为了让挥手流程衔接更顺畅,咱们先快速回顾三次握手的实际核心,避免上下文脱节: 第一步(客户端→服务器)…...
如何快速安装Hollow Knight模组:Scarab模组管理器的完整指南
如何快速安装Hollow Knight模组:Scarab模组管理器的完整指南 【免费下载链接】Scarab An installer for Hollow Knight mods written in Avalonia. 项目地址: https://gitcode.com/gh_mirrors/sc/Scarab 厌倦了手动下载和安装Hollow Knight模组的繁琐过程&am…...
通俗易懂讲透超参数优化
通俗易懂讲透超参数优化(本科生/研究生都能看懂) 本文用大白话生活案例公式拆解完整代码,把超参数优化从概念、方法、对比到实战讲得清清楚楚,适合机器学习入门、面试复习、课程笔记。 一、先搞懂:什么是超参数优化&a…...
