golang实现剑指offer：动态规划题型

丑数

LeetCode 面试题49：丑数

题目描述

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例：

输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

核心思想：

• 动态规划

• 三指针

解题思路：

• 已知丑数只包含因子 2, 3, 5，因此第N个丑数一定是 前面某个丑数 * 某个因子（2,3,5）得到

• 我们可以创建一个数组，里面的数字是排好序的丑数，里面的每一个丑数是前面的某丑数乘以2、3或者5得到的

• 定义三个指针p2,p3,p5，它们指向的数字分别只 X 2,X3,X5

• 每次基于p2，p3，p5指向的数字计算出三个丑数，取最小的minVal

• 将minVal添加进数组

func nthUglyNumber(n int) int {
    if n < 1 {
        return 1
    }
    dp := make([]int, n)
    //第一个丑数，即1
    dp[0] = 1
    //三指针初始指向数组第一个元素
    p2, p3, p5 := 0, 0, 0
    cur := 1

    for cur < n {
        //计算丑数，取最小值
        minVal := min(dp[p2]*2, dp[p3]*3, dp[p5]*5)
        dp[cur] = minVal
        // 每次谁计算出来，谁的指针就后移一位
        if minVal == dp[p2]*2 {
            p2++
        }
        if minVal == dp[p3]*3 {
            p3++
        }
        if minVal == dp[p5]*5 {
            p5++
        }
        cur++
    }
    return dp[cur-1]
}

func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }

    if b < c {
        return b
    }
    return c
}

有疑问加站长微信联系（非本文作者）