当前位置：首页 > article >正文

LeetCode热题100JS（79/100）第十五天|347|295|121|55|45

article 2025/3/31 9:17:33

347. 前 K 个高频元素

题目链接：347. 前 K 个高频元素

难度：中等

刷题状态：1刷

新知识：

解题过程

思考

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

没思路，看答案

题解分析

参考题解链接：240. 搜索二维矩阵 II（贪心，清晰图解）

详细分析如下，时间复杂度：O(nlogn)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    //使用map统计每个元素出现的次数
    let map=new Map()
    for(let num of nums){
        if(!map.has(num)) map.set(num,0)
        map.set(num,map.get(num)+1)
    }
    //map变成arry再排序
    let res=[]
    let sort=Array.from(map).sort((a,b)=>b[1]-a[1]).forEach(([key,val])=>{
        if(!k) return
        k--
        res.push(key)
    })
    return res
};

手搓答案（无非废话版）

/** 
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */

 var topKFrequent=function(nums,k){
    let res=[],map=new Map()
    for(let n of nums){
        if(!map.has(n)) map.set(n,0)
        map.set(n,map.get(n)+1)
    }
    Array.from(map).sort((a,b)=>b[1]-a[1]).forEach(([key,val])=>{
        if(!k) return 
        k--
        res.push(key)
    })
    return res
 }

总结

拿下，如果要用最小栈的方法，那就很复杂了，，我看不懂

295. 数据流的中位数

题目链接：295. 数据流的中位数

难度：困难

刷题状态：1刷

新知识：

- 优先队列（MaxPriorityQueue 和 MinPriorityQueue）

- this.right.enqueue(num); // 将新元素加入大顶堆

- this.right.dequeue() //弹出堆顶元素

- this.right.front() //front 方法返回堆顶元素而不移除它

- this.left.size()和length一样

解题过程

思考

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

定义类的题目，不会，看答案

题解分析

参考题解链接：如何自然引入大小堆？简洁写法！（Python/Java/C++/Go/JS/Rust）

详细分析如下

var MedianFinder = function() {
    //优先队列（MaxPriorityQueue 和 MinPriorityQueue）
    this.left = new MaxPriorityQueue();  // 小顶堆，用于存储较小的一半
    this.right = new MinPriorityQueue(); // 大顶堆，用于存储较大的一半
};

MedianFinder.prototype.addNum = function(num) {
    if (this.left.size() === this.right.size()) {
        this.right.enqueue(num); // 将新元素加入大顶堆
        this.left.enqueue(this.right.dequeue()); // 将小顶堆的堆顶元素（即 right 中的最小元素）移到大顶堆，以保持 left 中的元素始终不大于 right 中的元素。
    } else {
        this.left.enqueue(num);// 将新元素加入小顶堆
        this.right.enqueue(this.left.dequeue()); // 将大顶堆的堆顶元素（即 left 中的最大元素）移到小顶堆，以保持 right 中的元素始终不小于 left 中的元素。
    }
};


MedianFinder.prototype.findMedian = function() {
    //front 方法返回堆顶元素而不移除它
    if (this.left.size() > this.right.size()) {
        return this.left.front();
    }
    return (this.left.front() + this.right.front()) / 2;
};

手搓答案（无非废话版）

var MedianFinder=function(){
    this.left=new MaxPriorityQueue()
    this.right=new MinPriorityQueue()
}

MedianFinder.prototype.addNum=function(num){
    if(this.left.size()==this.right.size()){
        this.right.enqueue(num)
        this.left.enqueue(this.right.dequeue())
    }else{
        this.left.enqueue(num)
        this.right.enqueue(this.left.dequeue())
    }
}

MedianFinder.prototype.findMedian=function(){
    if(this.left.size()>this.right.size()){
        return this.left.front()
    }else{
        return (this.left.front()+this.right.front())/2.0
    }
}

总结

新知识优先队列，元素的出队顺序不是按照它们进入队列的顺序，而是根据它们的优先级。

121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

难度：简单

刷题状态：1刷

新知识：

解题过程

思考

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

贪心算法类型题目

题解分析

参考题解链接：买卖股票的最佳时机

详细分析如下，

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let minprice=Infinity,maxprofit=0
    for(let p of prices){
        //比较利润最大值
        maxprofit=Math.max(p-minprice,maxprofit)
        //更新最小价格
        minprice=Math.min(minprice,p)
    }
    return maxprofit
};

手搓答案（无非废话版）

/**
 * @param {number[]} prices
 * @return {number}
 */

 var maxProfit=function(prices){
    let minp=Infinity,res=0
    for(let p of prices){
        res=Math.max(p-minp,res)
        minp=Math.min(minp,p)
    }
    return res
 }

总结

拿下，基础贪心算法题

55. 跳跃游戏

题目链接：55. 跳跃游戏

难度：中等

刷题状态：1刷

新知识：

解题过程

思考

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

题解分析

参考题解链接：【跳跃游戏】别想那么多，就挨着跳吧

详细分析如下，

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    //step表示当前位置能到的最远下标
    let step=0
    for(let i=0;i<nums.length;i++){
        if(step>=nums.length-1) return true//提前结束
        if(i>step) return false//全部循环完了还是走不到
        step=Math.max(step,i+nums[i])
    }
};

手搓答案（无非废话版）

/**
 * @param {number[]} nums
 * @return {boolean}
 */

 var canJump=function(nums){
    let step=0,n=nums.length
    for(let i=0;i<n;i++){
        if(step>=n-1) return true
        if(step<i) return false
        step=Math.max(step,i+nums[i])
    }
 }

总结

拿下

45. 跳跃游戏 II

题目链接：45. 跳跃游戏 II

难度：中等

刷题状态：1刷

新知识：

解题过程

思考

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

题解分析

参考题解链接：【跳跃游戏 II】别想那么多，就挨着跳吧 II

详细分析如下，

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    //end是跳跃边界
    let res=0,end=0,step=0
    for(let i=0;i<nums.length-1;i++){
        step=Math.max(step,i+nums[i])
        if(i==end){
            //说明已经到边界了，更新边界为当前能到达的最远距离
            end=step
            //走了一步
            res++
        }
    }
    return res
};

手搓答案（无非废话版）

/**
 * @param {number[]} nums
 * @return {number}
 */

 var jump=function(nums){
    let res=0,end=0,step=0,n=nums.length
    for(let i=0;i<n-1;i++){
        step=Math.max(step,i+nums[i])
        if(i==end){
            end=step
            res++
        }
    }
    return res
 }