How to realize the ugly number in the skill of golang browsing leetcode

This article mainly introduces how to realize the ugly number of golang brush leetcode skills. It has certain reference value. Interested friends can refer to it. I hope you will have a lot of gains after reading this article. Let Xiaobian take you to understand it together.

We call numbers containing only factors 2, 3, and 5 ugly numbers. Find the nth ugly number in descending order.

Examples:

Input: n = 10 Output: 12 Interpretation: is the first 10 ugly numbers.

Description:

1 is ugly.

N does not exceed 1690.

Note: This question is the same as Question 264 of the main station: leetcode-cn.com/problems/ugly-number-ii/

problem-solving ideas

This is a typical dynamic programming problem.

2, find the n smallest ugly numbers 2^p2*3^p3*5^p5

3, the state transition equation is dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)

4, the final return result is dp[n-1]

code implementation

func nthUglyNumber(n int) int { dp:=make([]int,n) dp[0]=1 p2:=0 p3:=0 p5:=0 for i:=1;i