题目:编写一个算法来判断一个数 n 是不是高兴数。
「高兴数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个地位上的数字的平方和。
- 而后反复这个过程直到这个数变为 1,也可能是 有限循环 但始终变不到 1。
- 如果这个过程 后果为 1,那么这个数就是高兴数。
如果 n 是 高兴数 就返回 true ;不是,则返回 false 。
链接: 力扣Leetcode—中级算法—数学—高兴数.
示例 1:
输出:n = 19
输入:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输出:n = 2
输入:false
标签:哈希表、数学、双指针
思路:一开始大家都会思考一个问题,如果始终没有失去1会陷入循环。为了解决这个问题,咱们能够用快慢指针,检测是否存在循环,如果快指针追上慢指针还没呈现1,证实不是高兴数;反之亦然
全副Go代码如下:
package mainimport "fmt"func isHappy(n int) bool { // 如果始终没有失去1会陷入循环,所以咱们用快慢指针,检测是否存在循环,如果快指针等于慢指针还没呈现1,证实不是高兴数;反之亦然 slow := n fast := next(n) for fast != 1 && fast != slow { slow = next(slow) fast = next(next(fast)) } if fast == 1 { return true } return false}// 上一个数的和的数其每个地位上的数字的平方和func next(n int) int { sum := 0 for n != 0 { pop := n % 10 sum += pop * pop n /= 10 } return sum}func main() { fmt.Println(isHappy(19))}
提交截图: