-
Notifications
You must be signed in to change notification settings - Fork 6
/
202_HappyNumber.swift
76 lines (68 loc) · 1.68 KB
/
202_HappyNumber.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//
// 202. 快乐数
//
// 编写一个算法来判断一个数 n 是不是快乐数。
//
// 题目链接:https://leetcode-cn.com/problems/happy-number/
// 标签:哈希表、快慢指针、数学
// 要点:哈希表检测循环、数学规律
// 时间复杂度:O(log(N))
// 空间复杂度:
// * 哈希表:O(log(N))
// * 快慢指针: O(1)
// * 数学: O(1)
//
class Solution {
var numSet: Set<Int> = []
func isHappy(_ n: Int) -> Bool {
var num = n
var next = 0
while num >= 1 {
next += Int(pow(Double(num % 10), 2))
num /= 10
}
if next == 1 { return true }
if numSet.contains(next) { return false }
numSet.insert(next)
return isHappy(next)
}
}
class SolutionBy2Points {
func isHappy(_ n: Int) -> Bool {
var slow = n
var fast = _getNext(n)
while fast != 1 && slow != fast {
slow = _getNext(slow)
fast = _getNext(_getNext(fast))
}
return fast == 1
}
private func _getNext(_ n: Int) -> Int {
var num = n
var next = 0
while num >= 1 {
next += Int(pow(Double(num % 10), 2))
num /= 10
}
return next
}
}
class SolutionByMath {
func isHappy(_ n: Int) -> Bool {
var num = n
var next = 0
while num >= 1 {
next += Int(pow(Double(num % 10), 2))
num /= 10
}
if next == 1 { return true }
return next == 4 ? false : isHappy(next)
}
}
// Tests
let s = Solution()
s.isHappy(19) == true
let s2 = SolutionBy2Points()
s2.isHappy(19) == true
let s3 = SolutionByMath()
s3.isHappy(19) == true