leetcode-202:快乐数

简介: leetcode-202:快乐数

题目

题目链接

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

「快乐数」定义为:

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

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

示例 1:

输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2:

输入:n = 2
输出:false

解题

方法一:快慢指针

使用 “快慢指针” 思想,找出循环:“快指针” 每次走两步,“慢指针” 每次走一步,当二者相等时,即为一个循环周期。此时,判断是不是因为 1 引起的循环,是的话就是快乐数,否则不是快乐数。

注意:此题不建议用集合记录每次的计算结果来判断是否进入循环,因为这个集合可能大到无法存储;另外,也不建议使用递归,同理,如果递归层次较深,会直接导致调用栈崩溃。不要因为这个题目给出的整数是 int 型而投机取巧。

为啥一定不会出现死循环,因为int类型最大值为为‭‭2 147 483 647‬‬, 所以平方和最大的数是1 999 999 999,平方和为1 + 81*9 = 724。任何数的平方和都在1到724之间,724次循环之内一定有重复的

c++解法

class Solution {
public:
    int bitSquareSum(int n) {
        int sum = 0;
        while(n > 0)
        {
            int bit = n % 10;
            sum += bit * bit;
            n = n / 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n, fast = n;
        do{
            slow = bitSquareSum(slow);
            fast = bitSquareSum(fast);
            fast = bitSquareSum(fast);
        }while(slow != fast);
        return slow == 1;
    }
};

方法二:哈希表

class Solution {
public:
    int bitSquareSum(int n){
        int sum=0;
        while(n>0){
            int bit=n%10;
            sum+=bit*bit;
            n=n/10;
        }
        return sum;
    }   
    bool isHappy(int n) {
        unordered_set<int> set;
        while(true){
            int sum=bitSquareSum(n);
            if(sum==1){
                return true;
            }
            //如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return false
            if(set.find(sum)!=set.end()){  
                return false;
            }
            else{
                set.insert(sum);
            }
            n=sum;
        }
    }
};

java

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set=new HashSet<>();
        while(n!=1){
            if(set.contains(n)) return false;
            set.add(n);
            String s=String.valueOf(n);
            int tmp=0;
            for(int i=0;i<s.length();i++){
                int num=s.charAt(i)-'0';
                tmp+=num*num;
            }
            n=tmp;
        }
        return true;
    }
}

或者

class Solution {
    int bitSquareSum(int n){
        int res=0;
        while(n>0){
            int num=n%10;
            res+=num*num;
            n/=10;
        }
        return res;
    }
    public boolean isHappy(int n) {
        Set<Integer> set=new HashSet<>();
        while(n!=1){
            if(set.contains(n)) return false;
            set.add(n);
            n=bitSquareSum(n);
        }
        return true;
    }
}


相关文章
|
芯片
STM32F103标准外设库——中断应用/事件控制器(七)
STM32F103标准外设库——中断应用/事件控制器(七)
1029 0
STM32F103标准外设库——中断应用/事件控制器(七)
|
9月前
|
机器学习/深度学习 测试技术
专家模型不要专家并行!微软开源MoE新路径
微软研究团队提出了一种名为“GRIN(GRadient-INformed MoE training)”的新型训练方法,针对专家混合(MoE)模型优化难题。MoE通过稀疏计算提高效率,但传统梯度优化难以直接应用。GRIN利用梯度信息指导专家路由,引入稀疏梯度估计和并行配置,克服了这一局限,显著提升了MoE模型的训练效率和性能。实验表明,GRIN在语言建模等任务上超越了密集模型,并在多个基准测试中取得领先。尽管存在计算复杂度高等挑战,GRIN为MoE模型训练提供了新思路。论文地址:https://arxiv.org/abs/2409.12136
196 24
|
7月前
|
人工智能 分布式计算 调度
打破资源边界、告别资源浪费:ACK One 多集群Spark和AI作业调度
ACK One多集群Spark作业调度,可以帮助您在不影响集群中正在运行的在线业务的前提下,打破资源边界,根据各集群实际剩余资源来进行调度,最大化您多集群中闲置资源的利用率。
|
存储 安全 数据安全/隐私保护
安全升级!Python AES加密实战,为你的代码加上一层神秘保护罩
【9月更文挑战第12天】在软件开发中,数据安全至关重要。本文将深入探讨如何使用Python中的AES加密技术保护代码免受非法访问和篡改。AES(高级加密标准)因其高效性和灵活性,已成为全球最广泛使用的对称加密算法之一。通过实战演练,我们将展示如何利用pycryptodome库实现AES加密,包括生成密钥、初始化向量(IV)、加密和解密文本数据等步骤。此外,还将介绍密钥管理和IV随机性等安全注意事项。通过本文的学习,你将掌握使用AES加密保护敏感数据的方法,为代码增添坚实的安全屏障。
458 8
|
SQL Prometheus 运维
Higress on K8s 5分钟开箱即用
Higress on K8s 5分钟开箱即用
Higress on K8s 5分钟开箱即用
|
安全 Oracle 关系型数据库
智能合约中时间依赖漏洞
智能合约中时间依赖漏洞
313 6
|
编解码 前端开发 图形学
Unity 用脚本操作常用UI控件(上)
Unity 用脚本操作常用UI控件(上)
296 0
|
存储 运维 监控
从零入门 Serverless | 一文搞懂函数计算及其工作原理
在 Serverless 架构下,开发者只需要关注应用的开发构建和部署,无需关心服务器相关操作与运维。在函数计算架构下,开发者只需要编写业务代码并监控业务运行情况。这将开发者从繁重的运维工作中解放出来,把精力投入到更有意义的业务开发上。
从零入门 Serverless | 一文搞懂函数计算及其工作原理
|
PHP
使用xdebug调试基于swoole的项目,例如easyswoole
使用xdebug调试基于swoole的项目,例如easyswoole
470 0
|
人工智能 Cloud Native 安全
OpenCloudOS 9.0发布,腾讯闯入底层基础软件“深水区”
OpenCloudOS 9.0发布,腾讯闯入底层基础软件“深水区”
567 0