LeetCode_LinkedList_202. Happy Number 快乐数（C++/Java）【循环链表，快慢指针】

目录

​​一，题目描述​​

​​英文描述​​

​​中文描述​​

​​二，解题思路​​

​​方法一——集合​​

​​方法二——循环链表​​

​​三，AC代码​​

​​C++​​

​​Java​​

​​四，解题过程​​

​​第一博​​

一，题目描述

英文描述

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19

Output: true

Explanation:

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2

Output: false

Constraints:

1 <= n <= 2^31 - 1

中文描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：19

输出：true

解释：

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2

输出：false

提示：

1 <= n <= 2^31 - 1

来源：力扣（LeetCode）

链接：​​​https://leetcode-cn.com/problems/happy-number​​ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

方法一——集合

这个是最容易想到的一种思路。

将每个遍历过的值（除了1）存放在集合中，当新值出现时，查看集合中是否已存在。

若存在说明正在经历一种循环，而且永远不会到达1

方法二——循环链表

由于规则具有唯一指向性（给定一个数，他的下一个数字就确定了），所以可以将规则的推进过程可以看作一个单向链表，当运行过程中出现重复后，就说明链表中存在循环，该链表为循环链表。

因此如果发现链表是循环链表之前没有出现1，就说明该数字不是快乐数。

此方法更重要的是锻炼算法思维，理解循环链表的另一种用法。

需要注意一点：这里判断指针是否相遇，不是依据指针是否相等，而是节点对应的值是否相等。

三，AC代码

C++

class Solution {
public:
    struct Node {
        Node(int data) : data(data), next(NULL) {}
        int data;
        Node *next;
    };
    int getNextData(int n) {
        int res = 0;
        while(n != 0) {
            res += pow(n % 10, 2);
            n /= 10;
        }
        return res;
    }
    bool isHappy(int n) {
        Node *head = new Node(n);
        int tem = getNextData(n);
        head->next = new Node(tem);
        if(head->data == 1 || head->next->data == 1) return true;
        Node *slow = head, *fast = head->next;
        // 注意这里判断两指针是否相遇用的是值而不是指针本身
        while(fast->data != 1 && slow->data != fast->data) {
            slow = slow->next;
            tem = getNextData(tem);
            if(tem == 1) return true;
            fast->next = new Node(tem);
            tem = getNextData(tem);
            fast->next->next = new Node(tem);
            fast = fast->next->next;
        }
        return fast->data == 1;
    }
};      

Java

class Solution {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    int getNextData(int n) {
        int res = 0;
        while(n != 0) {
            res += Math.pow(n % 10, 2);
            n /= 10;
        }
        return res;
    }
    public boolean isHappy(int n) {
        ListNode head = new ListNode(n);
        int tem = getNextData(n);
        head.next =new ListNode(tem);
        if(head.val == 1 || head.next.val == 1) return true;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast.val != 1 && slow.val != fast.val) {
            slow = slow.next;
            tem = getNextData(tem);
            if(tem == 1) return true;
            fast.next = new ListNode(tem);
            tem = getNextData(tem);
            fast.next.next = new ListNode(tem);
            fast = fast.next.next;
        }
        return fast.val == 1;
    }
}      

四，解题过程

第一博