零 标题：算法（leetcode，附思维导图 + 全部解法）300题之（264）丑数 II
一 题目描述
题目描述
二 解法总览（思维导图）
思维导图
三 全部解法
1 方案1
1)代码：
// 方案1：“自己。三指针法”。
// 想法：
// 因为每个数字都要被计算三次，一次是乘以2，一次是乘以3，一次是乘以5，
// 所以定义三个指针 —— index_2、index_3、index_5。
// 这三个指针的起点是一样的，都是0，
// 如果当前的数字是乘以2得到的，就将 index_2 向后移动，
// 如果当前的是乘以3得到的，就将 index_3 向后移动，
// 如果当前的是乘以5得到的，就将 index_5 向后移动。
// 思路：
// 1）状态初始化：resList = [1], index_2 = 0, index_3 = 0, index_5 = 0; 。
// 2）核心：循环处理，条件为 resList.length < n 。
// 2.1）求得下一个丑数 temp = Math.min(resList[index_2] * 2, resList[index_3] * 3, resList[index_5] * 5) 。
// 2.2）看当前丑数是乘哪个数得到的，那么对应的指针就向后移动。
// 2.3）将当前丑数塞到 数组 resList 里。
// 3）返回结果 resList[n-1] 。
var nthUglyNumber = function(n) {
// 1）状态初始化：resList = [1], index_2 = 0, index_3 = 0, index_5 = 0; 。
let resList = [1],
index_2 = 0,
index_3 = 0,
index_5 = 0;
// 2）核心：循环处理，条件为 resList.length < n 。
while(resList.length < n){
// 2.1）求得下一个丑数 temp = Math.min(resList[index_2] * 2, resList[index_3] * 3, resList[index_5] * 5) 。
let temp = Math.min(resList[index_2] * 2, resList[index_3] * 3, resList[index_5] * 5);
// 可以用 switch 代替 3个if语句、显得逼格高。不知道为啥行不通 很奇怪！！
// switch(temp){
// case resList[index_2] * 2:
// index_2++;
// break;
// case resList[index_3] * 3:
// index_3++;
// break;
// case resList[index_5] * 5:
// index_5++;
// break;
// }
// 2.2）看当前丑数是乘哪个数得到的，那么对应的指针就向后移动。
if(temp === resList[index_2] * 2){
index_2++;
}
if(temp === resList[index_3] * 3){
index_3++;
}
if(temp === resList[index_5] * 5){
index_5++;
}
// 2.3）将当前丑数塞到 数组 resList 里。
resList.push(temp);
}
// 3）返回结果 resList[n-1] 。
return resList[n-1];
};
2 方案2
1)代码：
// 方案2 “官方。最小堆法”。
// 参考：
// 1）https://leetcode.cn/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/
// 思路：
// 1）初始化：factors = [2, 3, 5];
// set = new Set(), heap = new MinHeap(), ugly = 1; set.add(1); heap.insert(1); 。
// 2）核心：循环 n - 1次，每次都从最小堆的顶堆中取值。
// 3）返回结果 ugly 。
// 最小堆
// TODO：重新手撕。
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return i * 2 + 1;
}
getRightIndex(i) {
return i * 2 + 2;
}
shiftUp(index) {
if(index === 0) {
return;
}
const parentIndex = this.getParentIndex(index);
if(this.heap[parentIndex] > this.heap[index]){
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1]= this.heap[i2];
this.heap[i2] = temp;
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
return this.heap[0];
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] < this.heap[index]){
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
var nthUglyNumber = function(n) {
// 1）初始化：factors = [2, 3, 5];
// set = new Set(), heap = new MinHeap(), ugly = 1; set.add(1); heap.insert(1); 。
const factors = [2, 3, 5];
let set = new Set(),
heap = new MinHeap(),
ugly = 1;
set.add(1);
heap.insert(1);
// 2）核心：循环 n - 1次，每次都从最小堆的顶堆中取值。
for (let i = 0; i < n; i++) {
ugly = heap.pop();
for (const factor of factors) {
const next = ugly * factor;
if (!set.has(next)) {
set.add(next);
heap.insert(next);
}
}
}
// 3）返回结果 ugly 。
return ugly;
};
四 资源分享 & 更多
1 历史文章 - 总览
刷题进度 - LeetCode：561 / 2695 、《剑指offer》：66 / 66
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 LeetCode ~
网友评论