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

代码随想录day11 栈与队列

article 2024/10/27 2:03:56

文章目录

    • day11 栈与队列(2)
      • 栈与队列的总结

day11 栈与队列(2)

  1. 逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

逆波兰表达式，也就是后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

例：( 1 + 2 ) * ( 3 + 4 )

遇见数字1，2就放入栈，遇到运算符+,就把栈里数据1，2取出用运算符+，结果3再加入栈里。继续操作，遇到3，4放入栈，遇到运算符+，取出3，4，运算符+结果是7，放入栈。遇到运算符*，取出3，7，运算结果是21，放入栈。

我们在输入合法的情况下写函数，不考虑输入非法情况。

class Solution {
    public int evalRPN(String[] tokens) {
        //虽然 Java 提供了一个 Stack 类，但推荐使用 Deque 接口来实现栈的功能，因为 Deque 提供了更多的灵活性和更好的性能。
        // 初始化了一个双端队列，用LiskedList实现
        Deque<Integer> stack =new LinkedList();
        //遍历数组
        for(String s: tokens){
            //处理加法操作符
            if("+".equals(s)){
                stack.push(stack.pop()+stack.pop());
            }else if("-".equals(s)){
                int num1=stack.pop();
                int num2=stack.pop();
                //先出来的是减数，后出来的是被减数
                stack.push(num2-num1);
            }else if("*".equals(s)){
                stack.push(stack.pop()*stack.pop());
            }else if("/".equals(s)){
                int num1=stack.pop();
                if(num1==0){
                    throw new ArithmeticException("Division by zero");
                }
                int num2=stack.pop();
                //先弹出的是除数，再弹出的是被除数
                stack.push(num2/num1);
            }else{
                //如果当前是数字，将其转换为Integer后压入栈
                stack.push(Integer.valueOf(s));
            }
        }
        //栈里唯一一个元素就是答案
        return stack.pop();
    }
}

239. 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/

单调栈的过程pop() push() getMaxValue()

确保出口处的元素的最大值，把小数弹出。像这个例题，直接把1弹出去，留下3，没必要维护比3之前小的元素。

如果pop()的是当前元素最大值3，此时窗口[3,-1,-3]，pop(3)，push(5)，5比-1和-3大。5放出口处。

1 自定义双端队列 MyQueue：

  • poll(int val) 方法：弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出。同时判断队列当前是否为空。
  • add(int val) 方法：添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出，保证队列元素单调递减。
  • peek() 方法：返回队列队顶元素，即当前窗口的最大值。

2 Solution 类和 maxSlidingWindow 方法：

  • 初始化结果数组：int len = nums.length - k + 1; 计算结果数组的长度。
  • 初始化自定义队列：MyQueue myQueue = new MyQueue();
  • 处理前 k 个元素：将前 k 个元素加入队列。
  • 滑动窗口处理：
    • 移除窗口最前面的元素。
    • 加入窗口最后面的元素。
    • 记录当前窗口的最大值。
class MyQueue{
    //自定义的双端队列 MyQueue
    Deque<Integer> deque=new LinkedList<>();

    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    void poll(int val){
        //当然，当前队列不能为空
        if(!deque.isEmpty()&&val==deque.peek()){
            deque.poll();
        }
    }

    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出，保证队列元素单调递减。
    void add(int val){
        while(!deque.isEmpty()&&val>deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }

    //返回队列队顶元素，即当前窗口的最大值。
    int peek(){
        return deque.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //原数组为空，窗口大小为0，返回空数组
        if(nums==null||nums.length==0||k==0){
            return new int[0];
        }
        //原数组长度为1
        if(nums.length==1){
            return nums;
        }
        //初始化结果数组
        int len=nums.length-k+1;
        int[] result=new int[len];
        //记录result中存储位置，作为索引位置来存储每次滑动窗口的最大值
        int num=0;
        MyQueue myQueue=new MyQueue();

        //将前k个元素放入队列
        for(int i=0;i<k;i++){
            myQueue.add(nums[i]);
        }
        result[num]=myQueue.peek();
        num++;

        //处理剩余的元素
        for(int i=k;i<nums.length;i++){
            //滑动窗口移除最前面的元素
            myQueue.poll(nums[i-k]);
            //滑动串口加入最后面的元素
            myQueue.add(nums[i]);
            //记录当前窗口的最大值
            result[num]=myQueue.peek();
            num++;
        }
        return result;
    }
}

347 前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/descriptio

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

输出: [1,2]

示例 2:

输入: nums = [1], k = 1

输出: [1]

统计频率

  • 使用HashMap统计每个元素的出现次数。

解法1：基于大顶堆

  • 创建一个大顶堆，存储元素及其出现次数。
  • 将所有元素加入大顶堆。
  • 从大顶堆中取出前 k 个元素。
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //大顶堆
        //边界条件处理
        if(nums==null||nums.length==0||k==0){
            return new int[0];
        }
        if(k==nums.length){
            return nums;
        }
        //初始化HashMap，统计频次
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //创建大顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        //将所有元素加入大顶堆
        for(Map.Entry<Integer,Integer> entry :map.entrySet()){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        //从大顶堆中取出前k个元素
        int[] ans=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=pq.poll()[0];
        }
        return ans;
    }
}

解法2：基于小顶堆

  • 创建一个小顶堆，存储元素及其出现次数。
  • 维护一个小顶堆，使其最多包含 k 个元素。
  • 如果当前元素的出现次数大于小顶堆的根结点（出现次数最少的元素），则替换掉根结点。
  • 最后从小顶堆中取出所有元素。
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    // 解法2：基于小顶堆实现
    public int[] topKFrequent2(int[] nums, int k) {
        // 边界条件处理
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0]; // 输入数组为空或长度为0，或者k为0，直接返回空数组
        }
        if (k == nums.length) {
            return nums; // 如果k等于nums的长度，直接返回nums数组
        }

        // 初始化 HashMap，统计频次
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1); // 统计每个元素的出现次数
        }

        // 创建小顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        // 遍历 HashMap 中的所有条目
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (pq.size() < k) { // 小顶堆元素个数小于k个时直接加入
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) { // 当前元素的出现次数大于小顶堆的根结点（出现次数最少的那个）
                    pq.poll(); // 弹出队头（小顶堆的根结点），即把堆里出现次数最少的那个删除
                    pq.add(new int[]{entry.getKey(), entry.getValue()}); // 将当前元素加入小顶堆
                }
            }
        }

        // 从大顶堆中取出前 k 个元素
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0]; // 依次从队头弹出元素，存入结果数组
        }

        return ans; // 返回结果数组
    }
}

栈与队列的总结

一 栈与队列的理论基础

  1. Java 中 Stack 和 Queue 是容器吗？

Stack 和 Queue 是容器适配器，它们依赖于底层的具体容器来实现功能。

  1. 我们使用的 JDK 中 Stack 和 Queue 是如何实现的？
  • Stack 类继承自 Vector，因此它是一个线程安全的动态数组。
  • Queue 接口有多个实现类，如 LinkedList、PriorityQueue 等。LinkedList 实现了 Deque 接口，可以作为双端队列使用。
  1. Stack 和 Queue 提供迭代器来遍历空间吗？
  • Stack 和 Queue 都提供了迭代器来遍历元素。Stack 继承自 Vector，因此可以直接使用 Vector 的迭代器。Queue 的实现类如 LinkedList 也提供了迭代器。

栈内元素在内存中是否连续分布？

  • 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
  • 陷阱2：默认情况下，Stack 底层使用 Vector，数据在内存中是连续分布的。但如果是自定义的栈，底层容器不同，数据分布也可能不同。

二 栈经典题目

（1）栈在系统中的应用

  1. 括号匹配问题：

使用栈来匹配括号，确保括号的正确嵌套。

示例代码：

import java.util.Stack;

public class ParenthesesMatcher {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
  1. 字符串去重问题：

使用栈来去除字符串中的相邻重复项。

import java.util.Stack;

public class RemoveDuplicates {
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
        for (char c : S.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}
  1. 逆波兰表达式问题：

使用栈来计算逆波兰表达式。

import java.util.Stack;

public class EvaluateReversePolishNotation {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(applyOp(a, b, token));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    private boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    private int applyOp(int a, int b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default: throw new IllegalArgumentException("Invalid operator");
        }
    }
}

（2）队列的经典题目

  1. 滑动窗口最大值问题

使用单调队列来解决滑动窗口最大值问题。

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {
            // 移除不在窗口范围内的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // 移除小于当前元素的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 当窗口达到指定大小时，记录当前窗口的最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}
  1. 求前 K 个高频元素

使用优先级队列（大顶堆或小顶堆）来求前 K 个高频元素。

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentElements {
    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        if (k == nums.length) {
            return nums;
        }

        // 统计每个元素的出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 创建小顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);

        // 将所有元素加入小顶堆
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (pq.size() < k) {
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) {
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }

        // 从大顶堆中取出前 k 个元素
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0];
        }

        return ans;
    }
}

总结

在栈与队列系列中，我们强调了栈与队列的基础知识，包括它们的底层实现和常见应用场景。通过具体的题目练习，我们可以更好地理解和掌握这些数据结构的使用方法。

  1. 栈与队列的基础：
  • 栈和队列是常见的数据结构，栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。
  • 栈和队列可以通过不同的底层容器实现，如 Vector、LinkedList 等。
  1. 栈的应用：
  • 括号匹配：使用栈来匹配括号，确保括号的正确嵌套。
  • 字符串去重：使用栈来去除字符串中的相邻重复项。
  • 逆波兰表达式：使用栈来计算逆波兰表达式。
  1. 队列的应用：
  • 滑动窗口最大值：使用单调队列来解决滑动窗口最大值问题。
  • 前 K 个高频元素：使用优先级队列（大顶堆或小顶堆）来求前 K 个高频元素。

http://www.kler.cn/news/366639.html

相关文章：

  • 探秘 MySQL 数据类型的艺术：性能与存储的精妙平衡
  • 散列表：为什么经常把散列表和链表放在一起使用？
  • Uni-App-03
  • java中常见集合，非常重要！！！
  • WEBRTC教程:局域网怎么调试，http://172.19.18.101:8080 ,无法访问摄像头和麦克风，请检查权限
  • Redis 发布订阅 总结
  • Android静态变量中的字段被置空了
  • 关键词搜索的“魔法咒语”：用API接口召唤商品数据
  • Ubuntu服务器搭建Tailscale Derp节点
  • 掌握ElasticSearch（四）：数据类型、回复体
  • arm架构 ubuntu 部署docker
  • 校园表白墙源码修复版
  • 基于python智能推荐的丢失物品招领网站的制作，前端vue+django框架，协同过滤算法实现推荐功能
  • 【MySQL 保姆级教学】表的约束--详细（6）
  • #渗透测试#SRC漏洞挖掘# 信息收集-Shodan批量扫描
  • 新王Claude 3.5的6大应用场景
  • android 文字绘制
  • 常见的租用服务器类型和费用
  • Vue学习笔记（三、v-cloak、v-text、v-html指令）
  • 南京移动5G-A网络助力固城湖螃蟹高效运输
  • SIP 业务举例之 Call Forwarding - No Answer（无应答呼叫转移）
  • 一文了解：多智能体系统(MAS)的演变（算法篇）
  • zabbix 6.0 监控自定义服务
  • 设计模式（UML图、类之间关系、设计原则）
  • 【部署篇】RabbitMq-03集群模式部署
  • 基于机器学习的个性化电影推荐系统【源码+安装+讲解+售后+文档】