质因数只包含 2
3
5
的正整数
质因数都出现在质数数组的正整数
丑数 就是只包含质因数 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
};
给你一个整数 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]
};
超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 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]
};