【LeetCode】202. 快乐数(简单)——代码随想录算法训练营Day06

题目链接:202. 快乐数

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19

输出:true

解释:

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1

示例 2:

输入:n = 2

输出:false

提示:

  • 1 <= n <= 231 - 1

文章讲解:代码随想录

题解1:

思路:这里将题目描述中的一次替换操作称为1次 happy 操作。如果一个数是快乐数,则在有限次 happy 操作后它会变为1;如果不是快乐数,则进行无限次 happy 操作也不会变为1。

有一个重要结论:非快乐数在无限次 happy 操作中,会出现曾经出现过的 happy 操作的结果,即在求和的过程中,sum 会重复出现

证明可以先证这个问题是个有限状态,因为任何正整数 n 的每个位上的数字的平方和都小于或等于(9^2 × 位数),因此对于任何给定的 n,其平方和有一个上限。随着平方和的重复计算,新得到的数要么减小,要么在有限范围内波动,如下图。

再证收敛性:如果在某个点达到1,之后就永远是1,如果没有达到1,由于是有限状态,根据狄利克雷原则,无限次迭代必导致状态重复;所以算法最终会收敛到一个有限序列。

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    const hashSet = new Set();

    // 返回对 n 进行一次 happy 操作的结果
    const happy = function (n) {
        let res = 0;
        while (n > 0) {
            const d = n % 10;
            res += d * d;
            n = Math.floor(n / 10);
        }
        return res;
    };

    // 持续对 n 进行 happy 操作,如果出现1,则为快乐数,若出现了曾出现过的数,则不是快乐数。
    while (!hashSet.has(n)) {
        if (n === 1) {
            return true;
        }
        hashSet.add(n);
        n = happy(n);
    }
    return false;
};

分析:时间复杂度为 O(logn),空间复杂度为 O(logn)。

收获

(1) 继续体验哈希表的使用场景,判断一个数在不在集合中,就可以使用哈希表。

(2) 与数字有关的场景,数字范围大哈希表的数据结构使用 Set,数字范围小哈希表的数据结构使用 Array。

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

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

相关文章

Multimodal Contrastive Training for Visual Representation Learning

parameterize the image encoder as f i q _{iq} iq​ query feature q i i _{ii} ii​&#xff0c;key feature k i i _{ii} ii​ parameterize the textual encoder as f c q ( ⋅ ; Θ q , Φ c q ) f_{cq}(; Θ_q, Φ_{cq}) fcq​(⋅;Θq​,Φcq​)&#xff0c;momentum …

西贝柳斯音乐记谱软件Avid Sibelius Ultimate 2023中文激活版

Avid Sibelius(西贝柳斯终极解锁版) 是一款记谱软件&#xff0c;从有抱负的作曲家和词曲作者到教师和学生&#xff0c;任何人都可以快速轻松地开始创作和分享音乐。对于那些还不熟悉使用符号软件的人来说&#xff0c;直观的界面将引导您完成整个过程。磁性布局可防止对象相互碰…

API可视化编排如何实现

企业随着前后端分离架构、微服务架构、中台战略、产业互联互通的实施必将产生大量的各种协议的API服务&#xff0c;API将成为企业的数字化资产且API会越来越多&#xff0c; API服务之间的相互调用和依赖情况也随之越来越多和复杂。业务系统与业务系统之间、关联企业之间的API都…

【mars3d】 graphic.bindPopup(inthtml).openPopup()无需单击小车,即可在地图上自动激活弹窗的效果。

实现效果&#xff1a;new mars3d.graphic.FixedRoute({无需单击小车&#xff0c;即可在地图上实现默认打开弹窗的激活效果。↓↓↓↓↓↓↓↓ 相关链接说明&#xff1a; 1.popup的示例完全开源&#xff0c;可参考&#xff1a;功能示例(Vue版) | Mars3D三维可视化平台 | 火星科…

谷粒商城篇章8 ---- P236-P247 ---- 购物车【分布式高级篇五】

目录 1 环境搭建 1.1 新建购物车服务模块gulimall-cart 1.2 购物车服务相关配置 1.2.1 pom.xml 1.2.2 yml配置 1.2.2.1 application.yml配置 1.2.2.2 bootstrap.yml配置 1.2.3 主类 1.3 SwitchHosts增加配置 1.4 网关配置 1.5 整合SpringSession 1.5.1 session数据…

如何使用LightPicture+cpolar搭建个人云图床随时随地公网访问

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…

selenium 做 Web 自动化,鼠标当然也要自动化!

我们在做 Web 自动化的时候&#xff0c;有时候页面的元素不需要我们点击&#xff0c;值需要把鼠标移动上去就能展示各种信息。这个时候我们可以通过操作鼠标来实现&#xff0c;接下来我们来讲一下使用 selenium 做 Web 自动化的时候如何来操作鼠标。鼠标操作&#xff0c;我们可…

接口自动化测试难点:数据库验证解决方案

接口自动化中的数据库验证&#xff1a;确保数据的一致性和准确性 接口自动化测试是现代软件开发中不可或缺的一环&#xff0c;而数据库验证则是确保接口返回数据与数据库中的数据一致性的重要步骤。本文将介绍接口自动化中的数据库验证的原理、步骤以及示例代码&#xff0c;帮…

Nodejs基础3之fs模块的文件重命名和移动、文件的删除、文件夹操作、查看资源状态、fs路径

Nodejs基础二 fs模块文件重命名和移动文件的重命名文件的移动同步重命名和移动 文件的删除使用unlink进行删除unlink异步删除unlinkSync同步删除 使用rm进行删除rm异步删除rmSync同步删除 文件夹操作创建文件夹递归创建文件夹 读取文件夹删除文件夹rmdir删除文件夹删除递归文件…

K8s-Pod资源(二)node调度策略、node亲和性、污点与容忍度

目录 node调度策略nodeName和nodeSelector 指定nodeName 指定nodeSelector node亲和性 node节点亲和性 硬亲和性 软亲和性 污点与容忍度 本文主要介绍了在pod中&#xff0c;与node相关的调度策略&#xff0c;亲和性&#xff0c;污点与容忍度等的内容 node调度策略node…

一文速学-selenium高阶性能优化技巧

一文速学-selenium高阶性能优化技巧 前言 最近写的挺多自动化办公的selenium程序没有做优化&#xff0c;执行效率不高&#xff0c;启动浏览器又慢但是又可能出现其他不可控的因素&#xff0c;总结来说虽然放心运行但是又没那么好用&#xff0c;项目是写完了最后还是需要优化结…

内部软件产品数据治理平台(流程设计里,选择触发事件报错)

内部软件产品数据治理平台(流程设计里&#xff0c;选择触发事件报错) 页面报错如下 通过查看dp后台日志发现缺少表字段,表名称(TL_EVENT_SHADOW),需要新增字段即可 PROJECT_ID varchar(200) DEFAULT NULL COMMENT ‘对象所属项目ID’, SPACE_ID varchar(20) DEFAULT ‘0’ C…

黑马程序员JavaWeb开发|案例:tlias智能学习辅助系统(5)登录认证

指路&#xff08;1&#xff09;&#xff08;2&#xff09;&#xff08;3&#xff09;&#xff08;4&#xff09;&#x1f447; 黑马程序员JavaWeb开发|案例&#xff1a;tlias智能学习辅助系统&#xff08;1&#xff09;准备工作、部门管理_tlias智能学习辅助系统的需求分析-CS…

外汇天眼:模拟大赛报名人数突破一万大关

&#x1f525;&#x1f525;&#x1f525; 第二届模拟交易世界杯模拟交易赛区&#xff1a;截止到2024年1月15日上午9:58:06 报名人数已突破10000大关&#xff0c;累计模拟交易人数突破6800&#xff0c;日均模拟交易人数达1100&#xff0c;累计模拟交易金额超650亿&#xff0c;…

YOLOV7剪枝流程

YOLOV7剪枝流程 1、训练 1&#xff09;划分数据集进行训练前的准备&#xff0c;按正常的划分流程即可 2&#xff09;修改train.py文件 第一次处在参数列表里添加剪枝的参数&#xff0c;正常训练时设置为False&#xff0c;剪枝后微调时设置为True parser.add_argument(--pr…

HCIP的静态路由复习

VRP设置用户名密码登录 [R1]aaa [R1-aaa]local-user TMG password cipher huawei #创建一个名TMG的用户&#xff0c;密码huawei Info: Add a new user.[R1-aaa]local-user TMG privilege level 15 #设置权限 [R1-aaa]local-user TMG service-type terminal …

CentOS离线安装MongoDB

目录 1、下载 2、上传并解压 3、创建目录 4、新建配置文件 5、启动 6、验证 7、停止服务 7.1 快速停止 7.2 标准的关闭方法 1、下载 下载MongoDB对应的压缩包&#xff0c;本次使用的是4.0.10版本&#xff0c;点击下载 2、上传并解压 把压缩包上传到服务器&#xff0c…

人大金仓参与起草《数据库运维管理能力成熟度模型》标准

近日&#xff0c;由中国信息通信研究院、中国移动通信集团有限公司、人大金仓等单位参与起草的《数据库运维管理能力成熟度模型》标准正式发布。本标准适用于金融、电信、互联网、能源等重点行业对内部数据库运维管理能力进行全面综合的评价。 数据库作为基础软件的核心组成部分…

2024年初会报名照片要求(必须白底哦)

24初级会计报名照片要求 近期彩色标准1寸、(白色背景)&#xff0c; jpg格式&#xff0c;大于10KB ,像素>295*413. 初级会计考试报名照片要求为本人近期正面、免冠、清晰完整的证件电子照。 初级会计报名照片应显示报考人员双肩、双耳、双眉&#xff0c;不得佩戴首饰&#xf…