零 标题：算法（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 ~