leetcode202快乐数c++

题目描述

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

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

示例: 

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

           

代码实现

1. 用一个map存储已经访问过的数，但是当数据很多的时候，效率太低。

class Solution {
public:
    bool isHappy(int n) {
        map<int,int> m;
        while(n != 1 && m.find(n) == m.end()){
            m.insert(pair<int,int>(n,0));
            int s = 0;
            while(n){
                s += pow((n % 10),2);
                n /= 10;
            }
            n = s;
        }
        if(n == 1) return true;
        else return false;
    }
};
           

1. 用快慢指针实现

class Solution {
public:
    bool isHappy(int n) {
        int slow = n, fast = n;
        do{
            slow = f(slow);
            fast = f(fast);
            fast = f(fast);
        }while(slow != fast);
        
        if(slow == 1) return true;
        else return false;
    }
    int f(int x){
        int ans = 0;
        while(x){
            ans += pow(x%10,2);
            x /= 10;
        }
        return ans;
    }
};