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

优选算法 - 5 （ 栈 队列 + 宽搜 优先级队列 9000 字详解 ）

article 2024/11/18 21:52:05

一：栈

1.1 删除字符串中的所有相邻重复项

题目链接：删除字符串中的所有相邻重复项

在这里插入图片描述
在这里插入图片描述

class Solution {
    public String removeDuplicates(String _s) {
        // 用 StringBuffer 模拟一下栈结构
        StringBuffer ret = new StringBuffer();
        // 接着把 _s 转换为字符数组方便操作
        char[] s = _s.toCharArray();

        // 接着遍历一下这个字符数组
        for(char ch : s){
            // 因为栈顶元素的索引是 ret 的长度减一，为了保证不发生越界访问，我们要保证 ret 中的元素不为空
            //要避免越界异常，需要首先判断 ret 是否为空，再访问栈顶元素： if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1))

            if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1)) ret.deleteCharAt(ret.length() - 1);
            else ret.append(ch);
        }

        // 循环结束后 ret 就存储着最终的结果，返回即可
        return ret.toString();
    }
}

在这里插入图片描述

1.2 比较含退格的字符串

题目链接：比较含退格的字符串

在这里插入图片描述

在这里插入图片描述

class Solution {
   public boolean backspaceCompare(String s, String t)
    {
        // 调用 changeStr 方法处理字符串 s 和 t，比较它们的处理结果是否相等
        return changeStr(s).equals(changeStr(t));
    }

    // 辅助方法：将字符串中的退格符号（#）应用到字符串，返回最终的结果
    public String changeStr(String s){
        // 此时使用 StringBuffer 模拟栈结构
        StringBuffer ret = new StringBuffer();
        
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch != '#') ret.append(ch);
            else{
                // 如果栈非空（ret 中有字符），删除栈顶字符（出栈操作）
                if (ret.length() > 0) ret.deleteCharAt(ret.length() - 1);
            }
        }

        return ret.toString();
    }
}

在这里插入图片描述

1.3 基本计算器 II

题目链接：基本计算器 II

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {
    public int calculate(String _s) {
        // 用栈存储 Integer 类型的数字
        Stack<Integer> st = new Stack<>();
        char[] s = _s.toCharArray();
        char op = '+'; // 因为这题没有括号，我们明显知道乘除的优先级是大于加减的，因此不必用一个栈来存储符号，用一个字符即可
        int i = 0,n = s.length; // 遍历字符串的变量 i 以及字符数组 s 的长度 n

        // 开始遍历字符串
        while(i < n){
            // 首先先跳过空格
            if(s[i] == ' ') i++;
           else if (s[i] >= '0' && s[i] <= '9') {
                // 先把数字提取出来，用 tmp 临时存储一下数字
                int tmp = 0;
                while(i < n && s[i] <= '9' && s[i] >= '0'){ // 因为在提取字符时要让 i 移动，所以我们要保证 i 不越界以及这个字符是数字
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }

                // 接着分情况讨论
                if(op == '+') st.push(tmp);
                else if(op == '-') st.push(-tmp);
                else if(op == '*') st.push(st.pop() * tmp);
                else st.push(st.pop() / tmp);
            }else op = s[i++];
        }

        // while 循环结束后，st 存的就都是正数和负数了，我们要把栈中的元素取出来相加
        int sum = 0;
        for(int x : st) sum += x;
        
        return sum;
    }
}

在这里插入图片描述

1.4 字符串解码

题目链接：字符串解码
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {
    public String decodeString(String _s) {
        // 我们用两个 Stack 分别存储字符串和重复数字
        Stack<StringBuffer> st = new Stack<>(); // 存储字符串
        Stack<Integer> nums = new Stack<>(); // 存储重复次数
        st.push(new StringBuffer());; // 先往 st 中丢一个空字符串，方便处理边界情况
        char[] s = _s.toCharArray();
        int n = s.length, i = 0; // n 用于存储字符数组的长度， i 用于遍历字符数组

        while(i < n){
            if(s[i] >= '0' && s[i] <= '9'){  // 当 i 遇到数字时
                int tmp = 0; // 用 tmp 临时存储一下数字
                while(i < n && s[i] >= '0' && s[i] <= '9'){ // 因为 i 会加加，为了防止数组越界还是判断一下，并判断一下当前的字符加加后是不是还是数字
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(tmp);

            }
            
            else if(s[i] == '['){ // 当 i 遇到了左括号时
                // 把左括号后面的字符提取出来，放入 st 中
                i++; // 先跳过字符'['
                StringBuffer tmp = new StringBuffer(); // 用于存储括号内的部分字符串
                while(s[i] >= 'a' && s[i] <= 'z'){
                    tmp.append(s[i]);
                    i++;
                }
                 // 当循环结束后，把 tmp 丢入 st 中
                st.push(tmp);
            } 
            
            else if(s[i] == ']'){ // 当 i 遇到了右括号时
                // 取出 st 中的字符串和 nums 中的数字进行解析，解析完后拼接在 st 栈顶元素的后面
                StringBuffer tmp = st.pop();
                int k = nums.pop();
                while(k > 0){
                    st.peek().append(tmp);
                    k--;
                }
                i++; // 跳过右括号
            }
            
            else{ // 遇到了普通的字符
                StringBuffer tmp = new StringBuffer(); // 临时存储连续的字母
                while (i < n && s[i] >= 'a' && s[i] <= 'z'){
                    tmp.append(s[i]);
                    i++;
                }
                 // 将提取的字母拼接到当前栈顶字符串中
                st.peek().append(tmp);
            }
        }
         
        // 返回最终拼接结果
        return st.peek().toString();
    }
}

在这里插入图片描述

1.5 验证栈序列

题目链接：验证栈序列

在这里插入图片描述
在这里插入图片描述

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 用 st 来记录已经入栈的信息
        Stack<Integer> st = new Stack<>();
        int i = 0, n = popped.length; // i 用来遍历 popped 数组，n 用来记录数组长度

        for(int x : pushed){
            // 先把元素丢进 st 中
            st.push(x);

            // 接着循环判断一下是否需要出栈,出栈要保证元素不为空
            while(st.isEmpty() == false && st.peek() == popped[i]){
                st.pop();
                i++;
            }
        }

        //循环结束后判断一下 i 是否等于 n 就可以了
        return i == n;

    }
}

在这里插入图片描述

二：队列+宽搜

2.1 N 叉树的层序遍历

题目链接：N 叉树的层序遍历
在这里插入图片描述
在这里插入图片描述

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        // 用 ret 存储最终的结果
        List<List<Integer>> ret = new ArrayList<>();
        // 用队列 q 来模拟层序遍历的过程
        Queue<Node> q = new LinkedList<>();

        // 如果根节点为空，直接返回空列表
        if (root == null) return ret;
        else q.add(root); // 先把根节点丢进去

        // 接下来开始循环了，只要队列不为空就一直循环
        while(!q.isEmpty()){
            // 首先用 sz 存储一下这一层有多少个元素
            int sz = q.size();
            List<Integer> tmp = new LinkedList<>(); // 用来临时存储这一层的 t.val 值
            for(int i = 0; i < sz; i++){
                Node t = q.poll();
                tmp.add(t.val);

                // 接着把 t 的子元素放进去
                for(Node child : t.children){
                    if (child != null) q.add(child);
                }
            }

            // 将当前层的节点值列表加入最终结果列表
            ret.add(tmp);
        }
         // 当循环结束后 ret 就存储着最终结果
         return ret;
    }
}

在这里插入图片描述

2.2 二叉树的锯齿形层序遍历

题目链接：二叉树的锯齿形层序遍历

在这里插入图片描述

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 用 ret 存储最终的结果,q 模拟程序遍历的过程
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        int level = 1; // 用于标记当前的层数

        if(root == null) return ret; // 如果 root 为空，返回一个空的 ret
        else q.add(root);

        while(!q.isEmpty()){
            int sz = q.size();
            List<Integer> tmp = new LinkedList<>();
            for(int i = 0; i < sz; i++){
                TreeNode t = q.poll();
                tmp.add(t.val);

                if (t.left != null) q.add(t.left);
                if (t.right != null) q.add(t.right);
            }

            // 判断一下是否需要翻转
            if(level % 2 == 0)  Collections.reverse(tmp);
            ret.add(tmp);

            // 这一层结束后让 level 加一
            level++;
        }

        return ret;
    }
}

在这里插入图片描述

2.3 二叉树最大宽度

题目链接：二叉树最大宽度
在这里插入图片描述
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        // 用 List 模拟队列，pair 分别存储节点以及节点对应的编号
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        // 因为 root 不为空，所以我们直接把 root 添加进去
        q.add(new Pair<TreeNode, Integer>(root, 1));
        int ret = 0; // 用 ret 记录最终的结果

        // 当这一层的队列不为空就继续循环直到这一层的队列元素为空
        while(!q.isEmpty()){
            // 先计算当前层级的最大宽度，并看看是否需要更新结果
            Pair<TreeNode, Integer> t1 = q.get(0); // 获取这层第一个节点
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1); // 获取这层的最后一个节点
            ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);

            // 接着开始把下一层元素弄到 tmp 中，接着让 tmp 当下一层的 q 
            // 设置元素需要先获取当前元素的引用和索引
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for (Pair<TreeNode, Integer> t : q) {
                TreeNode node = t.getKey();
                int index = t.getValue();

                if (node.left != null) tmp.add(new Pair<TreeNode,Integer>(node.left, index * 2)); // 先处理左孩子
                if (node.right != null) tmp.add(new Pair<TreeNode,Integer>(node.right, index * 2 + 1)); // 再处理右孩子
            }

            // 循环结束后把 tmp 赋给 q，让他当下一层的 q
            q = tmp;
        }

        // 返回最大宽度
        return ret;
    }
}

在这里插入图片描述

2.4 在每个树行中找最大值

题目链接：在每个树行中找最大值

在这里插入图片描述

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        // 用 ret 存储最终的结果
        List<Integer> ret = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root == null) return ret;
        else q.add(root);

        while(!q.isEmpty()){
            int sz = q.size(), tmp = Integer.MIN_VALUE; //  先用 sz 记录一下这层的元素个数,tmp 记录这一层的最大值
            for(int i = 0; i < sz; i++){
               // 从队列中取出一个节点
                TreeNode t = q.poll();
                // 更新当前层的最大值
                tmp = Math.max(tmp, t.val);

                // 接着把这个节点的左右孩子添加进去
                if(t.left != null) q.add(t.left);
                if(t.right != null) q.add(t.right);
            }

            // 循环结束后把 tmp 存在 ret 中
            ret.add(tmp);
        }

        return ret;
    }
}

在这里插入图片描述

三：优先级队列

3.1 最后一块石头重量

题目链接：最后一块石头重量

在这里插入图片描述
在这里插入图片描述

class Solution {
    public int lastStoneWeight(int[] stones) {
        // 此处使用大根堆模拟解题过程
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        
        // 接着把数组中的元素全丢入大根堆中
        for(int x : stones) heap.offer(x);

        while(heap.size() >= 2){
            int a = heap.poll();
            int b = heap.poll();
            if(a > b) heap.offer(a - b);
        }

        // 循环结束后如果大根堆还有元素就是最后的答案，没有元素返回 0
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

在这里插入图片描述

3.2 数据流中的第 K 大元素

题目链接：数据流中的第 K 大元素

在这里插入图片描述
在这里插入图片描述

class KthLargest {
     // 创建一个大小为 k 的小根堆
    PriorityQueue<Integer> heap;
    // 存储 k 的值
    int _k;

    public KthLargest(int k, int[] nums) {
        // 干两件事，一是初始化 k，二是把 nums 中的元素放入堆中，最后用堆存储筛前 k 大的元素
        _k = k;
        heap = new PriorityQueue<>();
        for(int x : nums){
            heap.offer(x);
            if(heap.size() > _k) heap.poll();
        }  
    }
    
    public int add(int val) {
        heap.offer(val);
        if(heap.size() > _k) heap.poll();
        return heap.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

在这里插入图片描述

3.3 前 K 个高频单词

题目链接：前 K 个高频单词
在这里插入图片描述
在这里插入图片描述

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 先用一个哈希表统计一下 words 中字符串以及对应字符串出现的频率
        Map<String, Integer> hash = new HashMap<>();
        for(String s : words) hash.put(s, hash.getOrDefault(s, 0) + 1);

        // 接着创建一个堆，并初始化一个比较器，
        // 堆的排序规则：
        // - 频率低的单词排在前面（优先移除）。
        // - 如果频率相同，按字典序降序排列（为了保持正确的优先顺序）。
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>(
            (a, b) -> {
                if(a.getValue().equals(b.getValue())) return b.getKey().compareTo(a.getKey()); // 如果出现次数相同就按照字符序降序比较
                else return a.getValue() - b.getValue(); // 按照频率顺序比较
            }
        );

        // 接下来开始循环，把 words 中的元素都丢入堆中，同时保持堆的大小为 k
         for (Map.Entry<String, Integer> e : hash.entrySet()) {
            heap.offer(new Pair<>(e.getKey(), e.getValue()));
            if(heap.size() > k) heap.poll();
         }

        // 4. 提取结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) 
            ret.add(heap.poll().getKey());

         // 因为堆的顺序是从低频到高频，结果需要逆序
        Collections.reverse(ret);

        // 返回结果
        return ret;
    }
}

在这里插入图片描述

3.4 数据流中的中位数

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

在这里插入图片描述
在这里插入图片描述

class MedianFinder {
    // 使用两个堆来管理数据流
    PriorityQueue<Integer> left; // 大根堆，存储较小的一半元素
    PriorityQueue<Integer> right; // 小根堆，存储较大的一半元素

            // 初始化两个堆
    public MedianFinder() {
        left = new PriorityQueue<>((a, b) -> b - a); // 大堆，从大到小排序
        right = new PriorityQueue<>((a, b) -> a - b); // 小堆，从小到大排序
    }
    
    // 添加数字
    public void addNum(int num) {
        // 分情况讨论，首先看看两个堆的关系，是 m == n 还是 m == n+1
        if(left.size() == right.size()){ //  m == n 
            if(left.isEmpty() || num <= left.peek()) left.offer(num);
            else{right.offer(num); left.offer(right.poll());}
        }else{ // m == n+1
            if(num <= left.peek()){left.offer(num); right.offer(left.poll());}
            else right.offer(num);
        }
    }
    
    // 返回当前数据流的中位数
    public double findMedian() {
        if(left.size() == right.size()) return  (left.peek() + right.peek()) / 2.0;
        else return left.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

在这里插入图片描述


http://www.kler.cn/a/399248.html

相关文章：

  • 【开源免费】基于SpringBoot+Vue.JS购物推荐网站（JAVA毕业设计）
  • 【Golang】——Gin 框架中的模板渲染详解
  • 无人机场景 - 目标检测数据集 - 车辆检测数据集下载「包含VOC、COCO、YOLO三种格式」
  • Django5 2024全栈开发指南（一）：框架简介、环境搭建与项目结构
  • 腾讯云内容合规基于springboot架构设计
  • 【Java多线程】单例模式（饿汉模式和懒汉模式）
  • Windows下 TortoiseGit 的使用
  • Python绘制雪花
  • 2.STM32之通信接口《精讲》之USART通信
  • 执行flink sql连接clickhouse库
  • 《线性代数》学习笔记
  • 一个功能强大的文档解析和转换工具，支持PDF、DOCX、PPTX和Markdown等
  • 常用命令之LinuxOracleHivePython
  • 矩阵转置 Matlab与Numpy差异，复数慎重
  • 基于Java Springboot宠物流浪救助系统
  • Android中Crash Debug技巧
  • 单体架构 IM 系统之 Server 节点状态化分析
  • 【Rust中的策略模式实现】
  • 10款PDF合并工具的使用体验与推荐！！！
  • 【Redis】使用redis实现登录校验功能
  • vim配置 --＞ 在创建的普通用户下
  • linux,一、部署LNMP环境二、配置动静分离三、地址重写四、编写systemd Unit文件
  • Azure pipeline 通过git命令修改文件
  • 记录配置ubuntu18.04下运行ORBSLAM3的ros接口的过程及执行单目imu模式遇到的问题（详细说明防止忘记）
  • 【Python刷题】最少拐弯路线问题
  • 实战：深入探讨 MySQL 和 SQL Server 全文索引的使用及其弊端