Leetcode 202 快乐数（HashSet，环形链表思想）

题目链接>>>>>>>>>>>>>>

---

解法1 ： 用HashSet来检测循环

【HashSet】
计算sum，如果sum == 1 ，就可以返回true
如果hashset中没有sum，那就一直循环，但如果发现hashset中包含当前sum，就是死循环喽，那就可以返回false ！
需要使用hash表来保存每次的sum。

时间复杂度O：(logN) [见后]
空间复杂度O：(logN) [见后]

class Solution {
    public boolean isHappy(int n){
        // 如果sum == 1 ，就可以返回true
        // 如果发现hashset中包含当前sum，就是死循环喽，那就可以返回false
        
        // 需要使用hash表来保存每次的sum

        int sum = 0;
        HashSet<Integer> hashset = new HashSet<>();

        while(!hashset.contains(sum)){ // 当hashset中不包含当前sum就一直循环，包含了就说明死循环了，就输出false
            
            sum = 0;
            hashset.add(n);// 把n加进hashset

            // 计算sum
            while(n / 10 != 0){
                sum += (n%10)* (n%10);
                n = n/10;
            }
            sum += (n%10)* (n%10);

            if(sum == 1) return true;  // 如果sum为1则输出true
           
            // n = sum
            n = sum;
            
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

java的hashset中add方法有返回值，就可以不用contains方法了，可以合二为一——add方法有返回值true和false
在上一个方法的基础上，应用了hashset.add，如果成功添加就有返回值true，如果没有成功添加就有返回值false

class Solution {
    public boolean isHappy(int n){
        int sum = 0;
        HashSet<Integer> hashset = new HashSet<>();
        while(hashset.add(sum)){ // 当hashset中不包含当前sum就一直循环，包含了就说明死循环了，就输出false
            sum = 0;
            // 计算sum
            while(n / 10 != 0){
                sum += (n%10)* (n%10);
                n = n/10;
            }
            sum += (n%10)* (n%10);
            if(sum == 1) return true; 
            n = sum;  
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

⭐️为什么说数字n的位数由log n给定呢？

数字n的位数是log n是因为：我们通常使用的数字系统是以10为基数的十进制系统。在十进制系统中，一个数字n的位数可以通过对n取以10为底的对数来计算。例如，对于数字n=12345，它的位数是log10(12345) ≈ 4.09，取整后为5。因此，我们可以说数字n的位数是log n。同样地，在其他进制系统中，我们可以使用相应的基数来计算数字的位数。

---

解法2 ： 链表的思想[出现循环表示链表出现环]，使用快慢指针法

参照LeetCose环形链表
环形链表思想，快2慢1指针，好好好方法哦✋

🔴核心思想：
如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。
如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

时间复杂度:O(logN)
空间复杂度:O(1)

class Solution {
    public boolean isHappy(int n){
        // 使用环形链表的判断方法
        // 快2慢1指针，只要两者相遇则说明有环，无法相遇则无环
        int slow = square(n);
        int fast = square(square(n));   
        while(slow != fast){
            slow = square(slow);
            fast = square(square(fast));   
        }
        if(slow == 1) return true;
        return false;
    }

    public int square(int n){ // 用来处理平方和求和操作
        int sum = 0;
        while(n / 10 != 0){
            sum += (n%10) * (n%10);
            n = n/10;
        }
        sum +=  (n%10) * (n%10);
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24