題目網址：https://leetcode.cn/problems/happy-number/

題意：判斷整數 n 是否為快樂數。

快樂數的定義為：

  • 對於一正整數, 每次將該數轉換為它每一位數的平方和
  • 重複此步驟直到該數為 1, 也有可能進入無窮迴圈（始終無法變成 1 ）
  • 如果該數能變成 1, 則它就是快樂數

若 n 為快樂數, 則返回 true; 否則, 返回 false。

Solution 1：

想法：利用 hash table 來記錄出現過的數, 一旦重複出現, 代表會無限循環

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> s{n};
        while (n != 1) {
            n = squareSum(n);
            if (s.find(n) != s.end()) {
                return false;
            }
            s.emplace(n);
        }
        return true;
    }

private:
    int squareSum(int n){
        int sum = 0;
        while (n != 0) {
            sum += pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }
};
  • time：$O(log(n))$ ➔ 令 k 為 n 除以 10 的次數, $\dfrac{n}{10^k} = 1 ➔ k = log(n)$
  • space：$O(log(n))$ ➔ s 中儲存 $log(n)$ 次轉換後的元素

Solution 2：

想法：概念同 Solution 1, 只是改成利用 Two Pointers 來判斷是否出現重複的數, 可參考 141. Linked List Cycle, slow 每次只轉換一次, 而 fast 每次轉換兩次

  • 若存在循環（重複數）, 則 slow 和 fast 必相遇（fast 倒追 slow） ➔ n 不為快樂數
  • 若不存在循環, 經過 x 步後 fast 必先變成 1, 然後再經過 x 步後 slow 才會接著變成 1
class Solution {
public:
    bool isHappy(int n) {
        int slow = squareSum(n);
        int fast = squareSum(squareSum(n));

        while (fast != 1) {
            if (slow == fast) {
                return false;
            }
            slow = squareSum(slow);
            fast = squareSum(squareSum(fast));
        }
        return true;
    }

private:
    int squareSum(int n){
        int sum = 0;
        while (n != 0) {
            sum += pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }
};
  • time：$O(log(n))$ ➔ 令 k 為 n 除以 10 的次數, $\dfrac{n}{10^k} = 1 ➔ k = log(n)$
  • space：$O(1)$ ➔ 只需常數空間