关于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 ~