263. Ugly Number
题目描述
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note that 1 is typically treated as an ugly number.
题目大意
丑陋数即由主要因子 2、3、5
相乘得到,1
为特殊的丑陋数。例如:6和8是丑陋数,而14不是,因为丑陋因子不包括 7
解题思路
通过递归,对目标数进行取余,判断是否能被整除,以此循环。
代码
|
|
264. Ugly Number II
题目描述
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
题目大意
例如 1、2、3、4、5、6、8、9、10、12
。按照大小排列,求 n-th 丑陋数。
解题思路
从上述的例子可以看出 丑陋数由下列数组成
2 1, 2 2, 2 3, 2 4…..
3 1, 3 2, 3 3, 3 4…..
5 1, 5 2, 5 3, 5 4…..
就是在每一列求最小,例如第一次2 3 5
中2
是最小,则第二次就变成4 3 5
求最小,以此类推。
代码
|
|
313. Super Ugly Number
题目描述
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
题目大意
实际上是 Ugly Number II
的变形,丑陋因子不固定,由 primes
参数提供。
解题思路
实现思路与
Ugly Number II
一致,只是把2 3 5
变成了primes
数组。
代码
|
|