丑数：求解《263. 丑数》《剑指 Offer 49. 丑数》《264. 丑数 II》《313. 超级丑数》

什么是丑数，如何判断一个数是不是丑数，求解《263. 丑数》《剑指 Offer 49. 丑数》《264. 丑数 II》《313. 超级丑数》

丑数

质因数只包含 2 3 5 的正整数

超级丑数

质因数都出现在质数数组的正整数

例题

263. 丑数

丑数 就是只包含质因数 2、3 和 5 的正整数。 给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

答案

var isUgly = function(n) {
  if (n <= 0) return false
  for (const a of [2, 3, 5]) 
    while (n % a === 0) n /= a
  return n === 1 
};

剑指 Offer 49. 丑数

264. 丑数 II

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

答案

var nthUglyNumber = function(n) {
  const primes = [2, 3, 5], p = [0, 0, 0]
  const dp = new Uint32Array(n), m = primes.length
  dp[0] = 1
  for (let i = 1; i < n; i++) {
    let min = Number.MAX_SAFE_INTEGER, minIndexs = []
    for (let j = 0; j < m; j++) {
      const tmp = primes[j] * dp[p[j]]
      if (tmp < min) {
        min = tmp
        minIndexs = [j]
      } else if (tmp === min) minIndexs.push(j)
    }
    dp[i] = min
    for (let k = 0; k < minIndexs.length; k++) p[minIndexs[k]]++
  }
  return dp[n - 1]
};

313. 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。 给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。 题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

答案

var nthSuperUglyNumber = function(n, primes) {
  const dp = new Uint32Array(n), m = primes.length, p = new Uint32Array(m)
  dp[0] = 1
  for (let i = 1; i < n; i++) {
    let min = Number.MAX_SAFE_INTEGER, minIndexs = []
    for (let j = 0; j < m; j++) {
      const tmp = primes[j] * dp[p[j]]
      if (tmp < min) {
        min = tmp
        minIndexs = [j]
      } else if (tmp === min) minIndexs.push(j)
    }
    dp[i] = min
    for (let k = 0; k < minIndexs.length; k++) p[minIndexs[k]]++
  }
  return dp[n - 1]
};