溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了golang刷leetcode技巧之如何實現丑數，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
我們把只包含因子 2、3 和 5 的數稱作丑數（Ugly Number）。求按從小到大的順序的第 n 個丑數。
示例:
輸入: n = 10 輸出: 12 解釋: 是前 10 個丑數。
說明:
1 是丑數。
n 不超過1690。
注意：本題與主站 264 題相同：https://leetcode-cn.com/problems/ugly-number-ii/
解題思路
1，這是一個典型的動態規劃題目
2，求出n個最小的丑數 2^p2*3^p3*5^p5
3,狀態轉移方程為dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)
4,最終返回結果為dp[n-1]
代碼實現
func nthUglyNumber(n int) int {dp:=make([]int,n)dp[0]=1p2:=0p3:=0p5:=0for i:=1;i<n;i++{dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)if dp[i]==dp[p2]*2{p2++}if dp[i]==dp[p3]*3{p3++}if dp[i]==dp[p5]*5{p5++}}return dp[n-1]}func min(a,b,c int)int{if a<=b && a<=c{return a}if b<=a && b<=c{return b}return c}/*class Solution {public int nthUglyNumber(int n) {int p2=0,p3=0,p5=0;int[] dp=new int[n];dp[0]=1;for(int i=1;i<n;i++){dp[i]=Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5));if(dp[i]==dp[p2]*2) p2++;if(dp[i]==dp[p3]*3) p3++;if(dp[i]==dp[p5]*5) p5++;}return dp[n-1];}// 一個十分巧妙的動態規劃問題// 1.我們將前面求得的丑數記錄下來，后面的丑數就是前面的丑數*2，*3，*5// 2.但是問題來了，我怎么確定已知前面k-1個丑數，我怎么確定第k個丑數呢// 3.采取用三個指針的方法，p2,p3,p5// 4.index2指向的數字下一次永遠*2，p3指向的數字下一次永遠*3，p5指向的數字永遠*5// 5.我們從2*p2 3*p3 5*p5選取最小的一個數字，作為第k個丑數// 6.如果第K個丑數==2*p2，也就是說前面0-p2個丑數*2不可能產生比第K個丑數更大的丑數了，所以p2++// 7.p3,p5同理// 8.返回第n個丑數}*/
感謝你能夠認真閱讀完這篇文章，希望小編分享的“golang刷leetcode技巧之如何實現丑數”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
