剑指第二版/剑指Offer49.丑数.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>剑指 Offer 49. 丑数</title>
  </head>
  <body>
    <script>
      // https://leetcode-cn.com/problems/chou-shu-lcof/

      // 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
      // 提示：
      // 1 是丑数。
      // n 不超过1690。

      /**
       * @param {number} n
       * @return {number}
       */
      var nthUglyNumber = function (n) {};

      // --- answer-1 ---

      // 定义三个指针 two, three, five
      // 2 ≤ i ≤ n, dp[i] = min(dp[two]*2, dp[three]*3, dp[five]*5) 相应的指针需要+1
      var nthUglyNumber = function (n) {
        let dp = [0, 1];
        let two = 1;
        let three = 1;
        let five = 1;
        for (let i = 2; i <= n; i++) {
          let n2 = dp[two] * 2;
          let n3 = dp[three] * 3;
          let n5 = dp[five] * 5;
          dp[i] = Math.min(n2, n3, n5);
          if (dp[i] === n2) two++;
          if (dp[i] === n3) three++;
          if (dp[i] === n5) five++;
        }
        return dp[n];
      };

      // --- answer-1 ---

      // --- answer-2 ---

      // --- answer-2 ---

      var n = 10;
      var result = 12;
      // 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

      console.log('n = ', n);
      console.log('result = ', result);
      console.log('nthUglyNumber = ', nthUglyNumber(n));
    </script>
  </body>
</html>