关于leetcode:264丑数-II-算法leetcode附思维导图-全部解法300题

零 题目：算法（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 历史文章 - 总览

2 博主简介

码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专一于 一题多解、结构化思维 ，欢送一起刷穿 LeetCode ~