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;
    }
}      

四，解題過程

第一博