[数据结构与算法]leetcode264. 丑数 II(java & python)

不懂丑数的概念 尴尬

java:

class Solution {
    public int nthUglyNumber(int n) {
        int dp[] = new int[n];
        dp[0] = 1;
        int a = 0, b = 0, c = 0;

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

python3:

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp, a, b, c = [1] * n, 0, 0, 0
        for i in range(1,n):
            n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
            dp[i] = min(n2, n3, n5)
            if n2 == dp[i] : 
                a += 1
            if n3 == dp[i] :
                b += 1
            if n5 == dp[i] :
                c += 1
        return dp[-1]