Happy Number

• Easy
• keyword: Pattern, Math
• 类似: Happy Number, Count Digit, Add Digits, Next/Prev Permutation Index

• 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, and 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 numbers.
• Example: 19 is a happy number: $$1^2 + 9^2 = 82$$; $$8^2 + 2^2 = 68$$; $$6^2 + 8^2 = 100$$; $$1^2 + 0^2 + 0^2 = 1$$;

idea 1: 找规律

• 这个和Add digit很类似, 不过add digit是各个位加起来的循环, 这里是各个为的平方加起来. 有类似add digit的规律吗?
• 于是我尝试计算了0~9的平方的nextHappyNumber:

  1 : 1
  2 : 4 -> ... -> 4
  3 : 9 -> ... -> 4
  4 : 4 -> ... -> 4
  5 : 25 -> ... -> 4
  6 : 4 -> ... -> 4
  7 : 49 -> ... -> 1
  8 : 4 -> ... -> 4
  9 : 25 -> ... -> 4
  

• 所以只有1/7能得到1, 其他都会进入4的循环. 但是这个规律有什么用? Happy Number是各位数字的平方和. 例如19虽然2个数都会进入4的循环, 但是加起来就是happy的.

idea 2: 暴力解

• 既然所有数的平方和都会进入循环, 那就看循环的时候值是否为1即可.
• 代码如下:

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

  public boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    while (!set.contains(n)) {
      set.add(n);
      n = getNext(n);
      if (n == 1)  return true;
    }
    return false;
  }

idea 3: 循环---联想--->cycle detect--->Graph/LinkkedList--->快慢指针

• 这里和计算matrix里面最大的1组成的矩形面积类似, 或者Closet pair from 2 sorted array, 都是通过在做Leetcode题目的时候学会的算法来解决其他Leetcode问题.
• 这里通过联想: 循环---联想--->cycle detect--->Graph/LinkkedList--->快慢指针. 类似于word ladder/Alien Dictionary: 即题目没有明说是Graph/LinkedList, 但却可以通过想象或者处理成Graph/Linkedlist. 从而使用Graph/List的算法解决. 这里想象成list, 然后用九章的list cycle detect.
• 代码如下

public boolean isHappyCycle(int n) {
    int slow, fast;
    slow = n;
    fast = getNext(n);
    while (slow != fast) {
      slow = getNext(slow);
      fast = getNext(fast);
      fast = getNext(fast);
    }
    return slow == 1;
}

• discuss里面有人说了这个叫: Floyd Cycle Detection Algs. 有点点区别, 他是slow/fast都指向头结点, 但是while的时候是先做一步, 即使用的do...while.