题解 | #丑数#

丑数

https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param index int整型 
 * @return int整型
 */
function GetUglyNumber_Solution( index ) {
    if(index <= 0) return 0;
    // 动态规划法
    // dp[n]表示第n个丑数的值为dp[n]
    // 丑数 = Math.min(已有丑数 * 质因数(2 3 5))
    const dp = [];
    dp[1] = 1;
    // 定义三个指针分别表示乘2、乘3、乘5的已有丑数下标
    let i2 = 1;
    let i3 = 1;
    let i5 = 1;
    for(let i = 2; i <= index; i++){
        let min = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5);
        // 如果当前丑数是由有序丑数序列dp中某个丑数*2得到的,则i2指针要加1,因为这个丑数已经加入序列了,以后不需要再参与比较
        if(min === dp[i2] * 2) i2++;
        if(min === dp[i3] * 3) i3++;
        if(min === dp[i5] * 5) i5++;
        dp[i] = min;
    }
    return dp[index];
}
module.exports = {
    GetUglyNumber_Solution : GetUglyNumber_Solution
};

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务