【算法学习】-【双指针】-【快乐数】
LeetCode原题链接:202. 快乐数
下面是题目描述:
「快乐数」 定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 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
1、题目分析
根据题目说明,给定的一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程,直到这个数变为 1,也可能是无限循环但始终变不到1;对于始终变不到1的情况,有没有可能不是循环但仍一直在变化呢?
答案是不可能。运用鸽巢原理可以证明这一点。那么下面是简单的证明过程:
先简单地说明一下鸽巢原理,也就抽屉原理,指的是:有n个鸽巢,n+1个鸽子,鸽子全部往巢中飞时,至少有一个鸽巢中鸽子的数量是大于1的
接下来开始证明。由题目所给的数据范围,我们可通过最大的一个数可以计算得到“鸽巢”的大小(范围), 231 - 1 = 2,147,483,647 ,经题目要求的计算方式计算一次可以得到一个数,260。那么任意一个符合题目数据范围的数只会在[1, 260]这个区间内变化,这个区间也就是“鸽巢”。也就是说,只要一个正整数比 231 - 1 小,它的变化只会在[1, 260]中,极端来看,一个数在变化了260次之后(把n个鸽巢填满),下一次变化也绝对会在这个范围中(让某个鸽巢中鸽子的数量大于1),因为那个数不管变成多少都一定比231 - 1 小。由此我们就无需担心一开始的那个问题。
2、解题思路
根据上面分析,给定的正整数要么是无限循环,要么最后变成1;再通过对两个示例中算出来的数进行 “连接”,会发现这个问题可以转换成为链表带环问题。如下图:

所以可以直接按解决链表带环的问题方法解决本题。唯一需要变化的就是快慢指针的定义。链表带环问题中,快指针一次走两步,慢指针一次走一步;在本题中,快指针一次按要求计算两次,慢指针按要求计算一次,最后判断两个指针是否相遇即可。
3、具体代码
class Solution {
public:int calculate(int num){int sum = 0;while(num){sum += pow(num % 10, 2);num /= 10;}return sum;}bool isHappy(int n) {int slow = calculate(n);int fast = calculate(calculate(n));while(slow != 1 && fast != 1){if(slow == fast){return false;}slow = calculate(slow); //slow++;fast = calculate(calculate(fast)); //fast+=2;}return true;}
};
看完觉得有觉得帮助的话不妨点赞收藏鼓励一下,有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论,多多指点,谢谢朋友们!🌹🌹🌹
相关文章:
【算法学习】-【双指针】-【快乐数】
LeetCode原题链接:202. 快乐数 下面是题目描述: 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果…...
【Java-LangChain:使用 ChatGPT API 搭建系统-6】处理输入-链式 Prompt Chaining Prompts
第六章,处理输入-链式 Prompt Chaining Prompts 在本章中,我们将学习如何通过将复杂任务拆分为一系列简单的子任务来链接多个 Prompt。 您可能会想,为什么要将任务拆分为多个 Prompt,而不是像我们在上一个视频中学习的那样&…...
从零手搓一个【消息队列】创建核心类, 数据库设计与实现
文章目录 一、创建核心类1, 交换机2, 交换机类型3, 队列4, 绑定5, 交换机转发 & 绑定规则6, 消息7, 消息属性 二、数据库设计1, 使用 SQLite2, 使用 MyBatis2.1, 创建 Interface2.2, 创建 xml 文件 三、硬盘管理 -- 数据库1, 创建 DataBaseManager 类2, init() 初始化数据库…...
14:00面试,14:06就出来了,这问的过于变态了。。。
前言 刚从小厂出来,没想到在另一家公司我又寄了。 在这家公司上班,每天都要加班,但看在钱给的比较多的份上,也就不太计较了。但万万没想到5月一纸通知,所有人不准加班了,不仅加班费没有了,薪资…...
url请求头信息
Accept Accept:请求报头域,用于指定客户端可接受哪些类型的信息。 Accept-Language Accept-Language:指定客户端可接受的语言类型。 Accept-Encoding Accept-Encoding:指定客户端可接受的内容编码。 Host Host:…...
【Oracle】Oracle系列之十六--数据库备份
文章目录 往期回顾1. 数据库备份的分类1.1 逻辑备份与物理备份(1)逻辑备份(2)物理备份(3)归档模式与非归档模式 1.2 完全备份/差异备份/增量备份 2. Oracle 逻辑备份2.1 EXP/IMP(1)E…...
uni-app:实现页面效果3
效果 代码 <template><view><!-- 风速风向检测器--><view class"content_position"><view class"content"><view class"SN"><view class"SN_title">设备1</view><view class&quo…...
计算机网络基础(一):网络系统概述、OSI七层模型、TCP/IP协议及数据传输
通信,在古代是通过书信与他人互通信息的意思。 今天,“通信”这个词的外沿已经得到了极大扩展,它目前的大意是指双方或多方借助某种媒介实现信息互通的行为。 如果按照当代汉语的方式理解“通信”,那么古代的互遣使节、飞鸽传书…...
互联网金融理财知识点简单总结
互联网金融理财知识点总结 互联网金融理财是指通过互联网平台进行资产管理和投资的一种金融方式。它结合了金融、科技和互联网,为投资者提供了更多选择和便捷性。本文将介绍互联网金融理财的关键知识点,包括理财基础、投资产品、风险管理和未来趋势等方…...
微信小程序template界面模板导入
我们有些时候 会有一些比较大但并不复杂的界面结构 这个时候 你可以试试这种导入模板的形式 我们在根目录创建一个 template 目录 然后下面创建一个 text文件夹下面创建一个 test.wxml 参考代码如下 <template name"textIndex"><text class "testw&…...
C/C++跨平台构建工具CMake-----在C++源码中读取CMakeLists.txt配置文件中的内容
文章目录 1.需求描述2.需求准备2.1 创建项目2.2 编辑CMakeLists.txt文件2.3 编写C文件2.4 编译构建项目 3.需求实现3.1 在CMakeLists.txt中输出日志信息3.2 增加配置生成C头文件3.3在C 源码中访问配置的值3.4 C文件中读取CMakeLists.txt中的字符串 总结 1.需求描述 当我们开发…...
【MVP争夺战】python实现-附ChatGPT解析
1.题目 MVP争夺战 知识点 :DFS搜索 时间限制:1s 空间限制:256MB 限定语言:不限 题目描述: 在星球争霸篮球赛对抗赛中,强大的宇宙战队,希望每个人都能拿到MVP。 MVP的条件是,单场最高分得分获得者,可以并列,所以宇宙战队决定在比赛中尽可能让更多的队员上场,且让所有有得…...
6 个最佳免费 Android 数据恢复软件
如果您是 Android 用户,您可能会发现没有回收站。然而,聪明的开发人员已经创建了各种 Android 数据恢复软件程序,可以解决各种与数据丢失相关的问题。 Android 数据恢复软件如何工作? 问题是当你删除一个文件时,它的数…...
数学建模Matlab之数据预处理方法
本文综合代码来自文章http://t.csdnimg.cn/P5zOD 异常值与缺失值处理 %% 数据修复 % 判断缺失值和异常值并修复,顺便光滑噪音,渡边笔记 clc,clear;close all; x 0:0.06:10; y sin(x)0.2*rand(size(x)); y(22:34) NaN; % 模拟缺失值 y(89:95) 50;% 模…...
如何保证Redis的HA高可用
目录 1.关于Redis2.Redis 的使用场景3.Redis的高可用3.1 哨兵模式(Sentinel)3.2 集群模式(Cluster) 4.参考 本文主要介绍Redis如何保证高可用。 1.关于Redis Redis(Remote Dictionary Server)是一个开源的…...
第一百六十三回 如何在任意位置显示PopupMenu
文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了PopupMenuButton相关的内容,本章回中将介绍如何在任意位置显示PopupMenu.闲话休提,让我们一起Talk Flutter吧。 概念介绍 我们在上一章回中介绍了PopupMenuButton相关的内容,它主…...
采用python中的opencv2的库来运用机器视觉移动物体
一. 此次我们来利用opencv2来进行机器视觉的学习 1. 首先我们先来进行一个小的案例的实现. 这次我们是将会进行一个小的矩形手势的移动. import cv2 from cvzone.HandTrackingModule import HandDetectorcap cv2.VideoCapture(0) # cap.set(3, 1280) # cap.set(4, 720) col…...
一、thymeleaf简介
1.1 什么是thymeleaf Thymeleaf是一个适用于web和独立环境的现代服务器端Java模板引擎,能够处理HTML、XML、JavaScript、CSS甚至纯文本。主要目标是提供一种优雅且高度可维护的创建模板的方法。 何为模板引擎呢?模板引擎就是为了使用户页面和业务数据…...
二分查找模版
对于一个递增序列我们要找大于等于target的数,返回结果的下标时 比如 序列 5 7 7 8 8 10 初始化左右指针l0 rn-1 猜测区间 [l,r] 闭区间,mid(lr)/2 防溢出就写成 midl(r-l)/2 如果有nums[mid]<target 那么[l,mid]这个区间的数就都小于target 更新 lmi…...
idea清空缓存类
解决办法 网上有很多是让你去清空什么maven依赖,但假如这个项目是你不可以大刀阔斧的话 可以清空idea缓存 选择 Invalidate 开头的 然后全选 运行重启idea OK...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
