-
Notifications
You must be signed in to change notification settings - Fork 4
/
丑数.py
65 lines (58 loc) · 1.82 KB
/
丑数.py
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
"""
class Solution:
def GetUglyNumber_Solution(self, index):
if index < 1:
return None
#### 死循环,找丑数
#### 判断一个数是不是丑数,先循环除以2,直到不能整除
#### 循环除以3,直到不能整除,循环除以5,直到不能整除
#### 这是如果剩余的值是1,我们就说它是丑数
#### 其他情况都不是丑数
count = 0
def isUglyNumber(num):
while num % 2 == 0:
num = num // 2
while num % 3 == 0:
num = num // 3
while num % 5 == 0:
num = num // 5
if num == 1:
return True
else:
return False
num = 1
while True:
if isUglyNumber(num):
count += 1
if count == index:
return num
num += 1
if __name__ == '__main__':
s = Solution()
ans = s.GetUglyNumber_Solution(17)
print(ans)
"""
class Solution:
def GetUglyNumber_Solution(self, index):
if index < 1:
return 0
uglyList = [1]
count = 1
twoPointer = 0
threePointer = 0
fivePointer = 0
while count != index:
minValue = min( 2 * uglyList[twoPointer], 3 * uglyList[threePointer], 5 * uglyList[fivePointer])
uglyList.append(minValue)
count += 1
if minValue == 2 * uglyList[twoPointer]:
twoPointer += 1
if minValue == 3 * uglyList[threePointer]:
threePointer += 1
if minValue == 5 * uglyList[fivePointer]:
fivePointer += 1
return uglyList[count - 1]
if __name__ == '__main__':
s = Solution()
ans = s.GetUglyNumber_Solution(4)
print(ans)