【lc刷题】263264 丑数丑数 II

【lc刷题】263/264 丑数/丑数 II

116-117

2道题：

• 丑数
• 丑数 II

2道题：

丑数

263. 丑数
     编写一个程序判断给定的数是否为丑数。
      
     丑数就是只包含质因数 2, 3, 5 的正整数。
      
     示例 1:
      
     输入: 6
     输出: true
     解释: 6 = 2 × 3
      
     示例 2:
     输入: 8
     输出: true
     解释: 8 = 2 × 2 × 2
      
     示例 3:
     输入: 14
     输出: false
     解释: 14 不是丑数，因为它包含了另外一个质因数 7。
      
     说明：
      
     1 是丑数。
     输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。

百度：
丑数描述 ：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。
习惯上我们把1当做是第一个丑数。 前20个丑数为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18,
20, 24, 25, 27, 30, 32, 36。
判断方法：
首先除2，直到不能整除为止，然后除5到不能整除为止，然后除3直到不能整除为止。最终判断剩余的数字是否为1，如果是1则为丑数，否则不是丑数。

class Solution:def isUgly(self, num: int) -> bool:if num == 0: return Falsedef helper(num,k): while num%k == 0: num /= kreturn numnum = helper(num, 2)num = helper(num, 5)num = helper(num, 3)return num == 1

优化：

class Solution:def isUgly(self, num: int) -> bool:for k in 2, 3, 5:while num > 0 == num % k: num /= kreturn num == 1     

丑数 II

264. 丑数 II
      
     编写一个程序，找出第 n 个丑数。
      
     丑数就是只包含质因数 2, 3, 5 的正整数。
      
     示例:
      
     输入: n = 10
     输出: 12
     解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
     说明:
      
     1 是丑数。
     n 不超过1690。

上一题是给个数，看是否是丑数，这道题是自己把所有丑数算出来。

思路：三个指针
[1], *2，*3，*5
min(1*2，1*3，1*5) = 2 加入2
2用过了，但凡乘积==2的指针作废，以此类推

如图：

class Solution(object):def nthUglyNumber(self, n: int) -> int:res = [1]i2, i3, i5 = 0, 0, 0while len(res) < n:res.append(min(res[i2]*2,res[i3]*3,res[i5]*5))if res[-1] == res[i2]*2: i2 += 1if res[-1] == res[i3]*3: i3 += 1if res[-1] == res[i5]*5: i5 += 1return res[-1]