每日一题系列(day 06)
前言:
🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈
🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,日日累积,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️
题目:
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
- 如果 n 是 快乐数 就返回 true ;不是,则返回 false 。
示例:
提示:
- 1 <= n <= 2^31 - 1
思路:
虽然力扣把这题给标为了简单,但是如果你想不明白给的第二个条件,这题和困难也相差无二,第一个条件是给你一个正整数,每个位置的平方和就是下一个位置,第二个条件其实说明了在这里只有两种情况,一种是最后变成1一直循环,另外一种情况是存在一个环使得这个数永远不能为1。是1就快乐数,不是1就不是快乐数。
我知道你还有疑问:“为什么就这两种情况呢?循环会不会是无限不相等的循环?”
可以看到,当为2时就是一个循环,当为19时最后就能得到1,所以19为快乐数,2不是快乐数,但是最让人不快乐的地方在于会不会存在无限不循环?
上面也就说明了,我们快乐数只用两种情况,一种是最后为1一直循环,一种是其他数绕圈子循环,并不存在不循环的情况。
我们知道了题目是什么意思,那我们该如何写这个题目呢?
1、其实我们仔细观察不难发现,给了我们一个数,我们就一定能推出来下一个数,而下一个数就一定能推出来下下个数…而且所推的数是固定的不变的,这种关系是不是就像我们的链表关系?
2、所以这题其实我们就可以用链表来实现,给我们的每个值就是一个个节点,我们得到下一个数的方式其实也就是指针指向的关系。
3、我们前面得出了结论:如果最后循环为1就是快乐数,如果最后循环不为1就不是快乐数,说到循环和链表你能想到什么?没错————带环链表,还记得我们是如何解决带环链表的问题的吗?没错,我们使用的是双指针法来解决带环链表的问题。
4、这样就好办了,我们只需要设置快慢指针,如果快指针已经为1了,则就是快乐数,所以只要快指针不为1我们就一直循环,如果快指针与慢指针相遇了,这时我们就要判断快指针与慢指针的时的值是不是为1,如果不是1,则表示进入了我们所说的第二种情况,进入了其他数的循环,则就不为快乐数,直接返回false即可。
代码实现:文章来源:https://www.toymoban.com/news/detail-755883.html
class Solution {
public:
int GetNext(int x)//获得下一个数
{
int tmp = 0, cnt = 0;
while(x)
{
tmp = x % 10;
cnt += tmp * tmp;
x /= 10;
}
return cnt;
}
bool isHappy(int n) {//传入的n值即为第一个节点
int quick = n, slow = n;//让两个指针都指向第一个节点
while(quick != 1)//当快指针没有变成1的时候一直循环
{
quick = GetNext(GetNext(quick));//用平方和的关系得到下一个数(链表指向的下一个值)快指针为2个数,所以调用两次
slow = GetNext(slow);//慢指针一次一个数
if(quick == slow && slow != 1) return false;//当两个指针相遇的时候,
}
return true;
}
};
最后,快乐数这题我感觉不应该标位简单,应该标位中等或者困难,很多人会被无限不循环给误导,以至于代码实现起来就比较困难,这题最主要的还是题目给的第二个条件,理解了就很简单。文章来源地址https://www.toymoban.com/news/detail-755883.html
到了这里,关于每日一题:LeetCode-202.快乐数(一点都不快乐)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!