264、丑数 II | 算法(附思维导图+全部解法)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 历史文章 - 总览

文章名称 解法 阅读量
1. 两数之和(Two Sum) 共 3 种 2.7 k+
2. 两数相加 (Add Two Numbers) 共 4 种 2.7 k+
3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) 共 3 种 2.6 k+
4. 寻找两个正序数组的中位数(Median of Two Sorted Arrays) 共 3 种 2.8 k+
5. 最长回文子串(Longest Palindromic Substring) 共 4 种 2.8 k+
6. Z 字形变换(ZigZag Conversion) 共 2 种 1.9 k+
7. 整数反转(Reverse Integer) 共 2 种 2.4 k+
8. 字符串转换整数 (atoi)(String to Integer (atoi)) 共 3 种 4.2 k+
9. 回文数(Palindrome Number) 共 3 种 4.3 k+
11. 盛最多水的容器(Container With Most Water) 共 5 种 4.0 k+
12. 整数转罗马数字(Integer to Roman) 共 3 种 3.2 k+
13. 罗马数字转整数(Roman to Integer) 共 3 种 3.8 k+
14. 最长公共前缀(Longest Common Prefix) 共 4 种 3.0 k+
15. 三数之和(3Sum) 共 3 种 60.7 k+
16. 最接近的三数之和(3Sum Closest) 共 3 种 4.7 k+
17. 电话号码的字母组合(Letter Combinations of a Phone Number) 共 3 种 3.1 k+
18. 四数之和(4Sum) 共 4 种 11.5 k+
19. 删除链表的倒数第 N 个结点(Remove Nth Node From End of List) 共 4 种 1.2 k+
20. 有效的括号(Valid Parentheses) 共 2 种 1.8 k+
21. 合并两个有序链表(Merge Two Sorted Lists) 共 3 种 1.2 k+
22. 括号生成(Generate Parentheses) 共 4 种 1.1 k+
23. 合并K个升序链表(Merge k Sorted Lists) 共 4 种 0.9 k+
24. 两两交换链表中的节点(Swap Nodes in Pairs) 共 3 种 0.5 k+
25. K 个一组翻转链表(Reverse Nodes in k-Group) 共 5 种 1.3 k+
26. 删除有序数组中的重复项(Remove Duplicates from Sorted Array) 共 4 种 1.3 k+
27. 移除元素(Remove Element) 共 4 种 0.4 k+
28. 实现 strStr()(Implement strStr()) 共 5 种 0.8 k+
29. 两数相除(Divide Two Integers) 共 4 种 0.6 k+
30. 串联所有单词的子串(Substring with Concatenation of All Words) 共 3 种 0.6 k+
31. 下一个排列(Next Permutation) 共 2 种 0.8 k+
32. 最长有效括号(Longest Valid Parentheses) 共 2 种 1.4 k+
33. 搜索旋转排序数组(Search in Rotated Sorted Array) 共 3 种 1.0k+
34. 在排序数组中查找元素的第一个和最后一个位置(Find First and Last Position of Element in Sorted Array) 共 3 种 0.5 k+
35. 搜索插入位置(Search Insert Position) 共 3 种 0.3 k+
36. 有效的数独(Valid Sudoku) 共 1 种 0.6 k+
38. 外观数列(Count and Say) 共 5 种 1.1 k+
39. 组合总和(Combination Sum) 共 3 种 1.4 k+
40. 组合总和 II(Combination Sum II) 共 2 种 1.6 k+
41. 缺失的第一个正数(First Missing Positive) 共 3 种 1.2 k+
53. 最大子数组和(Maximum Subarray) 共 3 种 0.3k+
88. 合并两个有序数组(Merge Sorted Array) 共 3 种 0.4 k+
102. 二叉树的层序遍历(Binary Tree Level Order Traversal) 共 3 种 0.4 k+
146. LRU 缓存(LRU Cache) 共 2 种 0.5 k+
160. 相交链表(Intersection of Two Linked Lists) 共 2 种 0.1 k+
200. 岛屿数量(Number of Islands) 共 4 种 0.1 k+
206. 反转链表(Reverse Linked List) 共 3 种 1.0 k+
215. 数组中的第K个最大元素(Kth Largest Element in an Array) 共 3 种 0.5 k+
236. 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree) 共 3 种 0.1 k+
2119. 反转两次的数字(A Number After a Double Reversal) 共 2 种 0.3 k+
2120. 执行所有后缀指令(Execution of All Suffix Instructions Staying in a Grid) 共 1 种 0.4 k+
2124. 检查是否所有 A 都在 B 之前(Check if All A's Appears Before All B's) 共 4 种 0.4 k+
2125. 银行中的激光束数量(Number of Laser Beams in a Bank) 共 3 种 0.3 k+
2126. 摧毁小行星(Destroying Asteroids) 共 2 种 1.6 k+
2129. 将标题首字母大写(Capitalize the Title) 共 2 种 0.6 k+
2130. 链表最大孪生和(Maximum Twin Sum of a Linked List) 共 2 种 0.6 k+
2133. 检查是否每一行每一列都包含全部整数(Check if Every Row and Column Contains All Numbers) 共 1 种 0.6 k+

2 博主简介

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

#秋招##leetcode##leetcode刷题组队##微软##外企#
全部评论
感谢楼主分享
点赞 回复 分享
发布于 2022-07-12 10:47

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务