Java動(dòng)態(tài)規(guī)劃之丑數(shù)問(wèn)題實(shí)例講解
問(wèn)題描述:
我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱(chēng)作丑數(shù)(Ugly Number)。求按從小到大的順序的第 n 個(gè)丑數(shù)。
注: 1也是丑數(shù)
思路:
我們來(lái)分析一下丑數(shù)如何得到,肯定是由前面的丑數(shù)乘2,乘3或者乘5得到,因此這是一道動(dòng)態(tài)規(guī)劃題。
- 使用 dp[i] 記錄第i個(gè)丑數(shù), 初始值dp[0] = 1,返回 dp[n-1]
- 使用 a,b,c 記錄以及 2,3,5 分別乘到了第幾個(gè)丑數(shù)
- 動(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ù)問(wèn)題實(shí)例講解的文章就介紹到這了,更多相關(guān)Java丑數(shù)問(wèn)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Java通過(guò)動(dòng)態(tài)規(guī)劃設(shè)計(jì)股票買(mǎi)賣(mài)最佳時(shí)機(jī)
- Java動(dòng)態(tài)規(guī)劃之硬幣找零問(wèn)題實(shí)現(xiàn)示例
- Java使用動(dòng)態(tài)規(guī)劃算法思想解決背包問(wèn)題
- Java數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)詳解
- 在Java中實(shí)現(xiàn)二叉搜索樹(shù)的全過(guò)程記錄
- Java數(shù)據(jù)結(jié)構(gòu)超詳細(xì)分析二叉搜索樹(shù)
- Java動(dòng)態(tài)規(guī)劃方式解決不同的二叉搜索樹(shù)
相關(guān)文章
深入解析Java的設(shè)計(jì)模式編程中建造者模式的運(yùn)用
這篇文章主要介紹了深入解析Java的設(shè)計(jì)模式編程中建造者模式的運(yùn)用,同時(shí)文中也介紹了建造者模式與工廠模式的區(qū)別,需要的朋友可以參考下2016-02-02springmvc中進(jìn)行數(shù)據(jù)保存以及日期參數(shù)的保存過(guò)程解析
這篇文章主要介紹了springmvc中進(jìn)行數(shù)據(jù)保存以及日期參數(shù)的保存過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09SpringBoot中的Condition包下常用條件依賴注解案例介紹
這篇文章主要介紹了SpringBoot中的Condition包下常用條件依賴注解案例,文章基于Java的相關(guān)資料展開(kāi)主題詳細(xì)內(nèi)容,需要的小伙伴可以參考一下2022-04-04Netty + ZooKeeper 實(shí)現(xiàn)簡(jiǎn)單的服務(wù)注冊(cè)與發(fā)現(xiàn)
服務(wù)注冊(cè)和發(fā)現(xiàn)一直是分布式的核心組件。本文介紹了借助 ZooKeeper 做注冊(cè)中心,如何實(shí)現(xiàn)一個(gè)簡(jiǎn)單的服務(wù)注冊(cè)和發(fā)現(xiàn)。,需要的朋友可以參考下2019-06-06springboot集成開(kāi)發(fā)實(shí)現(xiàn)商場(chǎng)秒殺功能
這篇文章主要介紹了springboot集成實(shí)現(xiàn)商品秒殺功能,秒殺系統(tǒng)業(yè)務(wù)流程,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-12-12