Python每日一练(20230507) 丑数I\II\III、超级丑数

目录

1. 丑数 Ugly Number I

2. 丑数 Ugly Number II

3. 丑数 Ugly Number III

4. 超级丑数 Super Ugly Number

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

1. 丑数 Ugly Number I

丑数 就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

提示：

• -2^31 <= n <= 2^31 - 1

代码：

class Solution:def isUgly(self, n: int) -> bool:if n <= 0:return Falsefor i in [2, 3, 5]:while n % i == 0:n //= ireturn n == 1# %%
s = Solution()
print(s.isUgly(6))
print(s.isUgly(1))
print(s.isUgly(14))for i in range(1,21):s = Solution()if s.isUgly(i):print(i, end=" ")

递归写法：

class Solution:def isUgly(self, n: int) -> bool:if n <= 0:return Falseelif n == 1:return Trueelif n % 2 == 0:return self.isUgly(n // 2)elif n % 3 == 0:return self.isUgly(n // 3)elif n % 5 == 0:return self.isUgly(n // 5)else:return False
# %%
s = Solution()
print(s.isUgly(6))
print(s.isUgly(1))
print(s.isUgly(14))for i in range(1,21):s = Solution()if s.isUgly(i):print(i, end=" ")

输出：

True
True
False
1 2 3 4 5 6 8 9 10 12 15 16 18 20 

---

2. 丑数 Ugly Number 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

代码：

class Solution:def nthUglyNumber(self, n: int) -> int:nums = [1]p_2, p_3, p_5 = 0, 0, 0for i in range(1, n):nums.append(min(nums[p_2]*2, nums[p_3]*3, nums[p_5]*5))if nums[-1] == nums[p_2]*2:p_2 += 1if nums[-1] == nums[p_3]*3:p_3 += 1if nums[-1] == nums[p_5]*5:p_5 += 1return nums[-1]# %%
s = Solution()
print(s.nthUglyNumber(10))
print(s.nthUglyNumber(1))for i in range(1,15):print(s.nthUglyNumber(i), end=" ")

 调用上题函数：

class Solution:def isUgly(self, n: int) -> bool:if n <= 0:return Falsefor i in [2, 3, 5]:while n % i == 0:n //= ireturn n == 1def nthUglyNumber(self, n: int) -> int:count = 0i = 1while count < n:if self.isUgly(i):count += 1if count == n:return ii += 1return -1# %%
s = Solution()
print(s.nthUglyNumber(10))
print(s.nthUglyNumber(1))for i in range(1,15):print(s.nthUglyNumber(i), end=" ")

输出：

12
1
1 2 3 4 5 6 8 9 10 12 15 16 18 20 

---

3. 丑数 Ugly Number III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

示例 4：

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984

提示：

• 1 <= n, a, b, c <= 10^9
• 1 <= a * b * c <= 10^18
• 本题结果在 [1, 2 * 10^9] 的范围内

代码： 二分查找

class Solution:def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:def gcd(x, y):return x if y == 0 else gcd(y, x % y)def lcm(x, y):return x // gcd(x, y) * yleft, right = 1, 2 * 10**9ab_lcm, ac_lcm, bc_lcm, abc_lcm = lcm(a, b), lcm(a, c), lcm(b, c), lcm(lcm(a, b), c)while left < right:mid = left + (right - left) // 2cnt = mid // a + mid // b + mid // c - mid // ab_lcm - mid // ac_lcm - mid // bc_lcm + mid // abc_lcmif cnt < n:left = mid + 1else:right = midreturn left# %%
s = Solution()
print(s.nthUglyNumber(n = 3, a = 2, b = 3, c = 5))
print(s.nthUglyNumber(n = 4, a = 2, b = 3, c = 4))
print(s.nthUglyNumber(n = 5, a = 2, b = 11, c = 13))print(s.nthUglyNumber(n = 1000000000, a = 2, b = 217983653, c = 336916467))

输出：

4
6
10
1999999984

---

4. 超级丑数 Super Ugly Number

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 <= 10^6
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• 题目数据 保证 primes[i] 是一个质数
• primes 中的所有值都 互不相同 ，且按 递增顺序 排列

代码：

from typing import List
class Solution:def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:dp = [1] * nk = len(primes)pointers = [0] * kfor i in range(1, n):choices = [dp[pointers[j]] * primes[j] for j in range(k)]dp[i] = min(choices)for j in range(k):if dp[pointers[j]] * primes[j] == dp[i]:pointers[j] += 1return dp[-1]# %%
s = Solution()
print(s.nthSuperUglyNumber(n = 12, primes = [2,7,13,19]))
print(s.nthSuperUglyNumber(n = 1, primes = [2,3,5]))

输出：

32
1

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏