青岛通力建设集团网站,微商的货源都从哪来,成都网站建设木子网络,Wordpress如何自定义小工具前言
我做这类文档一个重要的目的还是给正在学习的大家提供方向#xff08;例如想要掌握基础用法#xff0c;该刷哪些题#xff1f;#xff09;我的解析也不会做的非常详细#xff0c;只会提供思路和一些关键点#xff0c;力扣上的大佬们的题解质量是非常非常高滴#…前言
我做这类文档一个重要的目的还是给正在学习的大家提供方向例如想要掌握基础用法该刷哪些题我的解析也不会做的非常详细只会提供思路和一些关键点力扣上的大佬们的题解质量是非常非常高滴
共勉 一.什么是栈和队列
1.队列
简单来说就是一种先进先出的线性数据结构如下图 2.栈
简单来说就是一种先进后出的线性数据结构如下图 二.在习题中掌握基本使用【力扣】
ps下面12两题虽然要求使用栈和队列这边我利用数组来实现栈和队列方便各位理解原理和如何自我实现我反倒觉得自己的是实现比java自带的要方便但是部分可以省去很多麻烦。
1.用栈实现队列
题目链接:232. 用栈实现队列 - 力扣LeetCode
题面:
基本分析: 可以利用数组模拟数据结构然后抽象出两个指针模拟队列边界那么进出等操作其实是指针的移动
class MyQueue {//利用数组模型模拟一个队列int[] arr new int[200];//运用双指针模拟队列边界int l 0;int r 0;public MyQueue() {}public void push(int x) {arr[r] x;}public int pop() {return arr[l];}public int peek() {return arr[l];}public boolean empty() {return (lr);}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* boolean param_4 obj.empty();*/ 2.用队列模拟栈
题目链接:225. 用队列实现栈 - 力扣LeetCode
题面
基本分析数组模拟并用一个指针表示头
class MyStack {//利用数组模拟栈int[] arr new int[200];//定义head表示头int head 0;public MyStack() {}public void push(int x) {arr[head] x;}public int pop() {return arr[head--];}public int top() {return arr[head];}public boolean empty() {return head0;}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/ 3.有效的括号
题目链接20. 有效的括号 - 力扣LeetCode
题面:
基本分析模拟一个栈字符依次入栈当栈头元素和要入栈的元素匹配时头出栈而要入栈的元素不入栈
代码
class Solution {public boolean isValid(String s) {int n s.length();if(n%21)return false;int head 0;char[] stack new char[10005];for(char c:s.toCharArray()){if(stack[head](c))head--;else if(stack[head][c])head--;else if(stack[head]{c})head--;else stack[head] c;}return head0;}
} 4.删除字符串中所有相邻重复项
题目链接1047. 删除字符串中的所有相邻重复项 - 力扣LeetCode
题面: 基本分析:这题和上一题思路一样
代码:
class Solution {public String removeDuplicates(String s) {char[] arr new char[100005];int head0;for(char c:s.toCharArray()){if(arr[head]c)head--;else arr[head]c;}return new String(arr,1,head);}} 5.逆波兰表达式求值
题目链接150. 逆波兰表达式求值 - 力扣LeetCode
题面:
基本分析 我们将得到的数字以此压入栈中每次拿到运算符时取两个数进行运算然后把运算结果再次存入栈中
代码:
class Solution {public int evalRPN(String[] tokens) {long[] arr new long[10005];int head 0;int n tokens.length-1;for(int i 0;in;i){long number Integer.MAX_VALUE;char c ;try {number Integer.valueOf(tokens[i]);} catch (Exception e) {number Integer.MAX_VALUE;c tokens[i].toCharArray()[0];}if(number!Integer.MAX_VALUE)arr[head]number;else{if(c){arr[head-1] arr[head]arr[head-1];}else if(c-){arr[head-1] arr[head-1]-arr[head];}else if(c*){arr[head-1] arr[head-1]*arr[head];}else{arr[head-1] arr[head-1]/arr[head];}head--;}}return (int)arr[1];}
} 6.滑动窗口最大值
题目链接:239. 滑动窗口最大值 - 力扣LeetCode
题面
基本分析: 这题用到单调队列队列元素不完全递减每次加入新元素要判断队列头元素有没有过期然后从右边删去所有小于新加入元素的元素然后把新元素加入每次窗口的最大值就是队列的最左边元素当然未形成窗口前要另外单独讨论代码如下:
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;int[] queue new int[100010];int count 0;int l 0;int r 0;queue[0] Integer.MIN_VALUE;int[] arr new int[n-k1];for(int i -k1,j0;jn;i,j){if(i1){while(lrqueue[0]!-100006queue[r-1]nums[j])r--;queue[r]nums[j];if(i0)arr[count]queue[l];}else{if(queue[l]nums[i-1])l;while(lrqueue[r-1]nums[j])r--;queue[r]nums[j];arr[count]queue[l];}}return arr;}
} 7.前k个高频元素
题目链接:347. 前 K 个高频元素 - 力扣LeetCode
题面:
基本分析 因为涉及到排序可以使用优先队列(如果你不懂这个数据结构可以去了解一下简单来说就是你用这个可以把队列里的数据排好序每次取都是队列里的最值)
代码:
class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger,Integer map new HashMap();for(int num:nums){map.put(num,map.getOrDefault(num,0)1);}PriorityQueueMap.EntryInteger,Integer queue new PriorityQueue((a,b)-b.getValue()-a.getValue());queue.addAll(map.entrySet());int[] result new int[k];for(int i 0;ik;i){result[i] queue.poll().getKey();}return result;}
} 后言
上面是栈与队列一些最经典的题目以后碰到其他好题也会更新希望有所帮助一同进步共勉
