263-丑数

LeetCode 263. Ugly Number

LeetCode-263

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: n = 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

method

如果满足条件，除完2或3或5之后应该等于1

bool isUgly(int n) {
    for (int i = 2; i <= 5 && n; i++) {  // 4用前面的2处理了
        while (n % i == 0) n /= i;  // 这里要用while 
    }
    return n == 1;
}

---

LeetCode 264. Ugly Number II

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

method: 动态规划

dp[i]：表示第i+1个丑数

三个指针：

• a表示前a个数都是通过乘以2获得的丑数
• b表示前b个数都是通过乘以3获得的丑数
• c表示前c个数都是通过乘以5获得的丑数

现在要算第i个数，它应该是第a个数乘以2，第b个数乘以3，第c个数乘以5，这三种情况中的最小值

同时，如果确定第i个丑数是由第a个数乘以2获得的，那么a就要递增，同理，如果是由第b个数乘以3获得的，b就要递增，如果同时满足是由a乘以2获得的，也是由b乘以3获得的，那a和b都要递增，c同理

int nthUglyNumber(int n) {
    int a = 0, b = 0, c = 0;
    vector<int> dp(n);
    dp[0] = 1;
    for (int i = 1; i < n; i++) {
        int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
        dp[i] = min(min(n2, n3), n5);
        if (dp[i] == n2) a++;  
        if (dp[i] == n3) b++;  
        if (dp[i] == n5) c++;  
    }
    return dp[n - 1];
}