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

LeetCode 202 - 快乐数

题目描述

编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,或者进入一个无限循环但始终变不到 1。如果这个过程的结果为 1,那么这个数就是快乐数。如果 n 是快乐数就返回 true;否则返回 false。

解题思路

这个问题可以通过快慢指针的思想来解决。我们可以定义一个计算平方和的函数 get_next(n),然后使用两个指针,一个快指针和一个慢指针,快指针每次走两步,慢指针每次走一步。如果 n 是快乐数,那么快慢指针最终会相遇在 1 上。如果不是快乐数,快指针会在某个循环中套圈,最终会等于慢指针。

算法实现

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;
    }
};
复杂度分析
  • 时间复杂度:O(log n),在最坏情况下,快乐数的计算过程不会无限循环,因此时间复杂度为O(log n)。
  • 空间复杂度:O(1),只需要常数级别的额外空间。
总结

通过使用快慢指针的方法,我们可以高效地判断给定的数是否为快乐数。这种方法可以避免额外的内存消耗,并且在O(log n)的时间复杂度内解决了问题。


http://www.kler.cn/a/373689.html

相关文章:

  • 计算机毕业设计——ssm-基于SSM框架的校园爱心公益平台的设计与实现-演示录像2021
  • C++ 模板专题 - 静态多态(CRTP)
  • OpenCV视觉分析之目标跟踪(6)轻量级目标跟踪器类TrackerNano的使用
  • 国标GB28181软件EasyGBS国标GB28181网页直播平台在邮政快递场景中的应用
  • 【更新】cyのLastDance - Chapter2(20241030~)
  • Spring MVC介绍
  • python multiprocessing lock锁在相同父进程ID起作用
  • 奥数与C++小学四年级(第十二题 装礼盒)
  • 【unity框架开发14】状态机的封装与实现
  • 正则表达式和通配符
  • 【C/C++】模拟实现strlen
  • 一个简单的Http根据规则自动路由
  • 沈阳乐晟睿浩科技有限公司抖音小店实力电商新星
  • c语言水仙花,超简单讲解
  • Java方法重写
  • C语言的知识框架
  • CSS秘籍-高效样式技巧
  • 【成都新篇】龙信科技电子取证实验室,引领科技取证新时代
  • PIDNet(语义分割)排坑
  • HarmonyOS生命周期
  • 基于局部近似的模型解释方法
  • 【数据结构】ArrayList的模拟实现--Java
  • android12属性设置
  • 使用 NCC 和 PKG 打包 Node.js 项目为可执行文件(Linux ,macOS,Windows)
  • 设计一个灵活的RPC架构
  • AI代币是什么?AI与Web3结合的未来方向在哪里?