202.快乐数

链接：202.快乐数
难度：Easy
标签：哈希表、数学、双指针
简介：编写一个算法来判断一个数 n 是不是快乐数。

题解 1 - typescript

• 编辑时间：2021-03-06
• 执行用时：80ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：循环计算。

function isHappy(n: number): boolean {
  const set = new Set();
  while (n !== 1) {
    if (set.has(n)) return false;
    set.add(n);
    let sum = 0;
    while (n !== 0) {
      sum += (n % 10) ** 2;
      n = ~~(n / 10);
    }
    n = sum;
  }
  return true;
}

题解 2 - cpp

• 编辑时间：2022-03-03
• 内存消耗：5.6MB
• 编程语言：cpp
• 解法介绍：快慢指针。

class Solution {
   public:
    int next(int n) {
        int ans = 0;
        for (; n; n /= 10) ans += pow(n % 10, 2);
        return ans;
    }
    bool isHappy(int n) {
        int slow = n, fast = n;
        while (fast != 1) {
            slow = next(slow);
            fast = next(next(fast));
            if (slow == fast) break;
        }
        return fast == 1;
    }
};

题解 3 - javascript

• 编辑时间：2020-04-30
• 执行用时：72ms
• 内存消耗：35.2MB
• 编程语言：javascript
• 解法介绍：递归判断，使用 Set 判断是否重复。

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
  const set = new Set();
  return happy(n);
  function happy(n) {
    if (set.has(n)) return false;
    set.add(n);
    let num = 0;
    while (n !== 0) {
      num += (n % 10) ** 2;
      n = Math.floor(n / 10);
    }
    if (num === 1) return true;
    else return happy(num);
  }
};

题解 4 - c

• 编辑时间：2021-11-19
• 内存消耗：5.3MB
• 编程语言：c
• 解法介绍：快慢指针。

int comp(int n) {
    int sum = 0, num;
    while (n) {
        num = n % 10;
        sum += num * num;
        n /= 10;
    }
    return sum;
}
bool isHappy(int n){
    int fast = n, slow = n;
    do{
        fast = comp(comp(fast));
        slow = comp(slow);
    } while(fast != slow);
    return slow == 1;
}

题解 5 - cpp

• 编辑时间：2022-03-03
• 执行用时：4ms
• 内存消耗：6.2MB
• 编程语言：cpp
• 解法介绍：递归，记录当前值是否被遍历过。

class Solution {
   public:
    unordered_set<int> s;
    bool isHappy(int n) {
        if (s.count(n)) return 0;
        s.insert(n);
        int ans = 0;
        for (; n; n /= 10) ans += pow(n % 10, 2);
        if (ans == 1) return 1;
        return isHappy(ans);
    }
};