做钟点工 网站,网站系统繁忙是什么意思,代刷网站建设,网站策划编辑如何做目录
232. 用栈实现队列
225. 用队列实现栈
20. 有效的括号
1047. 删除字符串中的所有相邻重复项
150. 逆波兰表达式求值
239. 滑动窗口最大值
347. 前 K 个高频元素 刷题顺序及思路来源于代码随想录#xff0c;网站地址#xff1a;https://programmercarl.com
232.…目录
232. 用栈实现队列
225. 用队列实现栈
20. 有效的括号
1047. 删除字符串中的所有相邻重复项
150. 逆波兰表达式求值
239. 滑动窗口最大值
347. 前 K 个高频元素 刷题顺序及思路来源于代码随想录网站地址https://programmercarl.com
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双端队列来模拟一个栈只要是标准的栈操作即可。
MyQueue queue new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
import java.util.ArrayDeque;
import java.util.Deque;/*** author light* Description 用栈实现队列** 定义两个栈一个输入栈一个输出栈* 入栈操作将所有元素加入发到输入栈中* 出栈操作要实现队列的先进先出首先先判断输出栈中是否为空如果为空则将输入栈* 中的元素全部加入输出栈中从输出栈中将元素弹出以实现队列先进先出的功能* create 2023-08-11 16:56*/
public class MyQueueTest {public static void main(String[] args) {MyQueue obj new MyQueue();obj.push(1);obj.push(2);int param_3 obj.peek();System.out.println(param_3);int param_2 obj.pop();System.out.println(param_2);boolean param_4 obj.empty();System.out.println(param_4);}}
class MyQueue {DequeInteger stackIn;DequeInteger stackOut;public MyQueue() {stackInnew ArrayDeque();stackOutnew ArrayDeque();}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty()stackOut.isEmpty();}public void dumpstackIn(){if(stackOut.isEmpty()){//如果输出栈中为空将输入栈中所有元素加入到输出栈中while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}}
}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双端队列来模拟一个队列 , 只要是标准的队列操作即可。
MyStack myStack new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
package com.light.code.leetcode.stack_queue;import java.util.Deque;
import java.util.LinkedList;/*** author light* Description 用队列实现栈**利用两个队列版另一种方法直接使用ArrayDeque双端队列进行实现** create 2023-08-11 17:28*/
public class MyStackTest {public static void main(String[] args) {MyStack myStack new MyStack();myStack.push(1);myStack.push(2);System.out.println(myStack.top()); // 返回 2System.out.println(myStack.pop()); // 返回 2System.out.println(myStack.empty()); // 返回 False}
}
class MyStack {DequeInteger que1;DequeInteger que2;public MyStack() {que1new LinkedList();que2new LinkedList();}public void push(int x) {que1.add(x);}public int pop() {while(que1.size()!1){que2.add(que1.pop());}int resque1.pop();while(!que2.isEmpty()){que1.add(que2.pop());}return res;}public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}20. 有效的括号
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
输入s ()
输出true
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;/*** author light* Description 有效的括号** 采用栈解决* create 2023-08-11 18:14*/
public class IsValidTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);String sinput.next();boolean res isValid(s);System.out.println(res);}public static boolean isValid(String s) {DequeCharacter stacknew ArrayDeque();for (int i 0; i s.length(); i) {char chs.charAt(i);if(ch(){stack.push());} else if (ch{) {stack.push(});}else if (ch[) {stack.push(]);} else if (stack.isEmpty()||ch!stack.peek()) {return false;}else {stack.pop();}}return stack.isEmpty();}
}1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入abbaca
输出ca
解释
例如在 abbaca 中我们可以删除 bb 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 aaca其中又只有 aa 可以执行重复项删除操作所以最后的字符串为 ca。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;/*** author light* Description 删除字符串中的所有相邻重复项* create 2023-08-11 18:39*/
public class RemoveDuplicatesTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);String sinput.next();sremoveDuplicates(s);System.out.println(s);}public static String removeDuplicates(String s) {DequeCharacter quenew ArrayDeque();que.push(s.charAt(0));for (int i 1; i s.length(); i) {char chs.charAt(i);if(!que.isEmpty()chque.peek()){que.pop();}else {que.push(ch);}}String s1;while(!que.isEmpty()){s1que.pop()s1;}return s1;}
}150. 逆波兰表达式求值
给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意
有效的算符为 、-、* 和 / 。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。
输入tokens [2,1,,3,*]
输出9
解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;/*** author light* Description 逆波兰表达式求值** (利用栈* create 2023-08-12 13:36*/
public class EvalRPNTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);String[] tokensinput.next().split(,);int resevalRPN(tokens);System.out.println(res);}public static int evalRPN(String[] tokens) {DequeInteger stacknew ArrayDeque();for (String s:tokens){if (.equals(s)) {stack.push(stack.pop()stack.pop());} else if (-.equals(s)) {//注意这里先入栈的作为减数stack.push(-stack.pop()stack.pop());} else if (*.equals(s)) {stack.push(stack.pop()*stack.pop());} else if (/.equals(s)) {//注意这里先入栈的作为除数int temp1stack.pop();int temp2stack.pop();stack.push(temp2/temp1);}else {stack.push(Integer.parseInt(s));}}return stack.peek();}
}239. 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
package com.light.code.leetcode.stack_queue;import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;/*** author light* Description 滑动窗口最大值** 自定义队列队列口中始终存放滑动窗口中的最大值;队内元素单调递减* create 2023-08-12 14:18*/
public class MaxSlidingWindowTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int ninput.nextInt();int[] numsnew int[n];for (int i 0; i n; i) {nums[i]input.nextInt();}int kinput.nextInt();int[] resmaxSlidingWindow(nums,k);System.out.println(Arrays.toString(res));}public static int[] maxSlidingWindow(int[] nums, int k) {MyQue quenew MyQue();int[] resnew int[nums.length-k1]; //定义结果数组int index0;for (int i 0; i k; i) {que.add(nums[i]);}res[index]que.getMaxValue();for (int i k; i nums.length; i) {//维持滑动窗口保证队列头部元素是该滑动窗口的最大值que.pop(nums[i-k]);que.add(nums[i]);res[index]que.getMaxValue();}return res;}
}
//自定义队列
class MyQue{DequeInteger quenew LinkedList();//添加元素时如果要添加的元素大于入口处的元素就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,1;2将要入队2比1大所以1弹出此时队列3,2public void add(int x){while(!que.isEmpty()que.getLast()x){que.removeLast();}que.add(x);}//获取滑动窗口内最大值public int getMaxValue(){return que.peek();}public void pop(int x){if(!que.isEmpty()xque.peek()){que.poll();}}
} 347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]
import java.util.*;/*** author light* Description 前k个高频元素**利用小顶堆堆中只维护k个元素* create 2023-08-12 15:55*/
public class TopKFrequentTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int ninput.nextInt();int[] numsnew int[n];for (int i 0; i n; i) {nums[i]input.nextInt();}int kinput.nextInt();int[] restopKFrequent(nums,k);System.out.println(Arrays.toString(res));}public static int[] topKFrequent(int[] nums, int k) {MapInteger,Integer mapnew HashMap();//key:元素value元素所出现的频率for (int i 0; i nums.length; i) {map.put(nums[i],map.getOrDefault(nums[i],0)1);}//按小顶堆排序从小到大排PriorityQueueInteger quenew PriorityQueue(k, new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return map.get(o1)-map.get(o2);}});for (Integer key:map.keySet()){if(que.size()k){que.add(key);}else if(map.get(key)map.get(que.peek())){que.poll();que.add(key);}}int[] resnew int[k];for (int i 0; i res.length; i) {res[i]que.poll();}return res;}
}
