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

一、题目形容：

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

二、思路剖析：

三指针

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

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

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

三、AC 代码：

javascript

<code class="js">/**
 * @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

<code class="py">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

<code class="ts">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

<code class="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对应的丑数，记录丑数到数组，取最初面一位。持续加油！

喜欢 (0)赏

[搞代码]

分享 (0)