C语言每日一题(64)快乐数

题目链接

力扣网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

思路分析

知识点:双指针、快慢指针

解析:

从题目开始分析,第一句话,对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。没什么好说的,很简单;第二句话:然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1,什么意思?

我们看示例1,你看着它的运算过程,发现它最终等于1,是快乐数,

但示例2没有运算过程,直接输出false,就不好分析为什么错误,那我们用上面的方法对他进行一下运算看看。

当我们把过程中出现的每一个数用画图的形式表现出来时,我们发现,2开头,最后从4开始进入循环,很想以前我们做过的判断带环链表,所以可以用快慢指针法来改进一下

环形链表详解

方法步骤

1.定义两个快慢指针,但此指针非比指针,而是每个阶段的值,slow走一步,fast走两步。

当它们相遇时,再判断其中一值是否为1即可。

代码

(建议自己去实现一下再看会比较好)

int bitsum(int n) {//求各位上的数的平方和
    int sum = 0;
    while (n) {
        int j = n % 10;
        sum += j * j;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int fast = n, slow = n;
    do {
        slow = bitsum(slow);
        fast = bitsum(bitsum(fast));
    } while (slow != fast);
    return slow == 1;
}

拓展

在前面我们漏了一个关键点没有考虑,就是这个方法实现的基础是这段数据组成的链表(逻辑上)是有环的,我们怎么肯定这段数据是带环的呢?

这里介绍一个数学原理:鸽巢原理

鸽巢原理,也被称为抽屉原理、鸽笼原理,是一种基本的计数原理,用来描述在一定条件下的排列组合问题。

鸽巢原理的形象解释是:如果有 n 个鸽子被放入 m 个鸽巢中,其中 n > m,那么至少有一个鸽巢中会有多于一个鸽子。

在数学上,鸽巢原理的一般形式是:如果有 n+1 个对象被放入 n 个容器中,那么至少有一个容器中会包含两个或更多的对象。

鸽巢原理的应用范围广泛,包括组合数学、概率论、计算机科学等领域。它可以用于解决各种问题,如证明存在性、推理、计数等。

鸽巢原理的应用举例:
1. 在一周的七天里,如果有八个人生日,那么至少有两个人生日在同一天。
2. 在一台有 30 个存储单元的计算机中,如果有 31 个数据需要存储,那么至少有两个数据会存储在同一存储单元中。

基于鸽巢原理,我们来证明一下这道题的任意数据是必定带环的。

这道题数据的取值范围是2的31次方-1,转换一下等于2147483647,我们取到数字个数的最大值,即9999999999,可以推导出,这个数通过题目的方法取到的数,一定是最大的(因为原数比范围还大,同时也是各位上的最大值),即81*10=810,所以,测试样例的变化范围就在【1,810】之间,不会有大于它的数存在。

设需要检测的数为x,假设最坏情况,它变化了810次都没有重复的数存在,说明它已经将1——810的数已经遍历完一遍,当进行第811次时,必定有重复值出现。

可以将1——810看成鸽巢,x的变化次数为鸽子。

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

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

相关文章

SAP Business Application Studio(BAS) 中Git的使用

1. 概要 本文将介绍如何在SAP BAS中使用Git。 2. BAS中Git功能的集成方式 2.1 简化版Git视图&#xff08;Simplified Git View&#xff09; 通过简化版Git视图&#xff0c;开发人员可以执行最常用的一些Git操作&#xff0c;例如&#xff1a; 初始化或克隆一个仓库reposito…

python中isinstance函数判断各种类型的小细节

1. 基本语法 isinstance(object, classinfo) Return true if the object argument is an instance of the classinfo argument, or of a (direct, indirect or virtual) subclass thereof. Also return true if classinfo is a type object (new-style class) and object is…

【送书福利!第一期】《ARM汇编与逆向工程》

&#x1f42e;博主syst1m 带你 acquire knowledge&#xff01; ✨博客首页——syst1m的博客&#x1f498; &#x1f618;《CTF专栏》超级详细的解析&#xff0c;宝宝级教学让你从蹒跚学步到健步如飞&#x1f648; &#x1f60e;《大数据专栏》大数据从0到秃头&#x1f47d;&…

语音信号数字编码总共有哪些

语音信号的数字编码主要用于将模拟语音信号转换为数字形式&#xff0c;以便可以通过数字网络传输&#xff0c;或者存储在数字存储媒介上。存在多种语音编码标准&#xff0c;各自有不同的编码方式、比特率和应用场景。以下是目前广泛使用的语音编码标准&#xff1a; 1. G.711&…

消息队列面试题

目录 1. 为什么使用消息队列 2. 消息队列的缺点 3. 消息队列如何选型&#xff1f; 4. 如何保证消息队列是高可用的 5. 如何保证消息不被重复消费&#xff08;见第二条&#xff09; 6. 如何保证消息的可靠性传输&#xff1f; 7. 如何保证消息的顺序性&#xff08;即消息幂…

革新监测技术:无线数据记录系统如何颠覆食品、医疗和制药行业的验证流程

在过去的 10-15 年中&#xff0c;无线数据记录系统逐渐取代了热电偶系统&#xff0c;用于食品、医疗和制药行业的验证。过去&#xff0c;使用记录仪的一个主要缺点是在研究过程中缺乏实时数据&#xff0c;但由于 虹科EllabSKY 选项可以提供来自无线设备的实时数据&#xff0c;这…

C语言自定义库

编写 xx.c 和xx.h文件\将源代码编译为目标文件 gcc -c add.c sub.c 执行完毕后会生产add.o和sub.o文件静态库创建使用ar命令&#xff1b; ar -r libmymath.a add.o sub.o将库和main.c文件一起编译 gcc -o main main.c -lmymath -L./ 注意 上述书写格式不要错乱 -L 是指定文件路…

排序算法:快速排序(递归)

文章目录 一、创始人托尼霍尔的快速排序二、挖坑法三、前后指针法 所属专栏:C初阶 引言&#xff1a;这里所说的快速排序有三种&#xff0c;第一种是霍尔大佬自创的&#xff0c;还有一种叫做挖坑法&#xff0c;另外一种叫前后指针法 一、创始人托尼霍尔的快速排序 1.这里我们先…

AI跟踪报道第33期-新加坡内哥谈技术-AI新闻快报:GTC和终结GPU/TPU的热力学未来Chip?

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

【gpt实践】比OpenAI 的 GPT-4 更好模型 Claude 3.0

Google 最近发布了最新的 Gemini 1.5 语言模型&#xff0c;震惊了世界。这是目前功能最强大的模型&#xff0c;拥有 100 万个上下文窗口&#xff0c;是所有大型基础模型中最大的。 OpenAI 的 GPT-4 才具有 128K 上下文窗口。 最近&#xff0c;谷歌最接近的竞争对手之一 Anthro…

【算法】AC自动机的优化:增量更新与删除

一、概述 AC自动机&#xff08;Aho-Corasick Automation&#xff09;是著名的多模匹配算法&#xff0c;源于贝尔实验室&#xff0c;并且在实际应用中得到广泛的引用&#xff0c;且具有以下特点&#xff1a; 只需要扫描一次文本&#xff0c;即可获取所有匹配该文本的模式串复杂…

svg代码应用于button

将svg代码的path属性应用于按钮内容&#xff0c;去掉按钮边框&#xff0c;并且自适应svg大小&#xff0c;以下实现的是一个旋转按钮。 svg代码如下(iconfont下载)&#xff1a; <svg t"1710741485848" class"icon" viewBox"0 0 1024 1024" ve…

SpringCloudLoadBalancer入门与实战系列

目录 一、什么是LoadBalancer&#xff1f; 1.1 负载均衡的分类 1.2 负载均衡策略 二、 为什么要学习 Spring Cloud Balancer &#xff1f; 三、 Spring Cloud LoadBalancer 内置的两种负载均衡策略 3.1 轮询负载均衡策略&#xff08;默认的&#xff09; 3.2 随机负载均衡…

高防服务器秒解是什么意思

高防服务器秒解是指高防服务器在遭受大规模的DDoS攻击时&#xff0c;能够迅速解决问题或应对攻击。DDoS攻击是指攻击者通过向目标服务器发送大量的请求&#xff0c;使服务器资源耗尽或无法正常响应其他合法用户的请求&#xff0c;从而导致服务不可用。高防服务器通过具备高性能…

C++容器适配器与stack,queue,priority_queue(优先级队列)的实现以及仿函数(函数对象)与deque的简单介绍

&#x1f389;个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名乐于分享在学习道路上收获的大二在校生 &#x1f648;个人主页&#x1f389;&#xff1a;GOTXX &#x1f43c;个人WeChat&#xff1a;ILXOXVJE &#x1f43c;本文由GOTXX原创&#xff0c;首发CSDN&…

centos云服务器安装cs(cobaltstrike4.0)教程

1、先安装JAVA环境 mkdir download #创建download目录 cd download #进入download目录 mkdir java1.8 #在download目录下再创建java1.8目录 cd java1.8 #进入java1.8目录 wget https://repo.huaweicloud.com/java/jdk/8u201-b09/jdk-8u201-linux-x64.tar.gz #下载jdk压缩包 tar…

积分法卷径计算(CODESYS ST完整源代码)

在学习积分法卷径计算课程之前大家需要属性下PLC的数值积分器运算。 1、博途PLC积分法卷径计算完整源代码 https://rxxw-control.blog.csdn.net/article/details/136719982https://rxxw-control.blog.csdn.net/article/details/1367199822、转动圈数累积功能块 https://rxxw…

代码随想录算法训练营三刷day27 | 回溯之 39. 组合总和 40.组合总和II 131.分割回文串

三刷day27 39. 组合总和回溯三部曲剪枝优化 40.组合总和II回溯三部曲 131.分割回文串回溯三部曲判断回文子串 39. 组合总和 题目链接 解题思路&#xff1a; 本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本…

组件化开发

一、引言 Vue.js 的组件化开发是其核心特性之一&#xff0c;它允许开发者将复杂的界面拆分为可复用的、独立的、小的组件&#xff0c;从而提高开发效率和代码的可维护性。 二、关键点 1.组件的定义 在components下创建.vue文件timecard.vue用来编辑内容。 文件创建完毕后&am…

我的导航学习笔记仓库大改版,欢迎关注!!

链接&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 我的导航学习笔记&#xff0c;内容涵盖导航定位开源程序的源码解读 ( 包括&#xff1a;RTKLIB、GAMP、SoftGNSS、KF-GINS、ORB-SLAM3 等)、各种导航设备的使用方式、书籍讲义、博客翻译、开源项目梳理、…