算法题每日一练---第74天：快乐数

一、问题描述

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

题目链接：快乐数。

二、题目要求

样例

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

考察

数学思想
建议用时15~35min

三、问题分析

快乐数理解起来很容易，就是拆分数位平方相加就行。这里我们需要一个结束的条件，那就是必须为2位数。

当n属于1~9时，退出位数相加的循环。而最后的单位数字只有1或7才可以结束循环成为快乐数。

如7的循环流程：7^2=49=4^2+9^2=97=9^2+7^2=130=1^2+3^2+0=10=1

其它的数字，暂且成为不快乐数，就会进入一个4→16→37→58→89→145→42→20→4的死循环里面，如此循环往复。

四、编码实现

classSolution {
public:
boolisHappy(intn) {
intk,ans;//初始化定义while(n>9)//单位数字直接退出        {
k=n;//暂存ans=0;//存储位数平方相加的结果while(k)
            {
ans+=(k%10)*(k%10);//平方相加k=k/10;
            }
n=ans;
        }
if(n==1||n==7)//1或7，输出truereturntrue;
elsereturnfalse;
    }
};

五、测试结果