当前位置: 首页 > news >正文

【算法学习】-【双指针】-【快乐数】

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原题链接&#xff1a;202. 快乐数 下面是题目描述&#xff1a; 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1&#xff0c;也可能是 无限循环 但始终变不到 1。 如果…...

【Java-LangChain:使用 ChatGPT API 搭建系统-6】处理输入-链式 Prompt Chaining Prompts

第六章&#xff0c;处理输入-链式 Prompt Chaining Prompts 在本章中&#xff0c;我们将学习如何通过将复杂任务拆分为一系列简单的子任务来链接多个 Prompt。 您可能会想&#xff0c;为什么要将任务拆分为多个 Prompt&#xff0c;而不是像我们在上一个视频中学习的那样&…...

从零手搓一个【消息队列】创建核心类, 数据库设计与实现

文章目录 一、创建核心类1, 交换机2, 交换机类型3, 队列4, 绑定5, 交换机转发 & 绑定规则6, 消息7, 消息属性 二、数据库设计1, 使用 SQLite2, 使用 MyBatis2.1, 创建 Interface2.2, 创建 xml 文件 三、硬盘管理 -- 数据库1, 创建 DataBaseManager 类2, init() 初始化数据库…...

14:00面试,14:06就出来了,这问的过于变态了。。。

前言 刚从小厂出来&#xff0c;没想到在另一家公司我又寄了。 在这家公司上班&#xff0c;每天都要加班&#xff0c;但看在钱给的比较多的份上&#xff0c;也就不太计较了。但万万没想到5月一纸通知&#xff0c;所有人不准加班了&#xff0c;不仅加班费没有了&#xff0c;薪资…...

url请求头信息

Accept Accept&#xff1a;请求报头域&#xff0c;用于指定客户端可接受哪些类型的信息。 Accept-Language Accept-Language&#xff1a;指定客户端可接受的语言类型。 Accept-Encoding Accept-Encoding&#xff1a;指定客户端可接受的内容编码。 Host Host&#xff1a;…...

【Oracle】Oracle系列之十六--数据库备份

文章目录 往期回顾1. 数据库备份的分类1.1 逻辑备份与物理备份&#xff08;1&#xff09;逻辑备份&#xff08;2&#xff09;物理备份&#xff08;3&#xff09;归档模式与非归档模式 1.2 完全备份/差异备份/增量备份 2. Oracle 逻辑备份2.1 EXP/IMP&#xff08;1&#xff09;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协议及数据传输

通信&#xff0c;在古代是通过书信与他人互通信息的意思。 今天&#xff0c;“通信”这个词的外沿已经得到了极大扩展&#xff0c;它目前的大意是指双方或多方借助某种媒介实现信息互通的行为。 如果按照当代汉语的方式理解“通信”&#xff0c;那么古代的互遣使节、飞鸽传书…...

互联网金融理财知识点简单总结

互联网金融理财知识点总结 互联网金融理财是指通过互联网平台进行资产管理和投资的一种金融方式。它结合了金融、科技和互联网&#xff0c;为投资者提供了更多选择和便捷性。本文将介绍互联网金融理财的关键知识点&#xff0c;包括理财基础、投资产品、风险管理和未来趋势等方…...

微信小程序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 用户&#xff0c;您可能会发现没有回收站。然而&#xff0c;聪明的开发人员已经创建了各种 Android 数据恢复软件程序&#xff0c;可以解决各种与数据丢失相关的问题。 Android 数据恢复软件如何工作&#xff1f; 问题是当你删除一个文件时&#xff0c;它的数…...

数学建模Matlab之数据预处理方法

本文综合代码来自文章http://t.csdnimg.cn/P5zOD 异常值与缺失值处理 %% 数据修复 % 判断缺失值和异常值并修复&#xff0c;顺便光滑噪音&#xff0c;渡边笔记 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 哨兵模式&#xff08;Sentinel&#xff09;3.2 集群模式&#xff08;Cluster&#xff09; 4.参考 本文主要介绍Redis如何保证高可用。 1.关于Redis Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的…...

第一百六十三回 如何在任意位置显示PopupMenu

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了PopupMenuButton相关的内容&#xff0c;本章回中将介绍如何在任意位置显示PopupMenu.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在上一章回中介绍了PopupMenuButton相关的内容&#xff0c;它主…...

采用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模板引擎&#xff0c;能够处理HTML、XML、JavaScript、CSS甚至纯文本。主要目标是提供一种优雅且高度可维护的创建模板的方法。 何为模板引擎呢&#xff1f;模板引擎就是为了使用户页面和业务数据…...

二分查找模版

对于一个递增序列我们要找大于等于target的数&#xff0c;返回结果的下标时 比如 序列 5 7 7 8 8 10 初始化左右指针l0 rn-1 猜测区间 [l,r] 闭区间&#xff0c;mid(lr)/2 防溢出就写成 midl(r-l)/2 如果有nums[mid]<target 那么[l,mid]这个区间的数就都小于target 更新 lmi…...

idea清空缓存类

解决办法 网上有很多是让你去清空什么maven依赖&#xff0c;但假如这个项目是你不可以大刀阔斧的话 可以清空idea缓存 选择 Invalidate 开头的 然后全选 运行重启idea OK...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...