LeetCode每日一题之专题一:双指针 ——快乐数

快乐数OJ链接:202. 快乐数 - 力扣(LeetCode)

题目:

题目分析:
为了房便叙述,将「对于⼀个正整数,每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个
操作记为 x 操作;
题目告诉我们,当我们不断重复 x 操作的时候,计算⼀定会「死循环」,死的方式有两种:
▪ 情况⼀:⼀直在 1 中死循环,即 1 -> 1 -> 1 -> 1...... 
▪ 情况⼆:在历史的数据中死循环,但始终变不到 1 
由于上述两种情况只会出现⼀种,因此,只要我们能确定循环是在「情况⼀」中进行,还是在「情
况⼆」中进行,就能得到结果。
简单证明:
a. 经过⼀次变化之后的最⼤值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最
⼤ 9999999999 ),也就是变化的区间在 [1, 810] 之间;
b. 根据「鸽巢原理」,⼀个数变化 811 次之后,必然会形成⼀个循环;
c. 因此,变化的过程最终会走到⼀个圈⾥面,因此可以用「快慢指针」来解决。
4. 解法(快慢指针):
算法思路:
根据上述的题目分析,我们可以知道,当重复执行 x 的时候,数据会陷入到⼀个「循环」之中。
⽽「快慢指针」有⼀个特性,就是在⼀个圆圈中,快指针总是会追上慢指针的,也就是说他们总会
相遇在⼀个位置上。如果相遇位置的值是 1 ,那么这个数⼀定是快乐数;如果相遇位置不是 1 
的话,那么就不是快乐数。
补充知识:如何求⼀个数n每个位置上的数字的平方和。
a. 把数 n 每⼀位的数提取出来:
循环迭代下面步骤:
i. int t = n % 10 拿到个位;
ii. n /= 10 噶掉个位;
直到 n 的值变为 0 ;
b. 提取每⼀位的时候,用⼀个变量 sum 记录这⼀位的平方与之前提取位数的平方和
▪ sum = sum + t * t

 

C++:

class Solution
{
public:
    int bitSum(int n)//返回 n 这个数每⼀位上的平⽅和
    {
        int sum = 0;
        while (n)
        {
            int t = n % 10;//拿到个位上的数
            sum += t * t;//个位上数的平方和
            n /= 10;//用完就噶掉一位数
        }
        return sum;
    }
    bool isHappy(int n)
    {
        int slow = n, fast = bitSum(n);
        while (slow != fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }
};

运行结果:

PS:看到这里了,码字不易,给个一键三连鼓励一下吧!有不足或者错误之处欢迎在评论区指出!  

 

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

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

相关文章

Shell脚本之基础-2

目录 一、字符处理 cut命令 awk命令 sed命令 字符串排序 二、条件判断 文件类型判断 文件权限判断 两个文件的判断 整数比较 字符串判断 多重判断 三、流程控制 if分支 if else 双分支结构 case分支 for循环 while循环 一、字符处理 cut命令 命令格式&#x…

Python 金融数据分析工具库之zvt使用详解

​​​​​​​ 概要 Python在金融数据分析领域有着广泛的应用,而zvt库作为一款强大的金融数据分析工具,为开发者提供了丰富的功能和灵活的应用接口。本文将深入介绍zvt库的安装、特性、基本功能、高级功能、实际应用场景,并总结其在金融数据分析中的价值和优势。 安装 …

mysql故障排查

MySQL是目前企业最常见的数据库之一日常维护管理的过程中,会遇到很多故障汇总了常见的故障,MySQL默认配置无法满足高性能要求 一 MySQL逻辑架构图 客户端和连接服务核心服务功能存储擎层数据存储层 二 MySQL单实例常见故障 故障1 ERROR 2002 (HY000)…

(echarts)title和legend不重叠/legend图例滚动显示不换行

(echarts)title和legend不重叠/legend图例滚动显示不换行 title和legend都被放置在了不同的位置,从而避免了重叠。你可以根据实际的图表布局和需求调整left(水平位置)和top(垂直位置)等属性,确保它们不会相…

【SCI绘图】【箱型图系列1 python】多类对比及各类下属子类对比

SCI,CCF,EI以及核心期刊绘图宝典,爆款更新,助力科研! 本期分享: 【SCI绘图】【箱型图系列1】多类对比各类下属子类对比 文末附带完整代码: 1.环境准备 python 3 from matplotlib import pyp…

QT-QPainter

QT-QPainter 1.QPainter画图  1.1 概述  1.1 QPainter设置  1.2 QPainter画线  1.3 QPainter画矩形  1.4 QPainter画圆  1.5 QPainter画圆弧  1.6 QPainter画扇形 2.QGradient  2.1 QLinearGradient线性渐变  2.2 QRadialGradient径向渐变  2.3 QConicalGr…

【Unity每日一记】如何从0到1将特效图集制作成一个特效

👨‍💻个人主页:元宇宙-秩沅 👨‍💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍💻 本文由 秩沅 原创 👨‍💻 收录于专栏:Uni…

Prometheus+grafana环境搭建Nginx(docker+二进制两种方式安装)(六)

由于所有组件写一篇幅过长,所以每个组件分一篇方便查看,前五篇链接如下 Prometheusgrafana环境搭建方法及流程两种方式(docker和源码包)(一)-CSDN博客 Prometheusgrafana环境搭建rabbitmq(docker二进制两种方式安装)(二)-CSDN博客 Prometheusgrafana环…

数据分析python代码——数据填充

在Python中,我们通常使用pandas库来处理和分析数据。数据填充是数据预处理的一个重要步骤,用于处理数据中的缺失值。以下是使用pandas库进行数据填充的示例代码: 在数据分析中,处理缺失值(空值)是一个重要…

基于微信小程序的实验室预约系统的设计与开发

个人介绍 hello hello~ ,这里是 code袁~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 🦁作者简介:一名喜欢分享和记录学习的…

c语言文件操作(超详细)

前言 这次的博客,可以让大家快速掌握文件操作,方便大家快速找到不懂的内容 文件操作的作用以及基础 1. 为什么使用文件? 如果没有文件,我们写的程序的数据是存储在电脑的内存中,如果程序退出,内存回收&…

(arxiv2401) CrossMAE

作者团队来自加州大学伯克利分校(UC Berkeley)和加州大学旧金山分校(UCSF)。论文主要探讨了在MAE的解码中,图像patch之间的依赖性,并提出了一种新的预训练框架 CrossMAE。 论文的主要贡献包括: …

代码随想录-算法训练营day02【滑动窗口、螺旋矩阵】

专栏笔记:https://blog.csdn.net/weixin_44949135/category_10335122.html https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG?uc71ed002e4554fee8c262b2a4a4935d8977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结 建议…

(源码+部署+讲解)基于Spring Boot和Vue的大学生快递代取服务平台的设计与实现

一、引言 本报告旨在详细阐述基于Spring Boot后端框架和Vue前端框架的大学生快递代取服务平台的设计与实现过程。该平台旨在为大学生提供便捷的快递代取服务,解决因时间冲突或距离过远而无法及时取件的问题。通过该平台,用户可以发布代取需求&#xff0c…

[中级]软考_软件设计_计算机组成与体系结构_07_存储系统

存储系统 层次划存储概念图局促性原理分类存储器位置存取方式按内容存储按地址存储 工作方式拓展 往年真题 高速缓存(cache)概念案例解析:求取平均时间 Cache与主存的地址映射映像往年真题 主存编制计算编址大小的求取编址与计算存储单元编址内容总容量求取例题解析…

java爬虫入门程序

<!--爬虫仅支持1.8版本的jdk--> <!-- 爬虫需要的依赖--> <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId><version>4.5.2</version> </dependency><!-- 爬虫需…

github生成新的SSH密钥

首先是参考官方文档 生成新的 SSH 密钥并将其添加到 ssh-agent述 当你在创建SSH密钥时遇到提示&#xff1a; Enter file in which to save the key (/c/Users/YOU/.ssh/id_ALGORITHM):这一步是让你选择保存生成的SSH密钥对的文件名和位置。如果你直接按回车键&#xff08;[Pr…

Java项目:基于Springboot+vue实现的医院住院管理系统设计与实现(源码+数据库+开题报告+任务书+毕业论文)

一、项目简介 本项目是一套基于Springbootvue实现的医院住院管理系统设 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简…

Activity入门2——生命周期与任务栈

OnCreate与OnDestroy OnCreate&#xff1a;创建一个活动。 OnDestroy&#xff1a;销毁一个活动。 假设某个用户在一个活动里输入了一些信息&#xff0c;用户由于某些原因退出了该活动&#xff0c;返回时希望能够还原之前输入的信息&#xff0c;不然重新输入就太麻烦了。 pub…

软考高级架构师:嵌入式软件开发概念和例题

一、AI 讲解 嵌入式软件开发和传统软件开发的差异 嵌入式软件开发与传统软件开发在目标、环境和开发过程等方面有显著的差异。下面通过对比的方式&#xff0c;简要阐述这些差异所在&#xff1a; 特性嵌入式软件开发传统软件开发开发目标针对特定硬件系统&#xff0c;强调软硬…