有没有网站免费的,网站界面技术方案,建设微网站,code编程网站1、题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为#xff1a;
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1#xff0c;也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1…1、题目
编写一个算法来判断一个数 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
2、解
快慢指针法 通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针但数据仍然形成链表结构。起始数字是链表的头 “节点”链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。
意识到我们实际有个链表那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手一个跑的快一个跑得慢。在龟兔赛跑的寓言中跑的慢的称为 “乌龟”跑得快的称为 “兔子”。
不管乌龟和兔子在循环中从哪里开始它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点在它们的移动方向上。
算法
我们不是只跟踪链表中的一个值而是跟踪两个值称为快跑者和慢跑者。在算法的每一步中慢速在链表中前进 1 个节点快跑者前进 2 个节点对 getNext(n) 函数的嵌套调用。
如果 n 是一个快乐数即没有循环那么快跑者最终会比慢跑者先到达数字 1。
如果 n 不是一个快乐的数字那么最终快跑者和慢跑者将在同一个数字上相遇。
int bitNumberPow(int n)
{int tempSum 0;//先求每位数的平方和while(n 0){int temp n % 10;tempSum pow(temp, 2);n n / 10;}return tempSum;
}
bool isHappyA(int n)
{int fast n;int slow n;do{fast bitNumberPow(fast);fast bitNumberPow(fast);slow bitNumberPow(slow);} while (fast ! slow);return 1 slow;
}
