✅作者简介：大家好我是烫嘴的辛拉面，大家可以叫我拉面。🐭🐭
📜个人主页: weixin_49405762的博客
📕系列专栏： 经典算法习题集
🌞为大🔥推荐一款刷题神器哦 👉点击跳转进入网站
☀️前言：从今天开始一个新的专栏 经典算法习题集，整理牛客网经典算法的习题练习，我将用java语言来解题。牛客网除了算法题单之外还有其他热门的各种提单，应有尽有，大家快刷起来吧点击跳转进入牛客网
目录
✏️数据结构
✒️AB1[模板]栈
题目描述
请你实现一个栈。
操作：
push x：将 加x x\ x 入栈，保证 x x\ x 为 int 型整数。
pop：输出栈顶，并让栈顶出栈
top：输出栈顶，栈顶不出栈
输入描述：
第一行为一个正整数 n n\ n ，代表操作次数。(1≤n≤100000)(1 \leq n \leq 100000)(1≤n≤100000)
接下来的 n n\ n ，每行为一个字符串，代表一个操作。保证操作是题目描述中三种中的一种。
输出描述：
如果操作为push，则不输出任何东西。
如果为另外两种，若栈为空，则输出 "error“
否则按对应操作输出。
示例1
输入： 6
push 1
pop
top
push 2
push 3
pop
输出：1
error
3
解题思路
首先看清题目要求，并且根据栈先进后出的特性解决题目 1.用到头文件include这样可以省去建栈等操作，除此之外包含有多种函数 2.将题目分为三种情况，可用if,else语句进行分类，继而进行更进一步划分 3.注意L.pop()用于栈顶的清除，并非用于输出,输出有L.top()函数。
代码实现(Java)
import java.util.Scanner;//自己做了个栈，不过没做太多校验publicclassMain{publicstaticvoidmain(String args[]){Scanner sc =newScanner(System.in);int size = Integer.valueOf(sc.nextLine());Stack stack =newStack(size);String tempStr;String[] tempArr;for(int i =0;i<size;i++){
tempStr = sc.nextLine();
tempArr = tempStr.split(" ");if(tempArr[0].equals("push")){
stack.push(Integer.valueOf(tempArr[1]));}elseif(tempArr[0].equals("top")){
stack.top();}else{
stack.pop();}}}}classStack{int[] stackSpace;staticint index =-1;Stack(int size){
stackSpace =newint[size];}publicvoidpush(int number){
stackSpace[++index]= number;}publicvoidpop(){if(index ==-1){
System.out.println("error");}else{
System.out.println(stackSpace[index--]);}}publicvoidtop(){if(index ==-1){
System.out.println("error");}else{
System.out.println(stackSpace[index]);}}}
✒️AB2 栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
示例1
输入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
说明：可以通过 push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false
解题思路
题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。
具体做法
step 1：准备一个辅助栈，两个下标分别访问两个序列。
step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
step 3：栈顶等于出栈数组当前元素就出栈。
step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。
图示
代码实现(Java)：
import java.util.Stack;publicclassSolution{publicbooleanIsPopOrder(int[] pushA,int[] popA){int n = pushA.length;//辅助栈Stack<Integer> s =newStack<>();//遍历入栈的下标int j =0;//遍历出栈的数组for(int i =0; i < n; i++){//入栈：栈为空或者栈顶不等于出栈数组while(j < n &&(s.isEmpty()|| s.peek()!= popA[i])){
s.push(pushA[j]);
j++;}//栈顶等于出栈数组if(s.peek()== popA[i])
s.pop();//不匹配序列elsereturnfalse;}returntrue;}}
✒️AB3 有效括号序列
题目描述
给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。
数据范围：字符串长度 0≤n≤100000\le n \le 100000≤n≤10000
要求：空间复杂度 O(n)O(n)O(n)，时间复杂度 O(n)O(n)O(n)
示例1
输入：“()[]{}”
返回值：true
示例2
输入：“[]”
返回值：true
示例3
输入：“([)]”
返回值：false
题目主要信息
给定一个只包含大中小左右括号的字符串，判断其中括号是否合法
中小括号的数学顺序与合法无关，只需要每种左括号在右边有相应匹配的右括号即可，不可交叉匹配，应该是括号嵌套
解题思路：
括号的匹配规则应该符合先进后出原理：最外层的括号即最早出现的左括号，也对应最晚出现的右括号，即先进后出，因此可以使用同样先进后出的栈：遇到左括号就将相应匹配的右括号加入栈中，后续如果是合法的，右括号来的顺序就是栈中弹出的顺序。
具体做法
step 1：创建辅助栈，遍历字符串。
step 2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的呦括号加入栈中，期待在后续遇到。
step 3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。
step 4：其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历。
step 5：理论上，只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判断是否合法。
图示
代码实现(java)
import java.util.*;publicclassSolution{publicboolean isValid (String s){//辅助栈Stack<Character> st =newStack<Character>();//遍历字符串for(int i =0; i < s.length(); i++){//遇到左小括号if(s.charAt(i)=='(')//期待遇到右小括号
st.push(')');//遇到左中括号elseif(s.charAt(i)=='[')//期待遇到右中括号
st.push(']');//遇到左打括号elseif(s.charAt(i)=='{')//期待遇到右打括号
st.push('}');//必须有左括号的情况下才能遇到右括号elseif(st.isEmpty()|| st.pop()!= s.charAt(i))returnfalse;}//栈中是否还有元素return st.isEmpty();}}
✒️AB4 逆波兰表达式求值
题目描述
给定一个逆波兰表达式，求表达式的值。
数据范围：表达式长度满足 1≤n≤104 1 \le n \le 10^4 \ 1≤n≤104 ，表达式中仅包含数字和 + ，- , * , / ，其中数字的大小满足 ∣val∣≤200 |val| \le 200 \ ∣val∣≤200 。
示例1
输入：[“2”,“1”,“+”,“4”,“*”]
返回值：12
示例2
输入：[“2”,“0”,“+”]
返回值：2
解题思路
逆波兰表达式求值的过程可以借助栈来求解，在遍历数组的时候，判断当前是否是数字，如果是就压入栈中，不是说明遇到了运算符，从栈中弹出两个数字进行运算即可。
图示
代码实现(java)
import java.util.*;publicclassSolution{/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/publicint evalRPN (String[] tokens){// 栈Stack<Integer> stack =newStack<Integer>();// 长度int n = tokens.length;// 遍历for(int i =0; i < n; i++){String token = tokens[i];// 说明是数字，则押入栈if(isNumber(token)){
stack.push(Integer.parseInt(token));}// 说明遇到运算符else{// 弹出两个元素int num2 = stack.pop();int num1 = stack.pop();//判断+ - * /switch(token){case"+":
stack.push(num1 + num2);break;case"-":
stack.push(num1 - num2);break;case"*":
stack.push(num1 * num2);break;case"/":
stack.push(num1 / num2);break;default:}}}return stack.pop();}// 用于判断token是数字还是运算符publicbooleanisNumber(String token){return!("+".equals(token)||"-".equals(token)||"*".equals(token)||"/".equals(token));}}
✒️AB5 点击消除
题目描述
牛牛拿到了一个字符串。
他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？
输入描述：
一个字符串，仅由小写字母组成。（字符串长度不大于300000）
输出描述：
一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。
示例1
输入：abbc
输出：ac
示例2
输入：abba
输出：0
示例3
输入：bbbbb
输出：b
解题思路
分为两步来解决：
1.比较消除相同的字符
2.顺序输出不同的字符
步骤1：
遍历字符，放入栈中。当栈为空栈时(也就是遍历第一次字符的时候，此时栈为空)和栈顶元素和当前遍历的字符不相等时，将该字符放入栈中。
反之说明当前遍历的字符和栈顶字符是相同的，那么消除(移除)
步骤2：
判断栈是否为空，为空说明全部消除，不为空则顺序输出，因为栈是先进后出，这里要保证顺序的话，可以把当前栈的字符放入另外一个栈，然后再输出即保证顺序输出。
代码实现(java)
import java.util.Stack;publicclassSolution2{publicstaticvoidmain(String[] args){eliminate("tsirhvtujuzdnwprhoihkzvckc");
System.out.println();
System.out.println("-----------------");eliminate("abba");}/**
*
* @param s string字符串
* @return bool布尔型
*/publicstaticvoid eliminate (String s){if(s ==null|| s ==""){return;}char[] chars = s.toCharArray();Stack<Character> stack =newStack<>();for(int i =0;i<chars.length;i++){if(stack.isEmpty()|| stack.peek()!= chars[i]){
stack.push(chars[i]);}else{
stack.pop();}}if(stack.isEmpty()){
System.out.println("ok");}else{// 目的是为了顺序输出Stack<Character> stack2 =newStack<>();while(!stack.isEmpty()){
stack2.push(stack.pop());}while(!stack2.isEmpty()){
System.out.print(stack2.pop());}}}}
✒️AB6 表达式求值
题目描述
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：0≤∣s∣≤1000\le |s| \le 1000≤∣s∣≤100，保证计算结果始终在整型范围内
要求：空间复杂度： O(n)O(n)O(n)，时间复杂度 O(n)O(n)O(n)
示例1
输入：“1+2”
返回值：3
示例2
输入：“(2*(3-4))*5”
返回值：-10
示例3
输入：“3+234-1”
返回值：26
题目的主要信息
写一个支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级
支持括号运算
解题思路：
对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。
处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。
处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算：
终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。
返回值： 将括号内部的计算结果值返回。
本级任务： 遍历括号里面的字符，进行计算。
具体做法
step 1：使用栈辅助处理优先级，默认符号为加号。
step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
step 5：最后将栈中剩余的所有元素，进行一次全部相加。
图示
代码实现(java)
import java.util.*;publicclassSolution{publicArrayList<Integer>function(String s,int index){Stack<Integer> stack =newStack<Integer>();int num =0;char op ='+';int i;for(i = index; i < s.length(); i++){//数字转换成int数字//判断是否为数字if(s.charAt(i)>='0'&& s.charAt(i)<='9'){
num = num *10+ s.charAt(i)-'0';if(i != s.length()-1)continue;}//碰到'('时，把整个括号内的当成一个数字处理if(s.charAt(i)=='('){//递归处理括号ArrayList<Integer> res =function(s, i +1);
num = res.get(0);
i = res.get(1);if(i != s.length()-1)continue;}switch(op){//加减号先入栈case'+':
stack.push(num);break;case'-'://相反数
stack.push(-num);break;//优先计算乘号case'*':int temp = stack.pop();
stack.push(temp * num);break;}
num =0;//右括号结束递归if(s.charAt(i)==')')break;else
op = s.charAt(i);}int sum =0;//栈中元素相加while(!stack.isEmpty())
sum += stack.pop();ArrayList<Integer> temp =newArrayList<Integer>();
temp.add(sum);
temp.add(i);return temp;}publicint solve (String s){ArrayList<Integer> res =function(s,0);return res.get(0);}}
版权归原作者 烫嘴的辛拉面 所有， 如有侵权，请联系我们删除。