【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;}
}

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;}
}