欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java動(dòng)態(tài)規(guī)劃之丑數(shù)問題實(shí)例講解

 更新時(shí)間:2022年09月30日 14:29:00   作者:劉婉晴  
這篇文章主要介紹了Java動(dòng)態(tài)規(guī)劃之丑數(shù)問題實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧

問題描述:

我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)(Ugly Number)。求按從小到大的順序的第 n 個(gè)丑數(shù)。

注: 1也是丑數(shù)

思路:

我們來分析一下丑數(shù)如何得到,肯定是由前面的丑數(shù)乘2,乘3或者乘5得到,因此這是一道動(dòng)態(tài)規(guī)劃題。

  1. 使用 dp[i] 記錄第i個(gè)丑數(shù), 初始值dp[0] = 1,返回 dp[n-1]
  2. 使用 a,b,c 記錄以及 2,3,5 分別乘到了第幾個(gè)丑數(shù)
  3. 動(dòng)態(tài)規(guī)劃方程為:

dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);

如何更新a,b,c:

  • 若當(dāng)前丑數(shù)(上述最小值)為dp[a]*2,則 a++
  • 若當(dāng)前丑數(shù)(上述最小值)為dp[b]*3,則 b++
  • 若當(dāng)前丑數(shù)(上述最小值)為dp[c]*5,則 c++

圖解:

代碼:

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

變式題

題目描述:

有些數(shù)的素因子只有 3,5,7,請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找出第 k 個(gè)數(shù)。注意,不是必須有這些素因子,而是必須不包含其他的素因子。例如,前幾個(gè)數(shù)按順序應(yīng)該是 1,3,5,7,9,15,21。

思路

本題和前面的題一樣,只要把 2,3,5 改成 3,5,7即可 代碼

class Solution {
    public int getKthMagicNumber(int k) {
        int a=0, b=0, c=0;
        int[] dp = new int[k];
        dp[0] = 1;
        for(int i=1; i<k; i++){
            int n1 = dp[a]*3;
            int n2 = dp[b]*5;
            int n3 = dp[c]*7;
            dp[i] = Math.min(Math.min(n1, n2), n3);
            if(dp[i] == n1){ a++; }
            if(dp[i] == n2){ b++; }
            if(dp[i] == n3){ c++; }
        }
        return dp[k-1];
    }
}

到此這篇關(guān)于Java動(dòng)態(tài)規(guī)劃之丑數(shù)問題實(shí)例講解的文章就介紹到這了,更多相關(guān)Java丑數(shù)問題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論