题目描述
编写一个算法来判断一个数
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
计算每一个数，它每个位置上的数字的平方和
然后判断是否为1
如果为1就是快乐数，如果不为1，那么就存入一个set中，如果平方和已经存在在了set中，那么就说明不是。因为非快乐数，最终会形成循环
例如2和3
代码1
class Solution {
public boolean isHappy(int n) {
//保存不是快乐数的值
Set<Integer> set = new HashSet<>();
//n！=1并且不在set中
while (n!=1&&!set.contains(n)){
set.add(n);
//计算下一个
n=happy(n);
}
//跳出循环的条件1、是快乐数2、在set中，不是快乐数，不是 快乐数不等于1
return n==1;
}
//计算n每个位置上的数字的平方和
public int happy(int n){
int sum=0;
while(n>0){
//依次取个位、十位、百位、、、上的数
int digit = n%10;
sum+=digit*digit;//求和
//计算除掉最后一位后的数
n/=10;
}
return sum;
}
}思路2
快慢指针方法（也称为Floyd的龟兔赛跑算法）
因为发现非快乐数是一个循环，所以可以使用Floyd的龟兔赛跑算法
可以把非快乐数的情况看做是一个环
将每一次迭代看作是在一个“隐式图”上移动。这个图是由所有可能的平方和构成的，而从一个数到它的下一个平方和之间有一条边。如果这个过程进入了一个循环，那么快慢指针最终会在循环中相遇。
模拟这个过程：
- 初始化两个指针（或称为变量），一个快指针（每次迭代计算两次平方和）和一个慢指针（每次迭代计算一次平方和）。
- 同时移动快指针和慢指针，直到它们相遇或快指针达到1（快乐数的情况）。
- 如果在迭代过程中，快指针和慢指针指向了同一个数（即它们相遇了），那么说明原数不是一个快乐数，因为它进入了一个循环。
- 如果快指针达到了1，那么原数是一个快乐数。
Floyd的龟兔赛跑算法
Floyd的龟兔赛跑算法，正式名称为Floyd判圈算法（Floyd Cycle Detection Algorithm），是一种用于检测链表、迭代函数、有限状态机等结构中是否存在环的经典算法。这个算法因其直观性和高效性而广受欢迎，其基本思想源自快慢指针的策略，可以形象地比喻为龟兔赛跑。
算法原理
快慢指针：算法使用两个指针，一个称为慢指针（slow），另一个称为快指针（fast）。初始时，两者都指向链表（或结构）的头部。在每一步迭代中，慢指针向前移动一步，而快指针向前移动两步（或多步，只要保证快指针比慢指针快即可）。
相遇检测：
如果链表中存在环，那么快慢指针最终会在环内的某个点相遇。
如果链表中不存在环，那么快指针会首先到达链表末尾（即指向null），此时可以判断链表中无环。
环的起点和长度：
在检测到环后，可以将慢指针重新指向链表头部，而快指针保持在相遇点。然后，两者以相同的速度（每次一步）向前移动，它们会在环的起点再次相遇。
通过移动其中一个指针（如慢指针）并计数，可以计算出环的长度。
算法特点
时间复杂度：Floyd判圈算法的时间复杂度为O(n)，其中n是链表的长度（或结构的规模）。在最坏情况下，快指针需要遍历整个链表（或结构）一次，并额外遍历环的长度若干次，但由于环的长度不会超过链表的总长度，因此整体时间复杂度仍然是线性的。
空间复杂度：算法的空间复杂度为O(1)，因为它只使用了两个额外的指针，而不需要额外的数据结构来存储节点信息。
应用场景
Floyd判圈算法不仅限于链表中的环检测，还可以应用于其他需要检测循环结构的场景，如迭代函数中的周期解、有限状态机中的循环状态等。
示例代码（链表中的环检测）
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
}在这段示例代码中，hasCycle方法接受一个链表的头节点作为输入，并返回一个布尔值表示链表中是否存在环。如果存在环，则返回true；否则返回false。
代码2
class Solution {
public boolean isHappy(int n) {
//定义快慢指针
int slow =n;
int fast=happy(slow);
//当slow不等于fast说明未追上
while (slow!=fast){
//slow 移动一步
//fast移动两步
slow =happy(slow);
fast = happy(happy(fast));
}
//追上后判断是否是1
return slow==1;
}
//计算n每个位置上的数字的平方和
public int happy(int n){
int sum=0;
while(n>0){
//依次取个位、十位、百位、、、上的数
int digit = n%10;
sum+=digit*digit;//求和
//计算除掉最后一位后的数
n/=10;
}
return sum;
}
}优化：上述代码可以进行一下优化，将每次算出的不为1的和用set存储，当set中已经有该值时，说明肯定会有循环
class Solution {
public boolean isHappy(int n) {
//定义快慢指针
int slow =n;
int fast=happy(slow);
Set<Integer> set= new HashSet<>();
//当slow不等于fast说明未追上
while (slow!=fast&&!set.contains(fast)){
//非快乐数进set
set.add(slow);
//slow 移动一步
//fast移动两步
slow =happy(slow);
fast = happy(happy(fast));
//set中存在，说明有循环肯定不是快乐数直接返回false
if(set.contains(fast)){
return false;
}
}
//追上后判断是否是1
return slow==1;
}
//计算n每个位置上的数字的平方和
public int happy(int n){
int sum=0;
while(n>0){
//依次取个位、十位、百位、、、上的数
int digit = n%10;
sum+=digit*digit;//求和
//计算除掉最后一位后的数
n/=10;
}
return sum;
}
}