【LeetCode】202. 快乐数 - hash表 / 快慢指针

202. 快乐数

2023-9-5 09:56:15

关键是怎么去判断循环：

• hash表：
  每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。
  • 如果它不在哈希集合中，我们应该添加它。
  • 如果它在哈希集合中，这意味着我们处于一个循环中，因此应该返回 false
• 快慢指针：
  跟踪两个值，称为快跑者和慢跑者。在算法的每一步中，慢速在链表中前进 1 个节点，快跑者前进 2 个节点（对 getNext(n) 函数的嵌套调用）。
  • 如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。
  • 如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            n = getNum(n);
        }
        return n == 1 ;
    }

    /**
     * 19 -> 1^2 + 9^2 = 82
     */
    private int getNum(int n) {
        int totalSum = 0;
        while (n > 0) {
            int add = n % 10;
            n = n / 10;
            totalSum = n * n;
        }
        return totalSum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2023-9-6 19:40:51

第二次写的，使用的是hash表进行判断循环。

但是写的时候，由于过于自信了，但是还是有小问题出现：比如说私有方法忘记了返回值，忘记把数放到hash表里面。

下次需要注意这些问题：“无论会不会，都需要按照自己的想法一步一步来。”

附上代码：

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set =  new HashSet<Integer>();
        while ( n != 1 && !set.contains(n)){
            set.add(n);
            n = getNum(n);
        }
        return n ==1;
    }

    private int getNum(int n){
        int total = 0;
        int num = 0;
        while(n != 0){
            num = n % 10;
            n = n / 10;
            total += num * num;
        }
        return total;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21