02. 快乐数(C++)---"快慢指针"解题

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

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

——题目难度: 简单


 

思路
运用快慢指针，慢指针一次往后go一次，快指针一次往后go两次

在第一个周期里，这样每次两者的相对距离都会增加1，当快指针已经循环完了一个周期，会有以下两种情况：
1.快指针已经到了1了，那么快指针就会接下来一直是1，直到慢指针也是1
2.快指针已经开始第二次循环了，快指针将在它的下个循环里每次和慢指针缩短1的距离，那么快指针将在慢指针刚好循环完一个周期时"追上"慢指针
 

-下面代码
 

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

结果