Ugly Number

发表于 | 分类于 | |

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

解题思路

通过递归，对目标数进行取余，判断是否能被整除，以此循环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func isUgly(_ num: Int) -> Bool {
        guard num > 0 else { return false }
        if num == 1 { return true }
        else if num % 2 == 0 { return isUgly(num / 2) }
        else if num % 3 == 0 { return isUgly(num / 3) }
        else if num % 5 == 0 { return isUgly(num / 5) }
        return num == 1
    }
}

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求最小，以此类推。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    func nthUglyNumber(_ n: Int) -> Int {
        guard n > 6 else { return n }
        var uglyNums = Array(repeating: 0, count: n)
        uglyNums[0] = 1
        var f2 = 2, f3 = 3, f5 = 5
        var i2 = 0, i3 = 0, i5 = 0
        for i in 1..<n {
            let num = min(f2, f3, f5)
            uglyNums[i] = num
            if f2 == num {
                i2 += 1
                f2 = 2 * uglyNums[i2]
            }
            if f3 == num {
                i3 += 1
                f3 = 3 * uglyNums[i3]
            }
            if f5 == num {
                i5 += 1
                f5 = 5 * uglyNums[i5]
            }
        }
        return uglyNums.last!
    }
}

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数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func nthSuperUglyNumber(_ n: Int, _ primes: [Int]) -> Int {
        var uglyNums = Array(repeating: Int.max, count: n)
        var indexs = Array(repeating: 0, count: primes.count)
        uglyNums[0] = 1
        for i in 0..<n {
            for j in 0..<primes.count {
                uglyNums[i] = min(uglyNums[i], primes[j] * uglyNums[indexs[j]])
            }
            for j in 0..<primes.count {
                while primes[j] * uglyNums[indexs[j]] <= uglyNums[i] { indexs[j] += 1 }
            }
        }
        return uglyNums.last!
    }
}
0%