【算法专题】双指针算法之202. 快乐数 --- 快慢双指针(力扣)

时间:2024-07-16 10:51:51

欢迎来到CILMY23的博客

????本篇主题为:双指针算法之202. 快乐数 --- 快慢双指针(力扣)

????个人主页:CILMY23-****博客

 ????系列专栏:Python | C++ | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题 | 代码训练营

????感谢观看,支持的可以给个一键三连,点赞关注+收藏。


题目: 

202. 快乐数 - 力扣(LeetCode)

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

「快乐数」 定义为:

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

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

 一、题目解析

 通过题目可以看到要求:

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

首先,我们要求一个正整数的平方和,其次要重复这个过程,最后判断这个过程结果是否为1,如果为1则为快乐数.

二、算法原理

重点是过程的推断,我们得实际看看例题中的两个数, 在分别重复这两个过程后是什么情况。

首先是19的过程:

​​

19不断经过这个过程,最终会在1中无限循环下去

接下来我们看2的过程:

​​ 2不断经过第一个过程,最终会在4这个圈中无限循环下去。因此,为了判断类似环的问题,我们曾经在链表中学过一个思想 ---- 快慢双指针

 快慢双指针:

1.定义两个指针,一个为slow,每次走一步,一个为fast,每次走两步

2.如果在环内,那么这两个指针最终都会相遇

那现在,无论是上述哪种情况,都会形成一个环,这个环内的值不一样而已,一个全是1,一个绕回来不是1,所以判断相遇的值是不是1就可以判断是不是快乐数了。  

三、代码编写

class Solution 
{
public:
    //计算平方和
    int Num_Sum(int n)
    {
        int i = n % 10;
        int sum = 0;
        while(n)
        {
            i = n%10;
            sum += i*i;
            n = n/10;
        }
        return sum; 
    }
    bool isHappy(int n) 
    {
        int slow = n;
        int fast = Num_Sum(n);
        while(slow != fast)
        {
            slow = Num_Sum(slow);
            fast = Num_Sum(Num_Sum(fast)); 
        }
        return slow == 1;
    }
};

四、扩展---链表当中的快慢双指针 

快慢指针是一种解决链表问题的重要技巧。在单链表中设置两个指针,一个快速移动(快指针),一个慢速移动(慢指针),可以有效地解决诸如寻找链表中环的起始节点、寻找链表中倒数第k个节点等常见问题。
一、快慢指针的基本原理
快慢指针的基本原理是利用双指针在链表中同时移动,快指针每次移动两步,慢指针每次移动一步。这样,当快指针到达链表尾部时,慢指针刚好指向链表中的一个节点。此时,我们可以利用慢指针回溯,找到环的起始节点或者倒数第k个节点。

二、应用场景

  1. 寻找链表中环的起始节点
    当链表中存在环时,我们可以使用快慢指针来找到环的起始节点。首先,让快慢指针同时从链表头部开始移动。当它们相遇时,将快指针重新置为头部,然后继续移动。当快指针再次追上慢指针时,它所指的节点就是环的起始节点。
  2. 寻找链表中倒数第k个节点
    我们可以使用快慢指针来找到链表中倒数第k个节点。首先,让快指针和慢指针同时从链表头部开始移动,快指针每次移动两步,慢指针每次移动一步。当快指针到达链表尾部时,慢指针刚好指向倒数第k个节点。

????️感谢各位同伴的支持,本期C++就讲解到这啦,如果你觉得写的不错的话,可以给个一键三连,点赞,关注+收藏,若有不足,欢迎各位在评论区讨论。    

注:扩展来自:快慢指针:解决链表问题的利器-百度开发者中心 (baidu.com)