200-判断一个数是不是快乐数

蔚落 2022-10-30 11:22 156阅读 0赞

**题目如下：**  
编写一个算法来判断一个数 n 是不是快乐数。  
「**快乐数**」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。  
如果 n 是快乐数就返回 True ；不是，则返回 False 。

**示例：**

输入：19  
输出：true  
解释：  
1^2 + 9^2 = 82  
8^2 + 2^2 = 68  
6^2 + 8^2 = 100  
1^2 + 0^2 + 0^2 = 1

## 解题思路 ##

**使用快慢指针的方法来进行判断  
为什么要使用快慢指针呢？**  
1、快慢指针是快指针走两步，慢指针走一步，假如有环的话，那么快慢指针一定会在某一个位置相遇的，所以快慢指针经常使用来判断链表中是否存在环的情况，假如没有环快指针与慢指针是无法相遇在某个位置的。  
2、对于这道题目来说，快指针走两步，也就是计算两次平方和，慢指针走一次计算一次平方和，假如输入的数字是快乐数，那么一定是不存在环的，无环的情况下，快指针的结果最后一定是到达最终的数字1的（怎么样计算都是1），这个时候当慢指针追上快指针的时候一定会相遇在1，这个时候判断循环退出之后两个相遇的位置是否是1，即可判断是否是快乐数。  
3、当不是快乐数的时候，快慢指针也会相遇，因为怎么样平方计算都不会到达1，因为这中间存在着重复的数字而且是永远到达不了1的，所以存在环，两者一定会在某一个位置上相遇并且相遇的位置一定不是1，所以可以判断其不是快乐数。

**代码如下：**

#include<stdio.h>
    int func(int x)
    {
        
    	int sum = 0;
    	while (x != 0)
    	{
        
    		int i = x % 10;
    		sum += (i * i);
    		x /= 10;
    	}
    	return sum;
    }
    
    bool isHappy(int n)//判断是否是快乐数
    {
        
    	int fast = n, slow = n;//定义快慢
    	do
    	{
        
    		fast = func(fast);
    		fast = func(fast);
    		slow = func(slow);
    	} while (fast != slow);
    
    	return slow == 1;
    }
    
    int main()
    {
        
    	printf("%d\n",isHappy(19));
    	printf("%d\n",isHappy(12));
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/542f145c8b944de5b0be301aa469711a.png