LeetCode刷题笔记之栈与队列

news/2024/11/30 15:47:58/

一、队列与栈相互转换

1. 232【用栈实现队列】

  • 题目： 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    实现 MyQueue 类：
    • void push(int x) 将元素 x 推到队列的末尾
    • int pop() 从队列的开头移除并返回元素
    • int peek() 返回队列开头的元素
    • boolean empty() 如果队列为空，返回 true ；否则，返回 false
      说明：
    • 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  • 代码：
class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();stackOut = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {if(stackOut.isEmpty()){while (!stackIn.isEmpty()){int temp = stackIn.pop();stackOut.push(temp);}}return stackOut.pop();}public int peek() {int ans = pop();stackOut.push(ans);return ans;}public boolean empty() {if(stackOut.isEmpty() && stackIn.isEmpty()){return true;}return false;}
}

2. 225【用队列实现栈】

  • 题目： 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
    实现 MyStack 类：
    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
      注意：
    • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
    • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
  • 代码：
class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {q1.add(x);}public int pop() {int size = q1.size();while(size>1){q2.add(q1.poll());size--;}int ans = q1.poll();while (!q2.isEmpty()){q1.add(q2.poll());}return ans;}public int top() {int ans = pop();q1.add(ans);return ans;}public boolean empty() {if(q1.isEmpty()){return true;}return false;}
}

二、栈的应用

1. 20【有效的括号】

  • 题目： 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    • 左括号必须用相同类型的右括号闭合。
    • 左括号必须以正确的顺序闭合。
    • 每个右括号都有一个对应的相同类型的左括号。
  • 代码：
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i=0; i<s.length();i++){char c = s.charAt(i);if(c == '('){stack.push(')');}else if(c == '{'){stack.push('}');}else if(c == '['){stack.push(']');}else if(stack.isEmpty() || stack.peek()!=c){return false;}else{stack.pop();}}return stack.isEmpty();}
}

2. 1047【删除字符串中的所有相邻重复项】

  • 题目： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
  • 代码：
    方法一：双指针法
class Solution {public String removeDuplicates(String s) {int slow = 0;StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if(slow == 0){sb.append(c);slow++;}else if(c != sb.charAt(slow-1)){sb.append(c);slow++;}else{sb.deleteCharAt(slow-1);slow--;}}return sb.toString();}
}

方法二：栈

class Solution {public String removeDuplicates(String s) {Deque<Character> stack = new LinkedList<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if(stack.isEmpty() || stack.peek()!=c){stack.push(c);}else {stack.pop();}}String str = "";while (!stack.isEmpty()) {str = stack.pop() + str;}return str;}
}

3. 150【逆波兰表达式求值】

  • 题目： 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    请你计算该表达式。返回一个表示表达式值的整数。
    注意：
    • 有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
    • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    • 两个整数之间的除法总是 向零截断 。
    • 表达式中不含除零运算。
    • 输入是一个根据逆波兰表示法表示的算术表达式。
    • 答案及所有中间计算结果可以用 32 位 整数表示。
  • 代码：
class Solution {public int evalRPN(String[] tokens) {//如果把运算符作为中间节点，将表达式按照中序遍历的规则转换成一个二叉树，//那么逆波兰表达式就是用后序遍历的方式把二叉树序列化的结果。Deque<Integer> stack = new LinkedList<>();for (String s:tokens) {if(s.equals("+")){stack.push(stack.pop()+stack.pop());}else if(s.equals("-")){stack.push(-stack.pop()+stack.pop());}else if(s.equals("*")){stack.push(stack.pop()*stack.pop());}else if(s.equals("/")){int temp = stack.pop();stack.push(stack.pop()/temp);}else{stack.push(Integer.valueOf(s));}}return stack.pop();}
}

三、队列的应用

1. 239【滑动窗口最大值】

  • 题目： 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
  • 代码：
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {//不能使用双指针法，因为如果当前窗口的最大值不在下一个窗口，//则下一个窗口还需重新寻找最大值//因此需要维护一个最大值队列，该队列是递减的//若滑出元素等于队头元素，则需将队头弹出//若滑入元素大于队尾元素，则需将队尾弹出//将滑入元素入队int[] ans = new int[nums.length-k+1];Deque<Integer> queue = new ArrayDeque<>();for (int i = 0; i < nums.length; i++) {while (!queue.isEmpty() && nums[i]>queue.peekLast()){queue.pollLast();}queue.add(nums[i]);if(i-k+1>=0){ans[i-k+1] = queue.peek();if(nums[i-k+1] == queue.peek()){queue.poll();}}}return ans;}
}

2. 347【前K个高频元素】

  • 题目： 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。
  • 代码：
class Solution {public int[] topKFrequent(int[] nums, int k) {//可以使用map来存储每个元素及其对应出现的频率//寻找频率前k个元素，可以使用优先级队列PriorityQueue//PriorityQueue底层使用了堆的数据结构，满足FIFO原则//队头元素只可能是队列中优先级最高的元素//所以这里使用小根堆方式保留出现频率前k个高的元素PriorityQueue<int[]> pq = new PriorityQueue<>(new compareArr());HashMap<Integer,Integer> map = new HashMap<>();int[] ans = new int[k];for (int i = 0; i < nums.length; i++) {map.put(nums[i],map.getOrDefault(nums[i],0)+1);}for(Map.Entry<Integer,Integer> entry:map.entrySet()){int[] temp = new int[2];temp[0] = entry.getKey();temp[1] = entry.getValue();pq.offer(temp);}for (int i = pq.size()-1; i >= 0; i--) {if(i>=k){pq.poll();}else{ans[i] = pq.poll()[0];}}return ans;}
}
class compareArr implements Comparator<int[]>{@Overridepublic int compare(int[] m,int[] n) {return m[1]-n[1];}
}

http://www.ppmy.cn/news/1290572.html

相关文章

前端工程化回顾-vite 构建神器

前端工程化回顾-vite 构建神器

1.构建vite 项目 pnpm create vite2.常用的配置&#xff1a; 1.公共资源路径配置&#xff1a; base: ./, 默认是/2.路径别名配置&#xff1a; resolve: {alias: {: path.resolve(__dirname, ./src),ass: path.resolve(__dirname, ./src/assets),comp: path.resolve(__dirnam…
阅读更多...
C++：通过erase删除map的键值对

C++：通过erase删除map的键值对

map是经常使用的数据结构，erase可以删除map中的键值对。 可以通过以下几种方式使用erase 1.通过迭代器进行删除 #include <iostream> #include <map> #include <string> using namespace std;void pMap(const string& w, const auto& m) {cout&l…
阅读更多...
Python基础-06（while循环、break、continue）

Python基础-06（while循环、break、continue）

文章目录 前言一、while循环二、break&#xff08;中断&#xff09;和continue&#xff08;跳过&#xff09;1.break2.continue 总结 前言 上章是关于if关键字&#xff0c;属于条件控制语句或者称为流程控制语句&#xff0c;就好比于一个分岔路口&#xff0c;哪个路口符合条件…
阅读更多...
原码、反码、补码，计算机中负数的表示

原码、反码、补码，计算机中负数的表示

原码&#xff1a;将一个整数&#xff0c;转换成二进制&#xff0c;就是其原码。 如单字节的5的原码为&#xff1a;0000 0101&#xff1b;-5的原码为1000 0101。 反码&#xff1a;正数的反码就是其原码&#xff1b;负数的反码是将原码中&#xff0c;除符号位以外&#xff0c;每一…
阅读更多...
面试题理解深层次的数组名

面试题理解深层次的数组名

目录 引言 一&#xff1a;一维数组 举例如下 1.铺垫知识 数组名是数组首元素的地址&#xff0c;但是有两个特殊情况 &#xff08;1&#xff09;sizeof(数组名) &#xff08;2&#xff09;&数组名 2.分析讲解上述代码结果 2.字符数组 举例一如下 1.知识铺垫 …
阅读更多...
灸哥问答：分布式系统中数据一致性的问题如何解决

灸哥问答：分布式系统中数据一致性的问题如何解决

在分布式系统&#xff0c;数据一致性的问题是一个老生常谈&#xff0c;必须面对的一个问题&#xff0c;而且又极具挑战和复杂度的一个问题&#xff0c;针对数据一致性的问题&#xff0c;没有一个简单的单一的解决方案可以圆满解决&#xff0c;是需要结合具体的场景&#xff0c;…
阅读更多...
二分查找（一）

二分查找（一）

算法原理 原理&#xff1a;当一个序列有“二段性”的时候&#xff0c;就可以使用二分查找算法。 适用范围&#xff1a;根据规律找一个点&#xff0c;能将这个数组分成两部分&#xff0c;根据规律能有选择性的舍去一部分&#xff0c;进而在另一个部分继续查找。 除了最普通的…
阅读更多...
普中STM32-PZ6806L开发板(HAL库函数实现-TIM5 设置 PWM input, 获取频率跟占空比)

普中STM32-PZ6806L开发板(HAL库函数实现-TIM5 设置 PWM input, 获取频率跟占空比)

简介 初始化 TIM5 为 PWM input CH1&#xff0c; 获取输入PWM的频率和占空比电路原理图 连线 将 PC7 与 PA0使用跳线进行连接 其他知识 APIs /* Blocking mode: Polling */ HAL_StatusTypeDef HAL_TIM_IC_Start(TIM_HandleTypeDef *htim, uint32_t Channel); // 堵塞捕获开…
阅读更多...
最新文章

Copyright @ 2022~2023