题解 | #丑数#
丑数
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 };