六十六、丑数系列，丑的颠覆我的思想
「@Author：Runsen」
@Date:2020/9/28
❝编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」 ❞
取一粒跳跃的文字，镶进九月的诗篇，无论是水榭的一角，还是月下的花园，只要有岁月的空格，就能拼接出精美的图案。
纯数学家哈代说，美是检验数学的第一标准，丑数学尾巴长不了。（Beauty is the first test: there is no permanent place in the world for ugly mathematics.）
我说的丑是丑数，不要以为我很丑，而且我也觉得我很丑。丑数算法题，我在阿里的题目中看见过。阿里面试曾考过此丑数，大家务必重视此丑数。
丑数
我们把只包含因子2,3,5的数称作丑数，求按从小到大的顺序，第1500个丑数。习惯上把1当作第一个丑数。
「Talk is cheap ,show me my code !」
Leetcode 263：判断给定的数是否为丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。小于1的不是丑数，1是丑数，2、3、4、5都是丑数。
此题是简单题：一个思路是递归，一个思路就是直接暴力。
第一步：只要num大于5（2,3,5中5最大）就继续循环。
第二步：只要num不能整除其中三个数任意一个，就返回False。
第三步：继续除以可以整除的循环。
备注：这里需要注意的是题目中“1”是返回True。
该题难点在于判断2，3，5是否为因数，都要进行相应的判断，且1到6为特殊的丑数不能忽略。若给定的整数过大不容易计算时，可对其进行多次相除，例如：在用2，3，5其中一个数当做除数进行一次或多次相除后，将得到的商再次进行以上操作，直到最简为止。
# 递归的做法
class Solution:
def isUgly(self, num: int) -> bool:
if num <= 0:
return False
elif num <=6 :
return True
if num % 2 == 0:
return self.isUgly(num / 2)
if num % 3 == 0:
return self.isUgly(num / 3)
if num % 5 == 0:
return self.isUgly(num / 5)
return False
# while循环暴力破解
class Solution:
def isUgly(self, num: int) -> bool:
if num <= 0:
return False
while num >= 5:
if num % 2 != 0 and num % 3 != 0 and num % 5 != 0:
return False
else:
if num % 2 == 0:
num = num // 2
elif num % 3 == 0:
num = num // 3
else:
num = num //5
return True
Leetcode 264：找出第 n 个丑数
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
此题是一个我想不到的dp（动态规划）+三指针以后细聊。
想一想丑数肯定是一个来源2，3，5 其中一个倍数，在第一个丑数处建立三个索引，分别代表质因子2、质因子3、质因子5；
找出2 * 丑数数组[质因子2索引]、3 * 丑数数组[质因子3索引]、5 * 丑数数组[质因子5索引]中的最小值，并将该丑数对应的因子指针往前走一步。重复该步骤直到计算完 。对应的dp状态转移方程：ugly = min(res[i2] * 2, res[i3] * 3, res[i5] * 5)
因为丑数是只包含2，3，5 的因子，所以丑数一定是之前的丑数乘 2，3，5得到的，所以如果我们能够保存之前出现的丑数，让它乘 2，3，5 即可得到三个丑数，我们取最小的那个，即是最新的丑数，
class Solution:
def nthUglyNumber(self, n: int) -> int:
# 还要一个最小堆的解决方法，需要 import heapq
# res = [1]*(n)
# minheap = [2,3,5]
# for i in range(1,n):
# minheap = sorted(set(minheap))
# res[i] = minheap.pop(0)
# minheap.append(res[i]*2)
# minheap.append(res[i]*3)
# minheap.append(res[i]*5)
# return res[-1]
res = [1]
# 三指针
i2 = i3 = i5 = 0
for _ in range(1,n):
ugly = min(res[i2] * 2, res[i3] * 3, res[i5] * 5)
res.append(ugly)
if ugly == res[i2] * 2:
i2 +=1
if ugly == res[i3] * 3:
i3 +=1
if ugly == res[i5] * 5:
i5 +=1
return res[-1]
Leetcode 313：超级丑数
写一个程序来找第 n 个超级丑数。
超级丑数的定义是正整数并且所有的质数因子都在所给定的一个的质数集合内。
超级丑数与找出第 n 个丑数不同的地方在于primes质因数不同。
方法和上面三指针的dp完全一样。我们在寻找新的超级丑数的时候，只需要遍历寻找质因数，并选择数组中最小的一个数来作为这个新的超级丑数就好了。
示例:
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。
其实没什么难度，算法的小逻辑做了一些调整，上面三指针代码变成N指针的代码，但是算法的思路并没有改变。
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
nums = [0 for _ in range(len(primes))]
result = [1]
for i in range(1,n):
ugly = min(result[nums[j]] * primes[j] for j in range(len(nums)))
result.append(ugly)
for k in range(len(nums)):
if ugly == result[nums[k]] * primes[k]:
nums[k] +=1
return result[-1]
人生的路，一步都不能少，你有多努力多拼命，心里最清楚。如果你还不能体会，那也没有关系，生活会让你在无数次跌倒中明白，你所有或潦草或努力走过的路，其实都有迹可循。
「还好，时光尚早。努力，总有出路。我还是那个少年！」
❝本文已收录 GitHub，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。 ❞
Reference
[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -
腾讯云开发者
