Shulou(Shulou.com)06/01 Report--

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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.