P180 快乐数

描述#

这个题目说的是，给你一个整数 n，你要实现一个算法来判断它是否为快乐数。

快乐数的定义是：从任意正整数开始，将它变换为十进制位上各个数字的平方和。不断重复这个变换过程，如果最后数字可以变换成 1，那么这个数字就是快乐数；否则它会在一系列不包含 1 的数字之间循环变换，这样的数字不是快乐数。

比如说，给你的整数 n 等于 28：
n = 28
接着将数字变换为十进制位上各个数字的平方和：
2^2 + 8^2 = 4 + 64 = 68
6^2 + 8^2 = 36 + 64 = 100
1^2 + 0^2 + 0^2 = 1
至此，整数 28 变换成 1。因此 28 是一个快乐数，返回 true。

相关视频：判断单链表是否有环

代码#

public class AlgoCasts {

  private int transform(int n) {
    int sum = 0;
    while (n != 0) {
      int a = n % 10;
      sum += a * a;
      n /= 10;
    }
    return sum;
  }

  // Time: O(1), Space: O(1)
  public boolean isHappyHashSet(int n) {
    if (n <= 0) return false;
    Set<Integer> set = new HashSet<>();
    for (int i = n; i != 1; i = transform(i)) {
      if (set.contains(i)) return false;
      set.add(i);
    }
    return true;
  }

  // Time: O(1), Space: O(1)
  public boolean isHappyTwoPointer(int n) {
    if (n <= 0) return false;
    int fast = n, slow = n;
    while (true) {
      fast = transform(transform(fast));
      slow = transform(slow);
      if (fast == 1) return true;
      if (fast == slow) return false;
    }
  }

  private static final boolean[] happy = new boolean[101];
  static {
    happy[1] = true; happy[7] = true; happy[10] = true; happy[13] = true;
    happy[19] = true; happy[23] = true; happy[28] = true; happy[31] = true;
    happy[32] = true; happy[44] = true; happy[49] = true; happy[68] = true;
    happy[70] = true; happy[79] = true; happy[82] = true; happy[86] = true;
    happy[91] = true; happy[94] = true; happy[97] = true; happy[100] = true;
  }

  // Time: O(1), Space: O(1)
  public boolean isHappyMath(int n) {
    if (n <= 0) return false;
    while (n > 100)
      n = transform(n);
    return happy[n];
  }

}