做汽车介绍视频的网站吗,网站推广排名,呼和浩特网站制作公司,编辑网站用什么软件一、队列与栈相互转换
1. 232【用栈实现队列】
题目#xff1a; 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a; 实现 MyQueue 类#xff1a; void push(int x) 将元素 x 推到队列的末…一、队列与栈相互转换
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 {StackInteger stackIn;StackInteger 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 {QueueInteger q1;QueueInteger 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(size1){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) {StackCharacter stack new Stack();for(int i0; is.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) {DequeCharacter 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) {//如果把运算符作为中间节点将表达式按照中序遍历的规则转换成一个二叉树//那么逆波兰表达式就是用后序遍历的方式把二叉树序列化的结果。DequeInteger 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-k1];DequeInteger 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-k10){ans[i-k1] queue.peek();if(nums[i-k1] 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个高的元素PriorityQueueint[] pq new PriorityQueue(new compareArr());HashMapInteger,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.EntryInteger,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(ik){pq.poll();}else{ans[i] pq.poll()[0];}}return ans;}
}
class compareArr implements Comparatorint[]{Overridepublic int compare(int[] m,int[] n) {return m[1]-n[1];}
}
