朝阳网站制作,网站设计费用志,筑方装饰口碑怎么样,杭州网络网站建设优质博文#xff1a;IT-BLOG-CN
一、题目
编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为#xff1a;对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为1#xff0c;也可能是无限循环但始终变不到1。如…优质博文IT-BLOG-CN
一、题目
编写一个算法来判断一个数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 1 n 231 - 1 二、代码
【1】用哈希集合检测循环 可以先举几个例子。我们从7开始。则下一个数字是49因为7^249然后下一个数字是97因为4^29^297。我们可以不断重复该的过程直到我们得到1。因为我们得到了1我们知道7是一个快乐数函数应该返回true。再举一个例子让我们从116开始。通过反复通过平方和计算下一个数字我们最终得到58再继续计算之后我们又回到58。由于我们回到了一个已经计算过的数字可以知道有一个循环因此不可能达到1。所以对于116函数应该返回false。
根据我们的探索我们猜测会有以下三种可能 1、最终会得到1。 2、最终会进入循环。 3、值会越来越大最后接近无穷大。
第三个情况比较难以检测和处理。我们怎么知道它会继续变大而不是最终得到1呢我们可以仔细想一想每一位数的最大数字的下一位数是多少。
DigitsLargestNext19812991623999243499993241399999999999991053
对于3位数的数字它不可能大于243。这意味着它要么被困在243以下的循环内要么跌到1。4位或4位以上的数字在每一步都会丢失一位直到降到3位为止。所以我们知道最坏的情况下算法可能会在243以下的所有数字上循环然后回到它已经到过的一个循环或者回到1。但它不会无限期地进行下去所以我们排除第三种选择。
即使在代码中你不需要处理第三种情况你仍然需要理解为什么它永远不会发生这样你就可以证明为什么你不处理它。
class Solution {public boolean isHappy(int n) {SetInteger seen new HashSet();while (n ! 1 !seen.contains(n)) {seen.add(n);n getNext(n);}return n 1;}private int getNext(int n) {int totalSum 0;while (n 0) {int d n % 10;n n / 10;totalSum d * d;}return totalSum;}
}时间复杂度 O(243⋅3lognloglognlogloglogn)... O(logn)。 1、查找给定数字的下一个值的成本为O(logn)因为我们正在处理数字中的每位数字而数字中的位数由logn给定。 2、要计算出总的时间复杂度我们需要仔细考虑循环中有多少个数字它们有多大。 3、我们在上面确定一旦一个数字低于243它就不可能回到243以上。因此我们就可以用243以下最长循环的长度来代替243不过因为常数无论如何都无关紧要所以我们不会担心它。 4、对于高于243的n我们需要考虑循环中每个数高于243的成本。通过数学运算我们可以证明在最坏的情况下这些成本将是O(logn)O(loglogn)O(logloglogn)...。幸运的是O(logn)是占主导地位的部分而其他部分相比之下都很小总的来说它们的总和小于logn所以我们可以忽略它们。
空间复杂度 O(logn)与时间复杂度密切相关的是衡量我们放入哈希集合中的数字以及它们有多大的指标。对于足够大的n大部分空间将由n本身占用。我们可以很容易地优化到O(243⋅3)O(1)方法是只保存集合中小于243的数字因为对于较高的数字无论如何都不可能返回到它们。
【2】数学 根据我们之前的分析我们知道它必须低于243。因此我们知道任何循环都必须包含小于243的数字用这么小的数字编写一个能找到所有周期的强力程序并不困难。如果这样做您会发现只有一个循环4→16→37→58→89→145→42→20→4。所有其他数字都在进入这个循环的链上或者在进入1的链上。因此我们可以硬编码一个包含这些数字的散列集如果我们达到其中一个数字那么我们就知道在循环中。
class Solution {private static SetInteger cycleMembers new HashSet(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));public boolean isHappy(int n) {while (n ! 1 !cycleMembers.contains(n)) {n getNext(n);}return n 1;}public int getNext(int n) {int totalSum 0;while (n 0) {int d n % 10;n n / 10;totalSum d * d;}return totalSum;}
}时间复杂度 O(logn)。 空间复杂度 O(1)我们没有保留我们所遇到的数字的历史记录。硬编码哈希集的大小是固定的。
【3】快慢指针法 通过反复调用getNext(n)得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针但数据仍然形成链表结构。起始数字是链表的头 “节点”链中的所有其他数字都是节点。next指针是通过调用getNext(n)函数获得。意识到我们实际有个链表那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手一个跑的快一个跑得慢。在龟兔赛跑的寓言中跑的慢的称为 “乌龟”跑得快的称为 “兔子”。
我们不是只跟踪链表中的一个值而是跟踪两个值称为快跑者和慢跑者。在算法的每一步中慢速在链表中前进1个节点快跑者前进2个节点对getNext(n)函数的嵌套调用。 1、如果n是一个快乐数即没有循环那么快跑者最终会比慢跑者先到达数字1。 2、如果n不是一个快乐的数字那么最终快跑者和慢跑者将在同一个数字上相遇。
class Solution {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;}public int getNext(int n) {int totalSum 0;while (n 0) {int d n % 10;n n / 10;totalSum d * d;}return totalSum;}
}时间复杂度 O(logn)。该分析建立在对前一种方法的分析的基础上但是这次我们需要跟踪两个指针而不是一个指针来分析以及在它们相遇前需要绕着这个循环走多少次。如果没有循环那么快跑者将先到达1慢跑者将到达链表中的一半。我们知道最坏的情况下成本是O(2⋅logn)O(logn)。一旦两个指针都在循环中在每个循环中快跑者将离慢跑者更近一步。一旦快跑者落后慢跑者一步他们就会在下一步相遇。假设循环中有k个数字。如果他们的起点是相隔k−1的位置这是他们可以开始的最远的距离那么快跑者需要k−1步才能到达慢跑者这对于我们的目的来说也是不变的。因此主操作仍然在计算起始n的下一个值即O(logn)。 空间复杂度 O(1)对于这种方法我们不需要哈希集来检测循环。指针需要常数的额外空间。
