关于Leetcode个人解题总结:LeetCode264-丑数-II-三指针-刷题打卡2

一、题目形容：

给你一个整数 n，请你找出并返回第 n 个 丑数。
丑数 就是只蕴含质因数 2、3 和 / 或 5 的正整数

二、思路剖析：

三指针

1.2,3,5 别离对应指针 i2,i3,i5, 遍历找到以后指针

2. 挪动 i 对于的以后指针，并记录后果

3. 找到数组最初一位即是第 n 个丑数

三、AC 代码：

javascript

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function (n) {
    let i2 = 0,// 2 对应的指针
        i3 = 0,// 3 对应的指针
        i5 = 0,// 5 对应的指针
        dp = [1] //dp 数组
    for (let i = 1; i < n; i++) {
        // 计算 i 对应以后那个指针
        let min = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
        // 指针别离向前挪动
        if (min === dp[i2] * 2) i2++ 
        if (min === dp[i3] * 3) i3++
        if (min === dp[i5] * 5) i5++
        dp[i] = min
    }
    return dp[dp.length - 1]
};

Python

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        i2,i3,i5,dp = 0,0,0,[1]
        for _ in range(1,n):
        # 计算 i 对应以后那个指针
            minMars = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
            # 指针别离向前挪动
            if minMars == dp[i2] * 2:
               i2 = i2+1
            if minMars == dp[i3] * 3:
               i3 = i3+1
            if minMars == dp[i5] * 5:
               i5 = i5+1
            dp.append(minMars)
        return dp[len(dp) - 1]

Typescript

function nthUglyNumber(n: number): number {
    let i2:number = 0,// 2 对应的指针
        i3:number = 0,// 3 对应的指针
        i5:number = 0,// 5 对应的指针
        dp:number[] = [1] //dp 数组
    for (let i = 1; i < n; i++) {
        // 计算 i 对应以后那个指针
        let min = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
        // 指针别离向前挪动
        if (min === dp[i2] * 2) i2++ 
        if (min === dp[i3] * 3) i3++
        if (min === dp[i5] * 5) i5++
        dp[i] = min
    }
    return dp[dp.length - 1]
};

Go

func nthUglyNumber(n int) int {dp := make([]int, n+1)
    dp[1] = 1
    i2, i3, i5 := 1, 1, 1
    for i := 2; i <= n; i++ {
        // 计算 i 对应以后那个指针
        x2, x3, x5 := dp[i2]*2, dp[i3]*3, dp[i5]*5
        dp[i] = min(min(x2, x3), x5)
        if dp[i] == x2 {i2++}
        if dp[i] == x3 {i3++}
        if dp[i] == x5 {i5++}
    }
    return dp[n]
}

// 因为 go 语言外面没有 min() 函数，本人构建一个
func min(a, b int) int {
    if a > b {return b}
    return a
}

四、总结：

1. 三指针计算以后 i 对应的丑数，记录丑数到数组，取最初面一位。持续加油！