Leetcode 264. Ugly NumberⅡ
程序员文章站
2022-03-07 18:13:42
...
这道题需要将前n个ugly number计算出来,计算的过程中,维护三个指针,分别对应2、3、5乘上第几个最大的ugly number时,没有超过当前ugly number最大值。
比如当前计算出了10个ugly number [1,2,3,4,5,6,8,9,10,12]
对应的第一个指针,2 * 6 <= 12,6 = array[5],因此第一个指针point1 = 5
对应的第二个指针,3 * 4 <= 12,4 = array[4],因此第一个指针point2 = 4
对应的第三个指针,5 * 2 <= 12,2 = array[5],因此第一个指针point3 = 1
当需要增加新的ugly number时,比较2 * (point1下一个数),3 * (point2下一个数),5*(point3下一个数),并将最小的加入ugly number队列中,同时更新point1, point2, point3
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
result = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
if n <= len(result):
return result[n-1]
points = [5,3,1]
mult = [2,3,5]
while n > len(result):
choice = 0
temp = result[points[0] + 1] * mult[0]
for i in range(1, 3):
while result[points[i] + 1] * mult[i] <= result[-1]:
points[i] += 1
if result[points[i] + 1] * mult[i] < temp:
temp = result[points[i] + 1] * mult[i]
choice = i
result.append(temp)
points[choice] += 1
return result[-1]
上一篇: win10出现0x80071ac3无法完成操作因为卷有问题怎么解决?
下一篇: Token的简单解释
推荐阅读
-
leetcode 136 Single Number bit Option
-
[leetcode] 306. Additive Number 解题报告
-
LeetCode_#9_回文数 Palindrome Number_C++题解
-
【LeetCode】806. Number of Lines To Write String
-
Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition (python)
-
LeetCode 1020. Number of Enclaves 解题报告(python)
-
Leetcode 1530. Number of Good Leaf Nodes Pairs (python)
-
Leetcode 200. Number of Islands (python+cpp)
-
LeetCode 1254. Number of Closed Islands解题报告(python)
-
【LeetCode】762. Prime Number of Set Bits in Binary Representation