Leetcode11-快乐数(202)

1、题目

编写一个算法来判断一个数 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、解

快慢指针法
通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针,但数据仍然形成链表结构。起始数字是链表的头 “节点”,链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。

意识到我们实际有个链表,那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手,一个跑的快,一个跑得慢。在龟兔赛跑的寓言中,跑的慢的称为 “乌龟”,跑得快的称为 “兔子”。

不管乌龟和兔子在循环中从哪里开始,它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点(在它们的移动方向上)。
在这里插入图片描述

算法

我们不是只跟踪链表中的一个值,而是跟踪两个值,称为快跑者和慢跑者。在算法的每一步中,慢速在链表中前进 1 个节点,快跑者前进 2 个节点(对 getNext(n) 函数的嵌套调用)。

如果 n 是一个快乐数,即没有循环,那么快跑者最终会比慢跑者先到达数字 1。

如果 n 不是一个快乐的数字,那么最终快跑者和慢跑者将在同一个数字上相遇。

int bitNumberPow(int n)
{int tempSum = 0;//先求每位数的平方和while(n > 0){int temp = n % 10;tempSum += pow(temp, 2);n = n / 10;}return tempSum;
}
bool isHappyA(int n)
{int fast = n;int slow = n;do{fast = bitNumberPow(fast);fast = bitNumberPow(fast);slow = bitNumberPow(slow);} while (fast != slow);return 1 == slow;
}

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

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

相关文章

网络通信理论-入门1

网口框架 100M 2. 物理层解读 2.1 同步的方法&#xff1a;编码 为了让接收方在没有外部时钟参考的情况也能确定每一位的起始、结束和中间位置&#xff0c;在传输信号时不直接采用二进制编码。在 10BASE-T 的传输方式中采用曼彻斯特编码&#xff0c;在 100BASE-T 中则采用 4B/…

cJSON代码解读

1、背景 cJSON用了很久&#xff0c;但是对它一直不太了解。这次向添加对long long类型的支持&#xff0c;一直出问题。因为有以前添加两位小数float的经历&#xff0c;我觉得会很轻松&#xff0c;没想到翻车了。于是有了这边文档&#xff0c;阅读了部分博主对cJSON的解析&…

02--数据定义语言DDL

1、数据定义语言DDL 1.1 操作数据库-DDL 创建数据库 create database 数据库名称; 创建数据库&#xff0c;并指定字符集 create database 数据库名称 character set 字符集名; 查询所有数据库的名称 show databases; 查询某个数据库的字符集:查询某个数据库的创建语句及字…

SpringBoot: 通过MyBatis访问ClickHouse

一、ClickHouse中建表&#xff0c;添加数据 二、SpringBoot项目添加mybatis、clickhouse、druid相关依赖 <dependency><groupId>com.alibaba</groupId><artifactId>druid</artifactId><version>1.2.6</version></dependency>…

stm32 HAL库 4096线ABZ编码器

[TOC]目录 ABZ编码器 4096线 买的是这个 AB相代表计数方向&#xff0c;Z代表过零点 cubemx配置 定时器Encoder 也可以选上DMA 中断 Z相GPIO中断 找一个空闲管脚 打开对应中断 代码 不用DMA int main(void) {short Enc_cnt 0;HAL_TIM_Encoder_Start_IT(&ht…

CSS 向上扩展动画

上干货 <template><!-- mouseenter"startAnimation" 表示在鼠标进入元素时触发 startAnimation 方法。mouseleave"stopAnimation" 表示在鼠标离开元素时触发 stopAnimation 方法。 --><!-- 容器元素 --><div class"container&q…

逻辑回归(LR)----机器学习

基本原理 逻辑回归&#xff08;Logistic Regression&#xff0c;LR&#xff09;也称为"对数几率回归"&#xff0c;又称为"逻辑斯谛"回归。 logistic回归又称logistic 回归分析 &#xff0c;是一种广义的线性回归分析模型&#xff0c;常用于数据挖掘&#…

五、Spring AOP面向切面编程(基于注解方式实现和细节)

本章概要 Spring AOP底层技术组成初步实现获取通知细节信息切点表达式语法重用&#xff08;提取&#xff09;切点表达式环绕通知切面优先级设置CGLib动态代理生效注解实现小结 5.5.1 Spring AOP 底层技术组成 动态代理&#xff08;InvocationHandler&#xff09;&#xff1a;…

改变传媒格局的新趋势

在如今信息高速发展的时代&#xff0c;人们早已进入了一个以手机为中心的智能化时代。随着科技的迅猛发展&#xff0c;手机无人直播成为了一种新兴的传媒形态&#xff0c;正逐渐改变着传媒格局。本文将从手机无人直播的定义、发展背景和影响等方面进行探讨。 首先&#xff0c;…

关于我花费六千多组了台window+Linux主机

一边学习&#xff0c;一边总结&#xff0c;一边分享&#xff01; 写在前面 我在2023年12月组了一台“洋垃圾”的主机&#xff0c;一边当做台式机使用&#xff0c;一边当做服务器使用。这个方案算是相对比较划算的方案。我开始是打算直接单做服务器使用的&#xff0c;以及内存…

ROS学习笔记(7)进一步深入了解ROS第一步

0.前提 最近在学习宾夕法尼亚大学工程学院的ROS公开课&#xff0c;在尽力的去融入全英语的环境&#xff08;哪怕我的英语水准并不是很高&#xff09;。既然是在学习&#xff0c;笔记也就是必须的了&#xff0c;当然这些笔记都是课程当中提出的问题&#xff0c;我去寻找后得出的…

【STM32】I2C通信

基本的任务是&#xff1a;通过通信线&#xff0c;实现单片机读写外挂模块寄存器的功能。其中至少要实现在指定位置写寄存器和在指定的位置读寄存器这两个功能。 异步时序的优点&#xff1a;省一根时钟线&#xff0c;节约资源&#xff1b;缺点&#xff1a;对事件要求严格&#…

20231228在Firefly的AIO-3399J开发板的Android11的挖掘机的DTS配置单前置摄像头ov13850

20231228在Firefly的AIO-3399J开发板的Android11的挖掘机的DTS配置单前置摄像头ov13850 2023/12/28 10:42 【碰到一个很神奇的问题】&#xff1a; 昨天晚上前置摄像头怎么也点不亮&#xff01;改了巨多的地方&#xff01;晚上睡觉之前把开发板彻底断电了&#xff01;今天开电脑…

深度生成模型之GAN基础 ->(个人学习记录笔记)

文章目录 深度生成模型之GAN基础生成对抗网络1. 生成对抗网络如何生成数据2. 生成对抗原理3. GAN的核心优化目标4. D的优化5. GAN的理想状态6. GAN的训练7. 梯度不稳定与模式崩塌(collapse mode)问题8. 梯度消失问题 深度生成模型之GAN基础 生成对抗网络 1. 生成对抗网络如何…

深入研究矫正单应性矩阵用于立体相机在线自标定

文章&#xff1a;Dive Deeper into Rectifying Homography for Stereo Camera Online Self-Calibration 作者&#xff1a;Hongbo Zhao, Yikang Zhang, Qijun Chen,, and Rui Fan 编辑&#xff1a;点云PCL 欢迎各位加入知识星球&#xff0c;获取PDF论文&#xff0c;欢迎转发朋…

【Java并发】深入浅出 synchronized关键词原理-上

一个问题的思考 建设我们有两个线程&#xff0c;一个进行5000次的相加操作&#xff0c;另一个进行5000次的减操作。那么最终结果是多少 package com.jia.syn;import java.util.concurrent.TimeUnit;/*** author qxlx* date 2024/1/2 10:08 PM*/ public class SynTest {privat…

稳部落 – 新浪微博备份导出工具

稳部落 稳部落是新浪微博备份导出工具&#xff0c;可以帮助用户非常方便的导出备份新浪微博的数据&#xff0c;让我们可以永久保存这些微博数据。它支持新浪微博、微博私信、微博评论的导出&#xff0c;并可以备份包含图片、视频的完整微博内容。用户只需登录微博账号&#xf…

Java学习,一文掌握Java之SpringBoot框架学习文集(2)

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…

【计算机毕业设计】SSM游戏点评网站

项目介绍 本项目分为前后台&#xff0c;前台为普通用户登录&#xff0c;后台为管理员登录&#xff1b; 管理员角色包含以下功能&#xff1a; 管理员登录,管理员管理,网站用户管理,游戏资讯管理,游戏类型管理,城市信息管理,竞技场管理,游戏信息管理,游戏评价信息管理等功能。…

双侧电源系统距离保护MATLAB仿真模型

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 系统原始数据 双侧电源系统模型如图所示&#xff1a; 仿真模型搭建 将线路AB分成Line1和Line2&#xff0c;将线路BC分成Line3和Line4&#xff0c;用三相电压电流测量模块作为系统母线&#xff0c;根据系统已…