Day 13 | 150.逆波兰表达式求值、239.滑动窗口最大值、347.前 K 个高频元素

Leetcode 150.逆波兰表达式求值

题目：150.逆波兰表达式求值

初始思路

和括号的匹配有些像，不过不是相等了，而是在栈顶遇到符号的时候进行运算。

代码

var evalRPN = function (tokens) {
    // 用map存下每个运算符
    const map = new Map([
        ['+', (a, b) => parseInt(a) + parseInt(b)],
        ['-', (a, b) => a - b],
        ['*', (a, b) => a * b],
        ['/', (a, b) => parseInt((a / b)) | 0]
    ])
    let stack = []
    for (const i of tokens) {
        // 如果tokens中这个字符在map中，即是字符，就进行运算
        if (map.has(i)) {
            let fn = map.get(i)
            let a = stack.pop()
            let b = stack.pop()
            // 将运算出来的结果再放入
            let res = fn(b, a)
            stack.push(res)
        } else {
            // 如果是数字就入栈
            stack.push(i)
        }
    }
    return stack[0]
};

感想

1. 使用map存下运算符，简洁方便。
2. 在弹出数字的时候，要注意第一下弹出的应该是减数或者是除数，第二次弹出的才是被减数和被除数。
3. 加法运算要转换，不然会当成字符串拼接

Leetcode 239.滑动窗口最大值

题目：239.滑动窗口最大值 讲解：https://www.bilibili.com/video/BV1XS4y1p7qj/

初始思路

困难题，尽力而为。。。

代码

var maxSlidingWindow = function (nums, k) {
    // 自定义一个单调队列
    class MonoQueue {
        constructor() {
            this.queue = []
        }
        // 如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
        enqueue (value) {
            let back = this.queue[this.queue.length - 1]
            while (back !== undefined && back < value) {
                this.queue.pop()
                back = this.queue[this.queue.length - 1]
            }
            this.queue.push(value)
        }
        // 如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
        dequeue (value) {
            let front = this.front()
            if (front === value) {
                this.queue.shift()
            }
        }
        // 返回队列最前端的元素
        front () {
            return this.queue[0]
        }
    }
    let q = new MonoQueue()
    let i = 0, j = 0
    let res = []
    while (j < k) {
        // 先把滑动窗口内的元素加入单调队列中，按照enqueue的逻辑进行过滤
        q.enqueue(nums[j++])
    }
    res.push(q.front())
    while (j < nums.length) {
        q.enqueue(nums[j])
        q.dequeue(nums[i])
        res.push(q.front())
        i++
        j++
    }
    return res
};

感想

1. 单调队列的思路看懂了，但是代码还是不是很明白。

Leetcode 347.前 K 个高频元素

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

初始思路

topK问题，没什么头绪

代码

var topKFrequent = function (nums, k) {
    // 法一：哈希表+sort
    let map = new Map()
    for (let num of nums) {
        //初始化出现次数为1，之后累加
        map.set(num, map.has(num) ? map.get(num) + 1 : 1)
    }
    if (k === map.size) {
        //k如果等于map.size，直接返回全部key
        return [...map.keys()]
    }
    let arr = Array.from(map).sort((a, b) => {
        //从大到小排序
        return b[1] - a[1]
    })
    return arr.slice(0, k).map(n => n[0])//截取前k个key
};
var topKFrequent = function (nums, k) {
    //法二：哈希表+桶排序
    let map = new Map();
    for (let num of nums) {
        //初始化出现次数为1，之后累加
        map.set(num, map.has(num) ? map.get(num) + 1 : 1);
    }
    if (k === map.size) {
        //k如果等于map.size，直接返回全部key
        return [...map.keys()];
    }
    const bucketSort = () => {
        let arr = [];
        let res = [];
        map.forEach((value, key) => {
            //arr[i]存放频率为i的key数组
            if (!arr[value]) arr[value] = [key];
            else arr[value].push(key);
        });
        for (let i = arr.length - 1; i >= 0 && res.length < k; i--) {
            if (arr[i]) {
                //将数组转换为用逗号分割的参数序列
                res.push(...arr[i]);
            }
        }
        return res;
    }
    return bucketSort();
};

感想

1. 题解：https://leetcode.cn/problems/top-k-frequent-elements/solution/by-confident-coldenbfp-w28l/
   方法一： 将哈希表转成数组，用sort方法排序再截取前k个key
   方法二： 桶排序，将频率一致的放在同一个桶里，数组下标i放置频率为i的key，最后倒序取出k个key
   sort时间复杂度为为O(nlogn)，不符合题意，第二种最好的时间复杂度接近O(n)
2. 代码随想录是自己定义了堆的结构