LeetCode202.快乐数——java语言_leetcode 快乐数 java

题目描述：

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

「快乐数」 定义为：

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

示例 1：

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

• 02 = 1 示例 2：

输入：n = 2 输出：false

解法一：Hash集合检测循环
本题的突破口在与找到终止循环的条件，除了sum==1为一个终止条件外，当sum重复出现时，以后的结果也会重复，也为一个终止条件。
代码如下：

class Solution {
     private int gcd(int n)
    {
        int sum=0;
        while(n>0)
        {
            int temp=n%10;
            sum+=temp*temp;
            n/=10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
            Set<Integer> ans=new HashSet<Integer>();
            while(n!=1&&!ans.contains(n))
            {
               ans.add(n);
                n=gcd(n); 
            }
            return n==1;
    }
   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法二、快慢指针法
使用快慢指针，如果出现1则快指针先等于1返回TRUE即可，如果不出现，则快慢指针相遇。

class Solution {
     private int gcd(int n)
    {
        int sum=0;
        while(n>0)
        {
            int temp=n%10;
            sum+=temp*temp;
            n/=10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
          int slow=n,fast=n;
          do
          {
              slow=gcd(slow);
              fast=gcd(fast);
              fast=gcd(fast);
          }while(fast!=1&&fast!=slow);
          return fast==1;
    }
   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24