丑数

作者: youzhihua | 来源:发表于2020-01-17 17:54 被阅读0次

    题目描述

    把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    思路

    1.首先写出几个连续的丑数。
    2.我们可以很容易的推导出状态转移方程为:dp[i] = min(2dp[cnt2],3dp[cnt3],5*dp[cnt5])。

    Java代码实现

    public class Solution {
        public int GetUglyNumber_Solution(int index) {
            if(index <= 0){
                return 0;
            }
            int[] dp = new int[index+1];
            dp[1]=1;
            int ans2= 1,ans3= 1,ans5 = 1;
    
            for (int i = 2; i <= index; i++) {
                dp[i] = Math.min(dp[ans2]*2,Math.min(dp[ans3]*3,dp[ans5]*5));
    
                if(dp[i] == dp[ans2]*2){
                    ans2++;
                }
                //一定要使用if if 而不是if else if,因为可能存在 2*dp[2] = 3*dp[1] = 6 代表的是同一个值,不应该将其重复放入结果集中
                if(dp[i] == dp[ans3]*3){
                    ans3++;
                }
                
                if(dp[i] == dp[ans5]*5){
                    ans5++;
                }
            }
            
            return dp[index];
        }
    }
    

    Golang代码实现

    func nthUglyNumber(n int) int {
        if n<=0{
            return 0
        }
    
        dp := make([]int,n+1)
        dp[1] = 1
    
        ans2,ans3,ans5 := 1,1,1
    
        for i:=2;i<=n;i++ {
            min := dp[ans2]*2
            if dp[ans3]*3 < min{
                min = dp[ans3]*3
            }
            if dp[ans5]*5 < min{
                min = dp[ans5]*5
            }
            dp[i] = min
    
            if min == dp[ans2]*2{
                ans2++
            }
    
            if min == dp[ans3]*3{
                ans3++
            }
    
            if min == dp[ans5]*5{
                ans5++
            }
        }
    
        return dp[n]
    }
    

    相关文章

      网友评论

          本文标题:丑数

          本文链接:https://www.haomeiwen.com/subject/enqhzctx.html