202. Happy Number
原题链接
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
题目大意:(谷歌翻译)
编写一个算法来确定一个数字是否“开心”。
幸福的数字是由以下过程定义的数字:从任何正整数开始,将数字替换为数字的平方和,并重复该过程,直到数字等于1(将保留在哪里),或者它在不包括1的循环中无休止地循环,这个过程以1结尾的数字是快乐的数字。
注意:并不可以无限循环下去!!!!!!!不是happy number的数字要返回false,刚开始理解错了,懵逼很久….
Example: 19 is a happy number
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
思路1:
- 写一个方法计算平方和
- 定义两个数slow, fast来记录前后两次得到的平方和
- 如果前后两个数字相等,进入死循环,这是就需要跳出循环
- 判断slow是否为1,是的话返回true,否则返回false
- 参考链接
代码如下:
class Solution {
public:
bool isHappy(int n) {//3ms
if(n <= 0)//确保n为正整数
return false;
int slow=n, fast=n;
do{
slow = digitSquaresSum(slow);//慢指针
fast = digitSquaresSum(fast);
fast = digitSquaresSum(fast);//快指针 比慢指针多执行一次digitSquaresSum方法
}while(slow != fast);//慢指针和快指针结果相同,跳出循环
if(slow == 1)
return true;
else
return false;
}
int digitSquaresSum(int n){//计算平方和
int squares = 0;
while(n != 0){
int temp = n%10;
squares += (temp*temp);
n = n/10;
}
return squares;
}
};
思路2:
- 本来我以为不用哈希表就是最快的解法了,但是天外有人
- 刚开始我没看懂,就拿之前写的算法测试了1-9这些数字,发现只有1和7返回true,并且不管循环多少次平方和最终还是要小于10的
- 于是就有了下面的解法
代码如下:
bool isHappy(int n) {//0ms
if(n == 0) return 0;
int squares = n;
while(squares >= 10){
int temp = 0;
while(squares) {
temp += (squares%10)*(squares%10);
squares = squares/10;
}
squares = temp;
}
if(squares == 1 || squares == 7)
return true;
else
return false;
}