60 - 快乐数

题目

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

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

示例:

输入: 19 输出: true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

解答

双指针

作者：rachy 链接：https://leetcode-cn.com/problems/happy-number/solution/shi-yong-kuai-man-zhi-zhen-si-xiang-zhao-chu-xun-h/

快指针每次多算一步，如果和慢指针相遇，说明有循环，那么判断这个循环的是不是1，就行了。

func squareSum(n int) int {
    var sum int
    for n > 0 {
        bit := n % 10
        sum += bit * bit
        n /= 10
    }
    return sum
}
func isHappy(n int) bool {
    slow := n
    fast := squareSum(n)
    for slow != fast {
        slow = squareSum(slow)
        fast = squareSum(fast)
        fast = squareSum(fast)
    }
    return slow == 1
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forHappy Number.

Memory Usage: 2 MB, less than 100.00% of Go online submissions forHappy Number.

const squareSum = function (n) {
  let sum = 0
  while (n > 0) {
    sum += (n % 10) * ( n % 10)
    n = Math.floor(n / 10)
  }
  return sum
}
var isHappy = function (n) {
  let slow = n
  fast = squareSum(n)
  while (slow != fast) {
    slow = squareSum(slow)
    fast = squareSum(fast)
    fast = squareSum(fast)
  }
  return slow == 1
};

Runtime: 56 ms, faster than 93.38% of JavaScript online submissions for Happy Number.

Memory Usage: 35 MB, less than 92.31% of JavaScript online submissions for Happy Number.

在第4行计算值的时候，不用bit来装一下n%10，而是直接放到sum里面一起算，速度就会快一点点。

不过go已经100%了，所以优化了这个也看不出来

查重

作者：coder233 链接：https://leetcode-cn.com/problems/happy-number/solution/wo-yu-cheng-xian-kuai-le-qi-tian-by-coder233/

如果发现数字出现过，而且是1，就返回true，不然返回false

func isHappy(n int) bool {
    m := make(map[int]bool)
    for n != 1 {
        m[n] = true
    sum := 0
        for n != 0 {
            sum += (n % 10) * (n % 10)
            n /= 10
        }
        n = sum
        if _, ok := m[n]; ok {
            return false
        }
    }
    return true
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forHappy Number.

Memory Usage: 2.1 MB, less than 100.00% of Go online submissions for Happy Number.

go中的哈希表就是map，所以就用来记录下曾经出现的数字

var isHappy = function (n) {
  let m = new Map()
  while (n != 1) {
    m.set(n, true)
    let sum = 0
    while (n != 0) {
      sum += (n % 10) * (n % 10)
      n = Math.floor(n / 10)
    }
    n = sum
    if (m.has(n)) {
      return false
    }
  }
  return true
};

Runtime: 64 ms, faster than 64.62% of JavaScript online submissions for Happy Number.

Memory Usage: 35 MB, less than 92.31% of JavaScript online submissions for Happy Number.