【面试经典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

写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第二证券:风电概念强势拉升,威力传动“20cm”涨停,双一科技等大涨

风电概念20日盘中强势拉升&#xff0c;到发稿&#xff0c;威力传动“20cm”涨停&#xff0c;双一科技涨超17%&#xff0c;顺发恒业亦涨停&#xff0c;金雷股份、大金重工涨约7%&#xff0c;新强联、海力风电涨超5%。 音讯面上&#xff0c;9月以来江苏、广东海风项目加快推动&a…

第十五章 I/O(输入/输出)流

15.1 输入/输出流 流是一组有序的数据序列&#xff0c;可分为输入流和输出流两种。 程序从指向源的输入流中读取源中数据&#xff0c;源可以是文件、网络、压缩包或者其他数据源 输出流的指向是数据要到达的目的地&#xff0c;输出流的目标可以是文件、网络、压缩包、控制台和…

机器学习笔记 - 特斯拉的占用网络简述

一、简述 ​ 2022 年,特斯拉宣布即将在其车辆中发布全新算法。该算法被称为occupancy networks,它应该是对Tesla 的HydraNet 的改进。 自动驾驶汽车行业在技术上分为两类:基于视觉的系统和基于激光雷达的系统。后者使用激光传感器来确定物体的存在和距离,而视觉系统…

【tg】6: MediaManager的主要功能

【tg】2:视频采集的输入和输出 的管理者是 media manager‘ media 需要 network的支持:NetworkInterface friend class MediaManager::NetworkInterfaceImpl;NetworkInterfaceImpl 直接持有 MediaManager 的指针即可:发送rtp包、rtcp包、设置socket选项?

小程序 swiper滑动

整个红色区域为可滑动区域&#xff0c;数字1区域为展示区域&#xff0c;数字2为下一个展示模块 <scroll-view class"h_scroll_horizontal" enhanced"ture" bind:touchend"touchEnd" bind:touchstart"touchStart"><view clas…

从昏暗到明亮—改善照明环境,提升编程效率

作为一名程序员博主&#xff0c;长时间写代码、写博客&#xff0c;对着电脑屏幕的生活方式已经渐渐成为了我的日常。 然而&#xff0c;这种生活方式却给我的眼睛带来了相当大的压力。每当一天的工作结束&#xff0c;我的眼睛总是感到干涩、疲劳&#xff0c;让我感到不舒适。&am…

基于C语言 --- 自己写一个通讯录

C语言程序设计笔记---039 C语言之实现通讯录1、介绍C/C程序的内存开辟2、C语言实现通讯录2.1、ContactMain.c程序大纲2.2、Contact2.h2.3、Contact2.c2.3.1 InitContact( )初始化通讯录函数2.3.2 AddContact( )添加联系人和CheckCapaticy( )检查容量函数2.3.3、ShowContact( )显…

模式识别——高斯分类器

模式识别——高斯分类器 需知定义特殊情况&#xff08;方差一致&#xff09;Sigmoid 需知 所有问题定义在分类问题下&#xff0c;基于贝叶斯决策 定义 条件概率为多元高斯分布&#xff0c;此时观测为向量 X X 1 , X 2 , . . . , X n X{X_1,X_2,...,X_n} XX1​,X2​,...,Xn​…

Docker Service 创建

Docker Swarm Mode Docker Swarm 集群搭建 Docker Swarm 节点维护 Docker Service 创建 service 只能依附于 docker swarm 集群&#xff0c;所以 service 的创建前提是&#xff0c;swarm 集群搭建完毕。 1. 创建 service docker service create 命令用于创建 service&#xff…

【C++项目】高并发内存池第二讲中心缓存CentralCache框架+核心实现

CentralCache 1.框架介绍2.核心功能3.核心函数实现介绍3.1SpanSpanList介绍3.2CentralCache.h3.3CentralCache.cpp3.4TreadCache申请内存函数介绍3.5慢反馈算法 1.框架介绍 回顾一下ThreadCache的设计&#xff1a; 如图所示&#xff0c;ThreadCache设计是一个哈希桶结构&…

前端领域的插件式设计

插件&#xff0c;是一个常见的概念。 例如&#xff0c;当我们需要把我们前端代码中的 css 样式提取打包&#xff0c;我们可以用 webpack 的 mini-css-extract-plugin&#xff0c;或者你如果用 rollup 的话&#xff0c;可以选择 rollup-plugin-postcss。 再比如我们可以给 bab…

RDB.js:适用于 Node.js 和 Typescript 的终极对象关系映射器

RDB.js 是适用于 Node.js 和 Typescript 的终极对象关系映射器&#xff0c;可与 Postgres、MS SQL、MySQL、Sybase SAP 和 SQLite 等流行数据库无缝集成。无论您是使用 TypeScript 还是 JavaScript&#xff08;包括 CommonJS 和 ECMAScript&#xff09;构建应用程序&#xff0c…

X32位汇编和X64位区别无参函数分析(一)

前言 一、X32汇编函数无参无返回分析 二、X64汇编函数无参无返回分析 总结 前言 提示&#xff1a;以下是个人学习总结&#xff1a;如有错误请大神指出来&#xff0c;只供学习参考&#xff0c;本内容使用使用VS2017开发工具&#xff1a;语言是C&#xff0c;需要一些常见的汇编指…

MySQL1——喵喵期末不挂科

宝宝&#xff0c;你不点个赞吗&#xff1f;不评个论吗&#xff1f;不收个藏吗&#xff1f; 最后的最后&#xff0c;关注我&#xff0c;关注我&#xff0c;关注我&#xff0c;你会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的很重要…

阶段六-Day04-MyBatis2

一、别名 Alias 1. 为什么使用别名 一般映射文件中会包含大量<select>标签, 每个<select>中都需要配置resultType"com.bjsxt.pojo.People"&#xff0c;MyBatis提供了别名机制可以对某个类起别名或给某个包下所有类起别名&#xff0c;简化resultType取值…

sklearn-6算法链与管道

思想类似于pipeline&#xff0c;将多个处理步骤连接起来。 看个例子&#xff0c;如果用MinMaxScaler和训练模型&#xff0c;需要反复执行fit和tranform方法&#xff0c;很繁琐&#xff0c;然后还要网格搜索&#xff0c;交叉验证 1 预处理进行参数选择 对于放缩的数据&#x…

性能测试 —— Jmeter 命令行详细

我们在启动Jmeter时 会看见&#xff1a;Don’t use GUI mode for load testing !, only for Test creation and Test debugging.For load testing, use CLI Mode (was NON GUI) 这句话的意思就是说&#xff0c;不要使用gui模式进行负载测试&#xff0c;gui模式仅仅是创建脚本…

Unity 通过jar包形式接入讯飞星火SDK

最近工作上遇到了要接入gpt相关内容的需求&#xff0c;简单实现了一个安卓端接入讯飞星火的UnitySDK。 或者也可以接入WebSocket接口的。本文只讲安卓实现 我使用的Unity版本为2021.3.27f1c2 Android版本为4.2.2 1.下载SDK 登陆讯飞开放平台下载如图所示SDK 2.新建安卓工程…

【广州华锐互动】关于物理力学的3D实验实操平台

在科学的广阔领域中&#xff0c;物理力学是一个至关重要的分支&#xff0c;它探索了物体在力作用下的运动规律。然而&#xff0c;传统的物理实验往往需要复杂的设备和大量的操作&#xff0c;这对于学生来说是一项巨大的挑战。为了解决这个问题&#xff0c;广州华锐互动开发了物…

django 商品及购物车逻辑实现

基于类视图模式实现商品分类菜单接口开发 创建菜单子应用 python manage.py startapp menu测试 apps/menu/views from django.http import HttpResponse from django.views import Viewclass GoodsMainMenu(View):def get(self,request):print("get请求")return …