【力扣】快乐数,哈希集合+快慢指针+数学

快乐数原题地址

方法一:哈希集合

定义函数getNext(n),返回n的所有位的平方和。一直执行n=getNext(n),最终只有2种可能:

  1. n停留在1。
  2. 无限循环且不为1。

证明:情况1是存在的,如力扣的示例一:

接下来只需证明,反复执行getNext操作,最终一定会无限循环(停留在1可以理解为无限的1->1循环)。

分类讨论:

  1. n的位数小于等于3,那么getNext(n)<=getNext(999)=243,那么反复执行getNext(n),执行244次以上,根据抽屉原理,一定会出现循环。
  2. n的位数大于3,如n为4位数,执行getNext(n)后,n的位数会减小,直到变为情况1。

所以,我们可以使用如下算法:反复执行n=getNext(n),会出现下面3种情况:

  1. n=1,说明原来的n是快乐数。
  2. n不在哈希表中,则把n插入哈希表。
  3. n在哈希表中,且n≠1,说明n已经进入循环,原来的n不是快乐数。
// 方法一:哈希集合
class Solution {
    // 计算n的所有位的平方和
    int getNext(int n)
    {
        int sum = 0;
        while (n)
        {
            int digit = n % 10;
            n /= 10;
            sum += (digit * digit);
        }

        return sum;
    }
public:
    bool isHappy(int n) {
        unordered_set<int> hashtable;
        while (n != 1)
        {
            // 若哈希表中没有n,就添加n,否则不是快乐数
            if (!hashtable.count(n))
            {
                hashtable.insert(n);
            }
            else
            {
                return false;
            }

            n = getNext(n);
        }

        return true;
    }
};

方法二:快慢指针(龟兔赛跑、弗洛伊德循环查找算法)

考虑到反复执行n=getNext(n),一定会进入循环,参考判断链表是否带环的思路,定义fast和slow,slow每次执行slow=getNext(slow)一次,fast每次执行fast=getNext(fast)两次,那么slow和fast最终一定会在循环内相遇。若相遇时slow=fast=1,则n为快乐数,否则不是快乐数。

这是因为若链表带环,最终fast和slow一定会入环,且每次fast比slow多走一步,fast和slow的距离缩短一步,最终距离一定会减为0,两者相遇。

// 方法二:快慢指针法
class Solution {
    // 计算n的所有位的平方和
    int getNext(int n)
    {
        int sum = 0;
        while (n)
        {
            int digit = n % 10;
            n /= 10;
            sum += (digit * digit);
        }

        return sum;
    }
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = getNext(slow);

        while (slow != fast)
        {
            // 慢指针一次走一步
            slow = getNext(slow);
            // 快指针一次走两步
            fast = getNext(getNext(fast));
        }

        return slow == 1;
    }
};

方法三:数学

根据方法一所述,反复执行n=getNext(n),n一定会跌为三位数以下,且进入循环。使用硬编码穷举,最终的循环一定是...,4,16,37,58,89,145,42,20,4,...或者...1...

所以只需要提前把循环中的数存储在哈希表中,反复执行n=getNext(n),会出现3种情况:

  1. n在哈希表中,说明已经进入循环,原来的n不是快乐数。
  2. n=1,说明原来的n是快乐数。
  3. n不在哈希表中。
// 方法三:数学
class Solution {
    // 计算n的所有位的平方和
    int getNext(int n)
    {
        int sum = 0;
        while (n)
        {
            int digit = n % 10;
            n /= 10;
            sum += (digit * digit);
        }

        return sum;
    }
public:
    bool isHappy(int n) {
        while (1)
        {
            // 最终要么为1,要么进入循环
            if (n == 1)
            {
                return true;
            }
            else if (cycleMembers.count(n))
            {
                return false;
            }

            n = getNext(n);
        }
    }
private:
    static unordered_set<int> cycleMembers;
};

unordered_set<int> Solution::cycleMembers = { 4,16,37,58,89,145,42,20 };

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

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

相关文章

怎么加密电脑磁盘?磁盘加密软件哪个好?

磁盘是电脑储存数据的基础工具&#xff0c;可以存放大量数据。为了避免数据泄露&#xff0c;可以使用专业的磁盘加密软件加密保护电脑磁盘。那么&#xff0c;磁盘加密软件哪个好呢&#xff1f;下面我们就来了解一下。 磁盘加锁专家 磁盘加锁专家是一款专业的磁盘加锁软件&…

阅读《极客时间 | Kafka核心技术与实战》(一)【Kafka入门】

阅读《极客时间 | Kafka核心技术与实战》 为什么要学习Kafka消息引擎系统ABC一篇文章带你快速搞定Kafka术语我应该选择哪种Kafka&#xff1f;聊聊Kafka的版本号 为什么要学习Kafka 如果你是一名软件开发工程师的话&#xff0c;掌握 Kafka 的第一步就是要根据你掌握的编程语言去…

使用CMSIS-DSP库进行嵌入式音频信号处理

在嵌入式环境下&#xff0c;使用CMSIS-DSP库进行音频信号处理是一种常见的应用场景。通过CMSIS-DSP库&#xff0c;开发人员可以利用嵌入式系统的处理能力来实现各种数字信号处理&#xff08;DSP&#xff09;功能&#xff0c;例如音频滤波、均衡器、噪音消除等。本文将介绍如何在…

C# 中的 out 参数传递

C# 是一种强大的编程语言&#xff0c;它提供了许多功能和特性来帮助开发人员编写高效和可维护的代码。其中&#xff0c;out 参数是 C# 中非常有用的一个特性之一。在本文中&#xff0c;我们将深入探讨 C# 中的 out 参数传递&#xff0c;并介绍它的用法、优势以及一些最佳实践。…

Dataway工具(一个接口竟然可以如此简单的配置出来无需开发任何一行代码,也不需要做任何 Mapping 实体映射绑定。)

基于 DataQL 服务聚合能力&#xff0c;为应用提供的一个接口配置工具&#xff0c;使得使用者无需开发任何代码就配置一个满足需求的接口。整个接口配置、测试、冒烟、发布&#xff0c;一站式都通过 Dataway 提供的 UI 界面完成。UI 会以 Jar 包方式提供并集成到应用中并和应用共…

Qt环境搭建+简单程序实现

Qt是什么 Qt是一个跨平台的C图形用户界面应用程序框架。 框架的本质就是一群大佬发明的让菜鸡写出来的代码也也比较规范 也就是限制程序员的自由&#xff0c;让程序员写出来的代码规范。 库和框架有相似性。 库是被程序员调用的&#xff0c;&#xff08;程序员是主体&…

【自动化测试】---Selenium+Java

1.自动化测试分类 接口自动化测试UI自动化测试&#xff08;移动端自动化测试、Web端自动化测试&#xff09; 2.选择Selenium作为web自动化工具原因&#xff08;面试题&#xff09; 开源免费支持多个浏览器支持多个系统支持多语言Selenium包提供很多供测试使用的API 3.自动化是什…

深入探索 Stable Diffusion:AI图像创新的新纪元

深入探索 Stable Diffusion&#xff1a;AI图像创新的新纪元 介绍 Stable Diffusion 的核心功能和应用场景Stable Diffusion 架构解析深入 Stable Diffusion 的关键组件变分自编码器&#xff08;VAE&#xff09;生成对抗网络&#xff08;GAN&#xff09;注意力机制优化算法数据集…

#Z0463. 巡逻1

Description 在一个地区中有 n 个村庄&#xff0c;编号为 1, 2, ..., n。有 n – 1 条道路连接着这些村 庄&#xff0c;每条道路刚好连接两个村庄&#xff0c;从任何一个村庄&#xff0c;都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单位。 为保证该地区的…

超实用的GPT使用三个明星技巧!

在我们对ChatGPT的基础能力有了一定的了解之后&#xff0c;我们就要开始在ChatGPT的基础上探索更多的可能性。 而ChatGPT本身的问题也很多&#xff0c;ChatGPT在使用上最大也最明显的革命&#xff0c;其实是对自然语言的处理能力&#xff0c;抛开太多专业性的术语&#xff0c;你…

漏电流的检测要求和理解

漏电流的检测要求和理解 简介漏电流的产生和效应标准要求漏电流的试验漏电流与电磁兼容的关系小结 简介 漏电流是指非功能性电流&#xff0c;是非期望的会引起安全方面危险的电流。漏电流表明了设备中电气绝缘起到防电击作用具有的性能&#xff0c;以使穿过电气绝缘的电流控制…

linux中dup/dup2/fcntl函数的简单使用

dup函数&#xff1a; 作用&#xff1a;复制文件描述符 原型&#xff1a;int dup(int oldfd); oldfd是要复制的文件描述符 函数返回值&#xff1a; 成功返回最小且未被占用的文件描述符 失败返回-1 newfd dup(int oldfd); 注意&#xff1a;在调用dup函数时&#xff0c…

零基础学编程从哪里入手,编程实例分享,配件进出库管理系统软件

零基础学编程从哪里入手&#xff0c;编程实例分享&#xff0c;配件进出库管理系统软件 一、前言 对于刚学编程的人来说&#xff0c;多看看现有的软件实例对自己学开发软件是很有帮助的。 下面分享的实例以配件进出库管理系统软件为例说明。 软件文件下载可以点击最下方官网…

Qwen-VL 技术报告总结

感谢如此优秀的开源工作,仓库链接 Qwen-VL 权重分为 Qwen-VL && Qwen-VL-Chat&#xff0c;区别文档稍后介绍 训练过程 在第一阶段中主要使用224X224分辨率训练&#xff0c;训练数据主要来源是公开数据集&#xff0c;经过清洗&#xff0c;数据总量大约是1.4B,中文数据…

canvas实现涂鸦画板功能

查看专栏目录 canvas实例应用100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…

高考志愿填报模拟系统的功能和技术总结

一、金秋志愿高考志愿填报系统主要功能&#xff1a; 用户注册与登录&#xff1a;允许学生和家长注册账号&#xff0c;使用注册的账号登录系统。 个人信息管理&#xff1a;允许用户查看、修改个人信息&#xff0c;如姓名、性别、联系方式等。 高考成绩输入&#xff1a;学生输…

《MySQL 简易速速上手小册》第1章:MySQL 基础和安装(2024 最新版)

文章目录 1.1 MySQL 概览&#xff1a;版本、特性和生态系统1.1.1 基础知识1.1.2 重点案例1.1.3 拓展案例 1.2 安装和配置 MySQL1.2.1 基础知识1.2.2 安装步骤1.2.3 重点案例1.2.4 拓展案例 1.3 基础命令和操作1.3.1 基础知识1.3.2 重点案例1.3.3 拓展案例 1.1 MySQL 概览&#…

STM32的分类和选型

F系列&#xff08;主要用于普通应用&#xff09; STM32F0xx&#xff1a;低成本、低功耗&#xff0c;适用于成本敏感和低功耗的应用。STM32F1xx&#xff1a;中低端微控制器&#xff0c;具有丰富的外设和良好的性能。STM32F2xx&#xff1a;高性能微控制器&#xff0c;适用于要求…

【C语言】位与移位操作符详解

目录 1.⼆进制和进制转换 ①十进制&#xff1a;生活中最常用 ②二进制&#xff1a;计算机中使用的&#xff0c;每个数字称为一个比特 ③八进制、十六进制也如上 ④二进制转十进制 ⑤十进制转二进制 ⑥二进制转八进制 ⑦二进制转十六进制 2.原码、反码、补码 3.移位操…

32USART串口

目录 一.通信接口 二.时序 三.USART简介 ​编辑四.数据帧 五.起始位侦测和采样位置对齐 &波特率计算 六.相关函数 七.编码格式设置 &#xff08;1&#xff09; UTF-8编码&#xff08;有的软件兼容性不好&#xff09;​编辑 &#xff08;2&#xff09;GB2312编码 八.…