【优选算法】——Leetcode——202—— 快乐数

 

目录

1.题目 

2. 题⽬分析:

3.简单证明:

4. 解法(快慢指针):

算法思路:

补充知识:如何求⼀个数n每个位置上的数字的平⽅和。

 总结概括

 5.代码实现

1.C语言

2.C++


1.题目 

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2:

输入:n = 2
输出:false

提示:

  • 1 <= n <= 231 - 1

2. 题⽬分析:


为了⽅便叙述,将「对于⼀个正整数,每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个操作记为 x 操作;
题⽬告诉我们,当我们不断重复 x 操作的时候,计算⼀定会「死循环」,死的⽅式有两种:
▪ 情况⼀:⼀直在 1 中死循环,即 1 -> 1 -> 1 -> 1...... 
▪ 情况⼆:在历史的数据中死循环,但始终变不到 1 
由于上述两种情况只会出现⼀种,因此,只要我们能确定循环是在「情况⼀」中进⾏,还是在「情
况⼆」中进⾏,就能得到结果。 

3.简单证明:


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. 提取每⼀位的时候,⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和
▪ tmp = tmp + t * t

 总结概括

1.定义快慢指针
2.慢指针每次向后移动一步快指针每次向后移动两步
3.判断相遇时候的值即可

 5.代码实现

1.C语言

 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;
}

2.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;
}
}
;

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

论文复现和点评《基于随机森林模型的个人信用风险评估研究》

作者Toby&#xff0c;来源公众号&#xff1a;Python风控模型&#xff0c;论文复现和点评《基于随机森林模型的个人信用风险评估研究》 最近Toby老师看到一篇论文热度比较高&#xff0c;下载量有665次&#xff0c;论文标题是《基于随机森林模型的 个人信用风险评估研究》 论文篇…

陪诊系统|陪诊小程序成品|陪诊系统功能

随着人们对健康的日益关注以及医疗技术的不断进步&#xff0c;陪诊小程序应运而生&#xff0c;通过提供陪同就医、医疗服务和健康管理等功能为患者和家庭成员提供了更多的便利和选择。本文将分析陪诊小程序的关键功能&#xff0c;以便更好地理解其在医疗领域的作用。 在陪诊小程…

练习项目后端代码解析注解篇(annotation)

前言 本来想从接口处入手的&#xff0c;但是一下看到接口里几十个方法&#xff0c;眼睛有点抗拒&#xff0c;想想还是先看作者写的自定义注解吧。 项目里有三个自定义注解&#xff1a; 分别是AccessLimit注解、OperationLogger注解、VisitLogger注解 AccessLimit注解 这是一…

Summer ‘24来啦!15个最热门的功能抢先看!

Salesforce Summer 24即将发布&#xff01;本篇文章我们将深入了解Summer 24最热门的声明性功能。 01 自动化Lightning应用程序 新的自动化Lightning应用程序中包含所有与自动化相关的内容。访问该应用程序的用户可以在主应用程序中看到Flow、错误信息和其他基于社区的链接。…

自动驾驶主流芯片及平台架构(一)

零部件成本下降、中低端车竞争加剧&#xff0c;推动ADAS渗透率在中国市场快速提升&#xff0c;自主品牌ADAS装配量大幅提升 零部件成本下降、中低端车竞争加剧&#xff0c;推动ADAS渗透率在中国市场快速提升&#xff0c;自主品牌ADAS装配量大幅提升。5年前在一些高端车型上才有…

【JVM】类加载机制及双亲委派模型

目录 一、类加载过程 1. 加载 2. 连接 a. 验证 b. 准备 c. 解析 3. 初始化 二、双亲委派模型 类加载器 双亲委派模型的工作过程 双亲委派模型的优点 一、类加载过程 JVM的类加载机制是JVM在运行时&#xff0c;将 .class 文件加载到内存中并转换为Java类的过程。它…

【硬核科普】一文读懂生成对抗网络GAN

0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&#xff0c;虽然参考了他人的宝贵见解及成果&#xff0c;但是内容可能存在不准确的地方。如果发现文中错误&#xff0c;希望批评指正&#xff0c;共同进步。 本文基于Ian在2014年发表在NIPS的论…

GDPU 天码行空11

&#xff08;一&#xff09;实验目的 1、掌握JAVA中IO中各种类及其构造方法&#xff1b; 2、重点掌握IO中类所具有的IO操作方法&#xff1b; 3、熟悉软件中登录模块的开发方法&#xff1b; 4、掌握IO中读写常用方法。 5、进一步熟悉正则规则的使用方法。 &#xff08;二&…

GT资源-Clock资源

一、Transmitter 时钟分布 XCLK&#xff1a;在使用TX buffer的模式下&#xff0c;XCLK来源于TXOUTCLK。在使用TX bypassing的模式下XCLK来源于TXUSERCLK。TXUSRCLK是GTX/GTH中PCS的内部逻辑时钟。TXUSRCLK2是GT Transceiver 用户侧逻辑时钟。 TXUSRCLK与TXUSRCLK2的关系 FPGA …

聚类分析:使用R语言对Iris数据集进行K均值聚类

引言 聚类分析是一种常用的无监督学习技术&#xff0c;旨在将数据集中的样本分成具有相似特征的组。K均值聚类是其中一种常见的方法&#xff0c;它通过将数据点划分为K个簇&#xff0c;并使每个数据点与其所属簇的中心点距离最小化来实现聚类。本文将介绍如何使用R语言执行K均…

奥威-金蝶BI现金流量表模板,可借鉴、可套用

企业现金流一旦出了问题都是大问题&#xff0c;会直接影响到企业的日常运作&#xff0c;甚至直接关系到企业能不能继续存活&#xff0c;因此现金流量表是企业财务分析中重要报表之一&#xff0c;也是企业监控财务监控情况的重要手段之一。那么这么重要的一份现金流量表该怎么做…

羊大师解读,当代年轻人焦虑应对指南

羊大师解读&#xff0c;当代年轻人焦虑应对指南 当代年轻人面临焦虑问题时&#xff0c;羊大师提出以下综合建议&#xff0c;要增强自我认知了解自身的需求和期望&#xff0c;明确自己的价值观和目标。这有助于避免盲目跟风和过度比较&#xff0c;从而减轻不必要的焦虑。 合理规…

Mybatis-Plus大批量插入数据到MySQL

MyBatis-Plus的saveBatch方法 GetMapping("/save1") public void save1() {// 数据准备List<MallOrder> orderList getMallOrderList();// mybatis-pluslong start System.currentTimeMillis();mallOrderService.saveBatch(orderList);System.out.println(&…

做私域,朋友圈到底该怎么发?

说到做私域&#xff0c;很多人都会问&#xff1a;朋友圈该怎么发&#xff1f;相信大家的朋友圈早已经被各种广告攻占了&#xff0c;很多也都被大家屏蔽了。但如果要做私域&#xff0c;单纯发广告是行不通的&#xff0c;可是现在依然有很多人&#xff0c;认为做私域就是狂发朋友…

RabbitMQ的介绍和使用

1.同步通讯和异步通讯 举个例子&#xff0c;同步通讯就像是在打电话&#xff0c;因此它时效性较强&#xff0c;可以立即得到结果&#xff0c;但如果你正在和一个MM打电话&#xff0c;其他MM找你的话&#xff0c;你们之间是不能进行消息的传递和响应的 异步通讯就像是微信&#…

美国纽扣电池UL4200A及16CFR1262标准亚马逊要求

2023年9月21日&#xff0c;美国消费品安全委员会CPSC(Consumer Product Safety Commission) 决定采用UL 4200A-2023&#xff08;包含纽扣电池或硬币电池的产品安全标准&#xff09;作为包含纽扣电池或硬币电池的消费品的强制性消费品安全规则&#xff0c;相关要求同时被编入到1…

前端数据可视化基础(折线图)

目录 前言&#xff1a; 画布&#xff1a; 折线图 (Line Chart): 前言&#xff1a; 前端中的数据可视化是指将大量数据以图形或图像的形式在前端页面上展示出来&#xff0c;以便用户能够更直观地理解和分析这些数据。数据可视化是一种强大的工具&#xff0c;它利用了人类视觉…

《架构思维:从程序员到CTO》:通往顶级架构师之路

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…

使用excel合理整理数据

使用excel合理整理数据 Excel函数LOOKUP把两个sheet数据关联起来LOOKUP函数 Excel函数LOOKUP把两个sheet数据关联起来 LOOKUP函数 需求场景 1、sheet1是视频的数据比如 aid、作者、视频信息 2、sheet2是视频的播放数据比如 aid vv uv等 做的就是根据1、2 的aid 将 sheet2中的所…

多目标灰狼算法(MOGWO):原理讲解与代码实现 Matlab代码免费获取

声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原理简介 一、Pareto最优概念 二、单目标G…