264. 丑数 II
问题描述
给你一个整数 n ,请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。
提示:
1 <= n <= 1690
问题求解
对于每一个丑数num,都可以扩展到num * 2,num * 3,num * 5三个数字。
可以设置三个指针分别指向当前处理的数字,然后进行比较迭代即可。
快慢指针。
class Solution:
def nthUglyNumber(self, n: int) -> int:
res = [1]
i, j, k = 0, 0, 0
while len(res) < n:
n1, n2, n3 = res[i] * 2, res[j] * 3, res[k] * 5
curr = min(n1, n2, n3)
if n1 == curr: i += 1
if n2 == curr: j += 1
if n3 == curr: k += 1
res.append(curr)
return res[-1]
313. 超级丑数
问题描述
超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ,返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1:
输入:n = 12, primes = [2,7,13,19]
输出:32
解释:给定长度为 4 的质数数组 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2:
输入:n = 1, primes = [2,3,5]
输出:1
解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
提示:
1 <= n <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ,且按 递增顺序 排列
问题求解
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
res = [1]
ps = [0] * len(primes)
while len(res) < n:
record = [primes[i] * res[p] for i, p in enumerate(ps)]
curr = min(*record) if len(record) > 1 else record[0]
for i, r in enumerate(record):
if r == curr:
ps[i] += 1
res.append(curr)
return res[-1]
标签:丑数,curr,int,res,record,系列,primes
From: https://www.cnblogs.com/hyserendipity/p/16631689.html