0202._hppay_number.md

Navigation

• Navigation
• Links:
• Solution 1 判断环使用HashTable
• Solution 2 判断环使用Floyd's Cycle-Finding Algorithm(快慢指针)

Links:

1. https://leetcode.com/problems/happy-number/
2. https://leetcode-cn.com/problems/happy-number/

Solution 1 判断环使用HashTable

有三种情况：

1. 最终是1
2. 最终进入一个循环
3. 一直增加，到无穷大(这种情况不可能，例如9999999999999，下一个数为1053)

算法如下：

1. 给定n，求下一个数
2. 检测是否已经出现过（成为环），利用哈希表（Python字典或者集合）

class Solution:
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        seen = set()

        while n not in seen:
            seen.add(n)
            n = self.get_next(n)

        return n == 1

    def get_next(self, n):
        total = 0
        
        while n > 0:
            n, digit = divmod(n, 10)
            total += digit ** 2
        
        return total

---

class Solution:
    def isHappy(self, n):
        seen = set()
        
        while n not in seen:
            seen.add(n)
            n = sum(int(i) ** 2 for i in str(n))
            
        return n == 1

---

Go

package main

func isHappy(n int) bool {
	seen := make(map[int]bool)

	for n != 1 && !seen[n] {
		seen[n] = true
		n = getNext(n)
	}

	return n == 1
}

func getNext(n int) int {
	next := 0

	for n != 0 {
		next += (n % 10) * (n % 10)
		n /= 10
	}

	return next
}

Solution 2 判断环使用Floyd's Cycle-Finding Algorithm(快慢指针)

class Solution:
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        slow = n
        fast = self.get_next(n)

        while fast != 1 and slow != fast:
            slow = self.get_next(slow)
            fast = self.get_next(self.get_next(fast))

        return fast == 1

    def get_next(self, n):
        total = 0
        
        while n > 0:
            n, digit = divmod(n, 10)
            total += digit ** 2
        
        return total

---

Go

func isHappy(n int) bool {
	slow, fast := n, getNext(n)

	for fast != 1 && slow != fast {
		slow = getNext(slow)
		fast = getNext(getNext(fast))
	}

	return fast == 1
}

func getNext(n int) int {
	next := 0

	for n != 0 {
		next += (n % 10) * (n % 10)
		n /= 10
	}

	return next
}