剑指 offer 动态规划算法题：丑数-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指 offer 动态规划算法题：丑数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

分析：

枚举法，从 1 开始判断遍历，判断是否丑数（只有 2， 3， 5 作为因子），若是丑数 n 自减，直到 n 等于 1，返回即可。

动态规划法，定义数组dp，其中 dp[i - 1] 表示第 i 个丑数，第 nn 个丑数即为 dp[n]。由于最小的丑数是 1，因此 dp[0]=1。然后定义三个指针 p2,p3,p5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 0。当 1≤ i ≤ n-1 时，令 dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，然后分别比较 dp[i] 和 dp[p2]×2,dp[p3]×3,dp[p5]×5 是否相等，如果相等则将对应的指针加 1。最终 dp[n - 1]即是第 n 个丑数。

求解：文章来源地址https://www.toymoban.com/news/detail-563384.html

// 枚举法
function nthUglyNumber1(n: number): number {
  if (n <= 0) return 0;
  function isUglyNumber(num: number): boolean {
    while (num % 2 === 0) {
      num /= 2;
    }
    while (num % 3 === 0) {
      num /= 3;
    }
    while (num % 5 === 0) {
      num /= 5;
    }
    return num === 1;
  }
  let num = 1;
  while (true) {
    if (isUglyNumber(num) && n === 1) {
      n = n - 1;
      break;
    }
    num = num + 1;
  }
  return num;
}

// 动态规划法
function nthUglyNumber2(n: number): number {
  if (n <= 0) return 0;
  const dp = new Array(n).fill(0);
  dp[0] = 1; // 第一个丑数是 1
  let factor2 = 0;
  let factor3 = 0;
  let factor5 = 0;
  for (let i = 1; i < n; i++) {
    const num2 = dp[factor2] * 2;
    const num3 = dp[factor3] * 3;
    const num5 = dp[factor5] * 5;
    dp[i] = Math.min(num2, num3, num5);
    // 选取 2、3、5 其中的那个因子下标加 1
    if (dp[i] === num2) {
      factor2 = factor2 + 1;
    }
    if (dp[i] === num3) {
      factor3 = factor3 + 1;
    }
    if (dp[i] === num2) {
      factor5 = factor5 + 1;
    }
  }
  return dp[n - 1];
}

到了这里，关于剑指 offer 动态规划算法题：丑数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！