题目

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

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。

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

示例 1：

输入：n = 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

解题方法

哈希表

通过set记录出现过的数字，若重复则证明进入死循环，返回false。若数字变为1，则证明是快乐数，返回true。
时间复杂度O(logn)，空间复杂度O(logn)。

class Solution {
public:
  bool isHappy(int n) {
      unordered_set<int> num;
      while(n!=1){
          if(num.count(n))    return false;
          else    num.insert(n);
          int temp = 0;
          while(n!=0){
              temp+=(n%10)*(n%10);
              n = n/10;
          }
          n = temp;
      }
      return true;
  }
};

双指针

通过两个指针进行循环，快指针追上慢指针则证明进入死循环。
降低空间复杂度。
时间复杂度O(logn)，空间复杂度O(log1)。

class Solution {
public:
  int nextnum(int n) {
      int temp = 0;
      while(n!=0){
          temp+=(n%10)*(n%10);
          n = n/10;
      }
      return temp;
  }

  bool isHappy(int n) {
      int slow = n, fast = n;
      while(fast!=1){
          slow = nextnum(slow);
          fast = nextnum(nextnum(fast));
          if(fast!=1) {
              if(slow==fast)    return false;
          }
      }
      return true;
  }
};

LeetCode

202. 快乐数

题目

解题方法

哈希表

双指针