[4]力扣每日一题

题目呈现如下:

题目传送门

思路介绍:

• 首先我猜测如果不是快乐数,一定会存在一个循环.我们假设n是一个三位数字,那么每位的平方和最多为(9^2+9^2+9^2=243),由于243也是一个三位数,那么之后求各位平方和一定不会超过243,所以循环的元素最大为243.所以一旦知道样例数据大小,就可以把循环次数写死,如下面的解法1.

• 其次我们可以用一个线性的数据结构存储每次的结果.出现1则返回true,而一旦发现本次运算的结果在之前出现过,则确定存在循环,返回false.

• 再者通过反复的尝试,可以发现:一旦出现循环,则必然是4-16-37-58-89-145-42-20-4循环,把出现这些数字作为循环退出条件.

• 最后可以采用快慢指针的方法,如果快指针和慢指针找到1,则返回1;一旦出现循环,那么快指针一定能追上慢指针,返回false.

下附AC代码:

// F1:暴力解
class Solution {
public:
    bool isHappy(int n) {
        for(int i = 0; i < 243; ++i) {
            int res = 0;
            while(n>0) {
                res += (n%10)*(n%10);
                n /= 10;
            }
            if(res==1) return true;
            n = res;
        }
        return false;
    }
};
// F2:记录出现的数
// 在c++11标准中需要引入头文件<unordered_map>
class Solution {
public:
    bool isHappy(int n) {
        unordered_map<int,bool> isSeen;
        while(2333) {
			int res = 0;
            while(n>0) {
                res += (n%10)*(n%10);
                n /= 10;
            }
            if(res == 1) return true;
            // 在unordered中查找
            else if(isSeen.find(res)!=isSeen.end()) return false; 
            // 找不到则插入
            else isSeen.insert(make_pair(res,true));
            n = res;
        }
    }
};