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

【LeetCode面试150】——202快乐数

博客昵称:沈小农学编程

作者简介:一名在读硕士,定期更新相关算法面试题,欢迎关注小弟!

PS:哈喽!各位CSDN的uu们,我是你的小弟沈小农,希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正,觉得好的话别忘了一键三连哦!😘

题目难度:简单

默认优化目标:最小化时间复杂度。

Python默认为Python3。

1 题目描述

编写一个算法来判断一个数 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

2 题目分析

输入是一个整数n,输出是布尔值。约束条件是,如果是快乐数,返回true;反之,返回false。

根据快乐数的定义,我们猜测有以下三种可能:

  1. 最终到1

  1. 最终会进入循环

  2. 值会越来越大,最后到无穷大

到1的情况如下图所示:

循环的情况如下图所示:

现在我们来分析第三种情况。

我们对不同位数的数取最大值,看看它们的下一个数和它们自身相比的是变大还是变小了。

位数最大下一个数
1981
299162
3999243
49999324
1399999999999991053

对于三位数字,他不可能大于243;而在4位以及4位以上的数字,最终也会跌落到3位数。所以,在最坏情况下,算法会在243以下的数字上循环,要么继续循环,要么到1。所以不会出现第三种情况。

3 代码实现

3.1 哈希表

我们使用哈希表记录已经出现过的快乐数,用于检查某个数是否在循环链当中。

时间复杂度O(log n),空间复杂度O(log n)。当n足够大时,这和n的位数有关,即log n。

C++代码实现

class Solution {
public:bool isHappy(int n) {auto getNext = [](int n) {int sum = 0;while (n > 0) {int digit = n % 10;n /= 10;sum += digit * digit;}return sum;};
​std::unordered_set<int> seen;while (n != 1 && seen.find(n) == seen.end()) {seen.insert(n);n = getNext(n);}
​return n == 1;}
};
 

Python代码实现

class Solution:def isHappy(self, n: int) -> bool:def nexthappy(n):sum=0while n>0:n,d=divmod(n,10)sum+=d**2return sumseen=set()while n!=1 and n not in seen:seen.add(n)n=nexthappy(n)
​return n==1

3.2 快慢指针法

我们使用两个指针,一个叫“兔子”,一个叫“乌龟”。“兔子”一次前进两格,“乌龟”一次一格。如果n是一个快乐数,即没有循环,那么快跑者会比慢跑者先到达数字1;反之,会在同一个数上相遇。

时间复杂度O(log n),空间复杂度O(1)。

C++代码实现

class Solution {
public:bool isHappy(int n) {auto getNext = [](int n) {int sum = 0;while (n > 0) {int digit = n % 10;n /= 10;sum += digit * digit;}return sum;};
​int slow = n;int fast = getNext(n);while (fast != 1 && slow != fast) {slow = getNext(slow);fast = getNext(getNext(fast));}
​return fast == 1;}
};

Python代码实现

class Solution:def isHappy(self, n: int) -> bool:def nexthappy(n):sum=0while n>0:n,d=divmod(n,10)sum+=d**2return sum
​slow=nfast=nexthappy(n)while fast!=1 and slow!=fast:slow=nexthappy(slow)fast=nexthappy(nexthappy(fast))return fast==1

参考文献

力扣面试经典150题

力扣官方题解

相关文章:

【LeetCode面试150】——202快乐数

博客昵称&#xff1a;沈小农学编程 作者简介&#xff1a;一名在读硕士&#xff0c;定期更新相关算法面试题&#xff0c;欢迎关注小弟&#xff01; PS&#xff1a;哈喽&#xff01;各位CSDN的uu们&#xff0c;我是你的小弟沈小农&#xff0c;希望我的文章能帮助到你。欢迎大家在…...

云原生之k8s服务管理

文章目录 服务管理Service服务原理ClusterIP服务 对外发布应用服务类型NodePort服务Ingress安装配置Ingress规则 Dashboard概述 认证和授权ServiceAccount用户概述创建ServiceAccount 权限管理角色与授权 服务管理 Service 服务原理 容器化带来的问题 自动调度&#xff1a;…...

【Vue】 npm install amap-js-api-loader指南

前言 项目中的地图模块突然打不开了 正文 版本太低了&#xff0c;而且Vue项目就应该正经走项目流程啊喂&#xff01; npm i amap/amap-jsapi-loader --save 官方说这样执行完&#xff0c;就这结束啦&#xff01;它结束了&#xff0c;我还没有&#xff0c;不然不可能记录这篇文…...

RocketMQ: 部署结构与存储特点

RocketMQ 是什么 它是一个队列模型的消息中间件&#xff0c;具有高性能、高可靠、高实时、分布式特点 Producer、Consumer、队列都可以分布式Producer 向一些队列轮流发送消息 队列集合称为 TopicConsumer 如果做广播消费则一个 consumer 实例消费这个 Topic 对应的所有队列如果…...

Android OpenGL ES详解——绘制圆角矩形

1、绘制矩形 代码如下&#xff1a; renderer类&#xff1a; package com.example.roundrectimport android.content.Context import android.opengl.GLES30 import android.opengl.GLSurfaceView.Renderer import com.opengllib.data.VertexArray import com.opengllib.prog…...

【大数据学习 | Spark】Spark的改变分区的算子

当分区由多变少时&#xff0c;不需要shuffle&#xff0c;也就是父RDD与子RDD之间是窄依赖。 当分区由少变多时&#xff0c;是需要shuffle的。 但极端情况下&#xff08;1000个分区变成1个分区)&#xff0c;这时如果将shuffle设置为false&#xff0c;父子RDD是窄依赖关系&…...

前端知识点---rest(javascript)

文章目录 前端知识点---rest(javascript)rest的用法基本语法特点使用场景与扩展运算符&#xff08;spread&#xff09;区别小练习 前端知识点—rest(javascript) rest出现于ES2015 function doSum(a,b, ...args) //示例中的args就是一个rest参数 //它会将后续的所有参数存储…...

Spark使用过程中的 15 个常见问题、详细解决方案

目录 问题 1&#xff1a;Spark 作业超时问题描述解决方案Python 实现 问题 2&#xff1a;内存溢出问题描述解决方案Python 实现 问题 3&#xff1a;Shuffle 性能问题问题描述解决方案Python 实现 问题 4&#xff1a;Spark 作业调度不均问题描述解决方案Python 实现 问题 5&…...

ASP.NET MVC宠物商城系统

该系统采用B/S架构&#xff0c;使用C#编程语言进行开发&#xff0c;以ASP.NET MVC框架为基础&#xff0c;以Visual Studio 2019为开发工具&#xff0c;数据库采用SQL Server进行保存数据。系统主要功能包括登录注册、宠物展示、个人中心、我的订单、购物车、用户管理、宠物类别…...

DQN系列算法详解

代码链接见文末 1. Q-learning 1.1 概述 Q-Learning是一种强化学习算法,目的是通过选择能带来最大长期收益的行为来完成任务。 做事包含瞬时奖励和记忆经验奖励: 在Q-Learning中,每个动作都会带来“瞬时奖励”,同时也会根据过去的经验记住哪些行为更有利。瞬时奖励: 这里…...

uniapp发布android上架应用商店权限

先看效果&#xff1a; 实现原理&#xff1a; 一、利用uni.addInterceptor的拦截器&#xff0c;在一些调用系统权限前拦截&#xff0c;进行弹窗展示&#xff0c;监听确定取消实现业务逻辑。 二、弹窗是原生nativeObj进行drawRect绘制的 三、权限申请调用使用的 plus.android.…...

已阻止加载“http://localhost:8086/xxx.js”的模块,它使用了不允许的 MIME 类型 (“text/plain”)。

记录今天解决的一个小bug 在终端启动8080端口号监听后&#xff0c;打开网址http://localhost:8080&#xff0c;发现不能正确加载页面&#xff0c;打开检查-控制台&#xff0c;出现如下警告&#xff1a;已阻止加载“http://localhost:8086/xxx.js”的模块&#xff0c;它使用了不…...

JavaEE之线程初阶(上)

前文我们知道计算机中的每一个程序都对应着一个进程&#xff0c;进程是CPU申请资源的最小单位&#xff0c;那么线程是什么呢&#xff0c;线程中我们又能学习到什么新的知识呢&#xff1f;&#xff1f; 我们来一探究竟 1. 认识线程&#xff08;Thread&#xff09; 线程是什么 …...

Spring Security @PreAuthorize注解

PreAuthorize 注解在 Spring Security 中提供了一种声明式的方法&#xff0c;可以在您的 Spring Boot 应用中添加方法级别的安全检查。本教程将引导您设置并有效使用 PreAuthorize&#xff0c;确保用户只能在具有特定角色或权限的情况下调用 REST API。 什么是 PreAuthorize&a…...

windows已建立威胁IP排查

在应急响应的时候&#xff0c;需要筛选出服务器建立连接的进程、PID&#xff0c;此代码可满足该需求实现共计2步 首先windos netstat-ano > all.txt&#xff0c; 上传至pycharm路径 第一步获取服务器建立连接的ip import re# 从文件读取 netstat 输出 def read_netstat_f…...

AI 大模型如何重塑软件开发流程?——技术革新与未来展望

人工智能的蓬勃发展为许多领域注入了强劲动力&#xff0c;而在软件开发这一关键技术领域&#xff0c;AI 大模型的应用正在彻底改变传统流程。从代码自动生成到智能测试&#xff0c;再到协同开发和流程优化&#xff0c;AI 正逐步成为软件开发者的得力助手&#xff0c;也推动企业…...

Admin.NET框架前端由于keep-alive设置缓存导致的onUnmount未触发问题

bug版本&#xff1a;next分支&#xff0c;基于.NET6版本&#xff1b; 问题描述&#xff1a; 1、添加keep-alive后&#xff0c;在其下运行的组件会出现onActived(被关注时)和onDeactived(取消关注时)生命周期&#xff0c;而组件原有生命周期为onMounted(被创造时)和onUnmounted(…...

Rest-assured

依赖 <--rest-assured依赖--><dependency><groupId>io.rest-assured</groupId><artifactId>rest-assured</artifactId><version>4.4.0</version><scope>test</scope> </dependency><--junit5依赖-->…...

ubuntu24挂载硬盘记录

1、显示硬盘及所属分区情况。在终端窗口中输入如下命令&#xff1a; sudo fdisk -l 找到自己硬盘的分区 我的地址/dev/sda 2、显示硬盘及所属分区情况。在终端窗口中输入如下命令&#xff0c;格式化自己硬盘&#xff1a; sudo mkfs -t ext4 /dev/sda 3、在终端窗口中输入如下…...

Dubbo集成SpringBoot实现远程服务调用

SpringBoot集成Dubbo Dubbo介绍了解 Dubbo 核心概念和架构dubbo特性dubbo运行原理图 SpringBoot集成Dubbo技术实战一、Dubbo Spring Boot 版本关系二、引入Maven依赖demo项目基础结构引入依赖创建每个模块1&#xff09;api模块2&#xff09;provider模块3&#xff09;consumer模…...

Redis最终篇分布式锁以及数据一致性

在前三篇我们几乎说完了Redis的所有的基础知识以及Redis怎么实现高可用性,那么在这一篇文章中的话我们主要就是说明如果我们使用Redis出现什么问题以及解决方案是什么,这个如果在未来的工作中也有可能会遇到,希望对看这篇博客的人有帮助,话不多说直接开干 一.Hotkey以及BigKey…...

TCP协议

报文格式 源/目的端口号&#xff1a;数据从哪个进程来&#xff0c;到哪个进程去32位序号&#xff1a;TCP传输过程中&#xff0c;在发送端出的字节流中&#xff0c;传输报文中的数据部分的每一个字节都有它的编号32位确认号&#xff1a;标识了报文接收端期望接收的字节序列4位首…...

Vue3 源码解析(十):watch 的实现原理

本篇文章笔者会讲解 Vue3 中侦听器相关的 api&#xff1a;watchEffect 和 watch 。在 Vue3 之前 watch 是 option 写法中一个很常用的选项&#xff0c;使用它可以非常方便的监听一个数据源的变化&#xff0c;而在 Vue3 中随着 Composition API 的写法推行也将 watch 独立成了一…...

2023年9月GESPC++一级真题解析

一、单选题&#xff08;每题2分&#xff0c;共30分&#xff09; 题号 123456789101112131415 答案 CDBCDBACACBBDDA 1. 我们通常说的 “ 内存 ” 属于计算机中的&#xff08;&#xff09;。 A. 输出设备 B. 输 ⼊ 设备 C. 存储设备 D. 打印设备 【答案】 C 【考纲知识点】…...

vscode 远程连接ssh 密钥方式

目录 1. powershell 生成key&#xff1a; 2. 在服务器上安装公钥 linux测试成功&#xff1a; 3).为了确保连接成功&#xff0c;输入如下指令以保证以下文件权限正确&#xff1a; 3 开启 ssh 密钥登录 vscode 远程连接配置 python连接测试ok 查看日志&#xff1a; 1. po…...

字符函数和字符串函数

字符分类函数 C语言中有⼀系列的函数是专门做字符分类的&#xff0c;也就是⼀个字符是属于什么类型的字符的。 这些函数的使用都需要包含⼀个头文件&#xff1a;ctype.h 这些函数的用法非常类似。 int islower ( int c )islower是能够判断参数部分是否是小写字母的。 通过返…...

如何利用ChatGPT加速开发与学习:以BPMN编辑器为例

在现代开发中&#xff0c;开发者经常会遇到各种需要编写和学习新技术的任务。ChatGPT作为一种强大的自然语言处理工具&#xff0c;不仅可以辅助编写代码&#xff0c;还可以帮助学习新的编程概念和解决开发中的难题。本文将以开发一个BPMN&#xff08;业务流程建模与标注&#x…...

深度学习2

四、tensor常见操作 1、元素值 1.1、获取元素值 tensor.item() 返回tensor的元素&#xff1b;只能在一个元素值使用&#xff0c;多个报错&#xff0c;当存在多个元素值时需要使用索引进行获取到一个元素值时在使用 item。 1.2、元素值运算 tensor对元素值的运算&#xff1a;…...

工业生产安全-安全帽第二篇-用java语言看看opencv实现的目标检测使用过程

一.背景 公司是非煤采矿业&#xff0c;核心业务是采选&#xff0c;大型设备多&#xff0c;安全风险因素多。当下政府重视安全&#xff0c;头部技术企业的安全解决方案先进但价格不低&#xff0c;作为民营企业对安全投入的成本很敏感。利用我本身所学&#xff0c;准备搭建公司的…...

单片机学习笔记 9. 8×8LED点阵屏

更多单片机学习笔记&#xff1a;单片机学习笔记 1. 点亮一个LED灯单片机学习笔记 2. LED灯闪烁单片机学习笔记 3. LED灯流水灯单片机学习笔记 4. 蜂鸣器滴~滴~滴~单片机学习笔记 5. 数码管静态显示单片机学习笔记 6. 数码管动态显示单片机学习笔记 7. 独立键盘单片机学习笔记 8…...

c++ 力扣题(1)JZ64

JZ64求123...n_牛客题霸_牛客网 因此不能使用等差求和&#xff08;禁掉位运算为了禁掉等差求和&#xff0c;右移一位就是等差除二&#xff09;、循环、递归来解决 我们运用到在 统计构造次数所学到的内容&#xff1a; 1.可以利用静态全局变量的思想来做 2.构造n次对象&…...

logback动态获取nacos配置

文章目录 前言一、整体思路二、使用bootstrap.yml三、增加环境变量四、pom文件五、logback-spring.xml更改总结 前言 主要是logback动态获取nacos的配置信息,结尾完整代码 项目springcloudnacosplumelog&#xff0c;使用的时候、特别是部署的时候&#xff0c;需要改环境&#…...

基于零相差前馈补偿的 PID 控制

零相差前馈补偿是一种结合前馈补偿与反馈控制的策略&#xff0c;旨在提高控制系统对参考信号的跟踪精度。通过设计合理的前馈补偿器&#xff0c;使得系统对参考输入实现零相位差的跟踪&#xff0c;同时利用 PID 控制器保证系统的稳定性和动态性能。 1. 原理概述 目标&#xff…...

任务通知的本质(任务通知车辆运行) 软件定时器的本质(增加游戏音效)

任务通知的本质 没有任务通知 所谓"任务通知"&#xff0c;你可以反过来读"通知任务"。 我们使用队列、信号量、事件组等等方法时&#xff0c;并不知道对方是谁。使用任务通知时&#xff0c;可 以明确指定&#xff1a;通知哪个任务。 使用队列、信号量、…...

如何在 MySQL 中进行数据导入和导出?

在 MySQL 中进行数据的导入和导出是一项常见的任务&#xff0c;用于数据备份、恢复、迁移以及数据分析等多种用途。MySQL 提供了多种方法来进行数据的导入和导出&#xff0c;每种方法都有其适用的场景和特点。以下是几种常用的 MySQL 数据导入和导出方法&#xff0c;包括命令行…...

python语言基础-5 进阶语法-5.3 流式编程

声明&#xff1a;本内容非盈利性质&#xff0c;也不支持任何组织或个人将其用作盈利用途。本内容来源于参考书或网站&#xff0c;会尽量附上原文链接&#xff0c;并鼓励大家看原文。侵删。 5.3 流式编程&#xff08;参考链接&#xff1a;https://www.zhihu.com/question/59062…...

centos 服务器 docker 使用代理

宿主机使用代理 在宿主机的全局配置文件中添加代理信息 vim /etc/profile export http_proxyhttp://127.0.0.1:7897 export https_proxyhttp://127.0.0.1:7897 export no_proxy"localhost,127.0.0.1,::1,172.171.0.0" docker 命令使用代理 例如我想在使用使用 do…...

[个人专属博客] - docker安装

&#x1f389;&#x1f389;&#x1f389;&#x1f389;&#x1f389;&#x1f389; 欢迎访问的个人博客&#xff1a;http://swzbk.site/&#xff0c;加好友&#xff0c;一起赚&#x1f9e7;&#x1f9e7;&#x1f9e7; &#x1f389;&#x1f389;&#x1f389;&#x1f389;&…...

推荐一个QDirStat基于 Qt 的目录统计工具

QDirStat 是一款基于 Qt 的目录统计工具&#xff0c;旨在帮助用户分析磁盘空间使用情况并进行清理。QDirStat的一些主要特点和功能&#xff1a; 跨平台兼容性&#xff1a;QDirStat 支持 Linux、BSD、Unix-like 系统以及 macOS&#xff0c;确保了广泛的用户基础。 直观的数据展…...

yolo自动化项目实例解析(九) 导航

比如我们经常使用的导航&#xff0c;说白了就是寻找两点之间最近的路径&#xff0c;也就是所谓的寻路&#xff0c;我们需要想办法让程序知道他要去哪里&#xff0c;路径包含&#xff08;起点、轨迹、终点&#xff09; 一、录制轨迹 从平面角度来看&#xff0c;我们可以把区域视…...

MySQL 报错:1137 - Can‘t reopen table

MySQL 报错&#xff1a;1137 - Can’t reopen table 1. 问题 对临时表查询&#xff1a; select a.ts_code,a.tsnum,b.tsnum from (select t.ts_code ,count(*) tsnum from tmp_table t group by t.ts_code having count(*) > 20 and count(*)< 50 ) a ,(select t.ts_…...

Bokeh实现大规模数据可视化的最佳实践

目录 引言 一、Bokeh简介 二、安装Bokeh 三、数据准备 四、性能优化 五、创建图表 六、添加交互功能 七、应用案例 八、高级技巧 九、总结 引言 在数据科学领域,数据可视化是一个至关重要的环节。通过可视化,我们可以直观地理解数据的特征和趋势,为数据分析和决策…...

HTMLCSS:比赛记分卡

效果演示 这段 HTML 和 CSS 代码创建了一个卡片式的体育比赛信息展示组件&#xff0c;用于显示篮球比赛的两个队伍名称、比赛时间、比分以及一些装饰性的视觉元素。 HTML <div class"card"><div data-status"inprogress" class"teams"…...

什么是 Faiss?

好的&#xff0c;我来详细解释 Faiss&#xff0c;它的用途、使用场景&#xff0c;以及如何安装和使用。 什么是 Faiss&#xff1f; Faiss 是由 Facebook AI Research 开发的一个开源库&#xff0c;专门用于高效的相似性搜索和聚类。它非常擅长在高维向量空间中进行快速搜索&a…...

【prism】遇到一个坑,分享!

背景 我通用prism的方式写了一个弹窗,弹窗绑定一个 Loaded 事件,但是Loaded事件一直不触发!!! 具体过程 我的loaded事件也是通过命令的方式绑定的: <i:Interaction.Triggers><i:EventTrigger EventName="Loaded...

vue制作代码比较工具

前两天朋友问我 有没有vue可以做一个json代码在线比较工具 我也是在网上搜了一下找到的 废话不说 直接上代码 采用 v3 pnpm i v-code-diff <div><CodeDiff:old-string"oldStr":new-string"newStr"output-format"side-by-side"/>…...

GPT系列文章

GPT系列文章 GPT1 GPT1是由OpenAI公司发表在2018年要早于我们之前介绍的所熟知的BERT系列文章。总结&#xff1a;GPT 是一种半监督学习&#xff0c;采用两阶段任务模型&#xff0c;通过使用无监督的 Pre-training 和有监督的 Fine-tuning 来实现强大的自然语言理解。在 Pre-t…...

Qt实现可拖拽的矩形

之前项目上需要用Qt来绘制可拖拽改变形状的矩形。看了Qt Graphics相关的内容&#xff0c;虽然对Qt怎么添加图元的有了些了解&#xff0c;但是具体如何实现拖拽效果&#xff0c;一时也没有什么好的想法。还好网上有人分享的例子&#xff0c;很受启发。后来又回顾了一下这部分的代…...

python爬虫初体验(五)—— 边学边玩小游戏

1. 打开浏览器 利用webbrowser 模块的 open()函数可以启动一个新浏览器&#xff0c;打开指定的 URL。 import webbrowser webbrowser.open(http://inventwithpython.com/) 2. 猜数字游戏 # -*- coding: utf-8 -*- # This is a guess the number game. import randomsecretN…...

学习日志015--python单链表

创建 class Node:def __init__(self,data):# 数据域self.data data# 链接域self.next Noneclass LinkList:def __init__(self,):# 初始化头节点self.head None# 记录链表的长度self.size 0 增加 #头插def insert_head(self,value):# 创建新节点node Node(value)q self…...