编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为:
如果 n 是 快乐数 就返回 true ;不是,则返回 false 。
示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输入:n = 2
输出:false
提示:
算法
算法分为两部分,我们需要设计和编写代码。
第 1 部分我们按照题目的要求做数位分离,求平方和。
第 2 部分可以使用哈希集合完成。每次生成链中的下一个数字时,我们都会检查它是否已经在哈希集合中。
我们使用哈希集合而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集合中需要 O(1) 的时间,而对于其他数据结构,则需要 O(n) 的时间。选择正确的数据结构是解决这些问题的关键部分。
class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
复杂度分析
通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针,但数据仍然形成链表结构。起始数字是链表的头 “节点”,链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。
意识到我们实际有个链表,那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手,一个跑的快,一个跑得慢。在龟兔赛跑的寓言中,跑的慢的称为 “乌龟”,跑得快的称为 “兔子”。
不管乌龟和兔子在循环中从哪里开始,它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点(在它们的移动方向上)。
算法
我们不是只跟踪链表中的一个值,而是跟踪两个值,称为快跑者和慢跑者。在算法的每一步中,慢速在链表中前进 1 个节点,快跑者前进 2 个节点(对 getNext(n) 函数的嵌套调用)。
如果 n 是一个快乐数,即没有循环,那么快跑者最终会比慢跑者先到达数字 1。
如果 n 不是一个快乐的数字,那么最终快跑者和慢跑者将在同一个数字上相遇。
class Solution {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
复杂度分析
前两种方法是你在面试中应该想到的。第三种方法不是你在面试中会写的,而是针对对数学好奇的人,因为它很有趣。
下一个值可能比自己大的最大数字是什么?根据我们之前的分析,我们知道它必须低于 243。因此,我们知道任何循环都必须包含小于 243 的数字,用这么小的数字,编写一个能找到所有周期的强力程序并不困难。
如果这样做,您会发现只有一个循环:44→16→37→58→89→145→42→20→4。所有其他数字都在进入这个循环的链上,或者在进入 1 的链上。
因此,我们可以硬编码一个包含这些数字的散列集,如果我们达到其中一个数字,那么我们就知道在循环中。
算法
class Solution {
private static Set<Integer> cycleMembers =
new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
while (n != 1 && !cycleMembers.contains(n)) {
n = getNext(n);
}
return n == 1;
}
}
复杂度分析
class Solution {
public boolean isHappy(int n) {
int slow_runner = n;
int fast_runner = getNextNumber(n);
while (fast_runner != 1 && slow_runner != fast_runner){
slow_runner = getNextNumber(slow_runner);
fast_runner = getNextNumber(getNextNumber(fast_runner));
}
if(fast_runner ==1)return true;
else return false;
}
public static int getNextNumber(int n){
int total = 0;
while(n !=0 ){
int a = n % 10;
total += a*a;
n = n/10;
}
return total;
}
}