当前位置：网站首页>Leetcode skimming -- bit by bit record 023

Leetcode skimming -- bit by bit record 023

2022-07-23 10:44:00 【Robust least squares support vector machine】

23. The finger of the sword Offer 49. Ugly number

requirement

We will include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. Seek the order from small to large n Ugly number .

Ideas

Recurrence properties of ugly numbers ： Ugly numbers contain only factors 2, 3, 5 , So there is “ Ugly number = Some clown number × Some factor ”
Dynamic programming ：

State definition ： Set up a dynamic programming list dp,dp[i] On behalf of the i + 1 Ugly number
Transfer equation ：
When indexing a, b, c When the following conditions are met , dp[i] Is the minimum of three cases ;
Calculation per round dp[i] after , Need to update index a, b, c Value , Make it always meet the conditions of the equation . Implementation method ： Judge independently dp[i] and dp[a]×2 , dp[b]×3 , dp[c]×5 The size of the relationship , If equal, the corresponding index a , b, c Add 1
The initial state ： dp[0] = 1 , That is, the first ugly number is 1
Return value ： dp[n-1] , That is, return to the second page n Ugly number

Problem solving

#include <iostream>
using namespace std;
#include <vector>

class Solution {
    
public:
    int nthUglyNumber(int n) {
    
        int a = 0, b = 0, c = 0;
        vector<int> dp(n + 1);
        dp[0] = 1;                 //  The initial state 
        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);   //  Minimum value of three cases 
            if (dp[i] == n2) 
                a++;
            if (dp[i] == n3) 
                b++;
            if (dp[i] == n5) 
                c++;
        }
        return dp[n - 1];  //  Back to page  n  Ugly number 
    }
};


void test01()
{
    
    Solution solution;
    int n = 10;
    cout << solution.nthUglyNumber(n) << endl;
}

int main()
{
    
    test01();

    system("pause");
    return 0;
}