首页云计算数据结构（Java）：力扣Stack集合OJ题

数据结构（Java）：力扣Stack集合OJ题

时间2024-07-25 03:36:44发布ongwu分类云计算浏览47

1、括号匹配问题

. - 力扣（LeetCode）

1.1 思路分析

根据栈的先进后出原则，我们可以这样解决问题：

遍历字符串，遇见左括号就将左括号push入栈；遇见右括号就pop出栈，将出栈的元素和该右括号比较是否匹配，若匹配则继续遍历并比较，若不匹配则直接返回false。细分为以下几种情况：

1.匹配（左右括号数量相同且匹配）：字符串遍历完，且栈为空（右括号与左括号数量相等，且均匹配），则说明括号匹配，返回true。

2.不匹配（括号不匹配）：遍历到的右括号和出栈的左括号比较是否匹配，一旦不匹配，立即返回false。

3.不匹配（左括号数量多）：当字符串遍历完后，发现栈还不为空，则说明左括号多，不匹配。

4.不匹配（右括号多）：遍历遇见右括号需将栈顶的左括号出栈，若要出栈时栈为空，则说明右括号多，不匹配。

1.2 代码

public boolean isValid(String s) {
//利用栈先进后出特点 解决问题
Stack<Character> stack = new Stack<>();
//遍历字符串
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//若为左括号 将括号入栈
if(ch == ( || ch == { || ch == [) {
stack.push(ch);
}else {//遍历到的为右括号 进入else
//若栈为空 则说明右括号多 立即返回false
if(stack.isEmpty()) {
return false;
}
//若栈不为空 则pop出栈 比较是否匹配
char ch2 = stack.pop();
switch(ch) {//使用switch语句比较是否匹配 一旦不匹配 立即返回false
case ):
if(ch2 != () {
return false;
}
break;
case ]:
if(ch2 != [) {
return false;
}
break;
case }:
if(ch2 != {) {
return false;
}
break;
}
}
}
//遍历完成且栈为空 则说明匹配
if(!stack.isEmpty()) {
return false;
}
return true;
}

2、栈的弹出、压入序列

2.1 思路分析

以i遍历pushV,每次都将将i下标的元素入栈

，再将栈顶元素和j下标元素比较，

若相等：则出栈，j++，i++

不相等：则i++，j保持原位

注意：j++后，j下标与栈顶元素可能依然相等，此时要连续出栈。即j变化后，要继续和栈顶元素比较。

i遍历完成，且j也遍历也完成（此时栈肯定为空），说明出栈序列匹配若i遍历完成后，j还没有遍历完成（栈不为空），则说明出栈序列不匹配

因为只有栈顶元素和j下标元素相等时，才会出栈，j++

 2.2 代码

public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushV.length; i++) {
//每次循环都会将pushV中i下标的元素入栈
stack.push(pushV[i]);
//因为j++后，元素可能连续出栈，所以要while循环
//出栈后，栈可能出现空的情况，!stack.isEmpty()，防止出现空指针异常
while (!stack.isEmpty() && stack.peek() == popV[j]) {
j++;
//若j下标和栈顶元素相同，则出栈
stack.pop();
}
}
//i遍历完成，若此时j也遍历完成（j == popV.length）,则说明出栈序列匹配
return j == popV.length;
}

3、逆波兰表达式（后缀表达式）求值

. - 力扣（LeetCode）

3.1 逆波兰表达式的定义

逆波兰表达式，也称为后缀表达式，是一种表达式的表示方法，其中运算符位于操作数之后。

后缀表达式由中缀表达式转化而来，可以实现表达式的求值和计算，提高了计算机内存访问的效率。而中缀表达式就是我们平时做运算的表达式。

那么如何将中缀表达式转换为后缀表达式？

从左向右，以先乘除后加减的次序加括号将括号中的相邻两项的运算符拿到括号的后面去掉所有括号

 3.2 后缀表达式如何求值（思路分析）

我们拿到后缀表达式后，

遍历表达式，若是非操作符元素（数字元素），则入栈若遇到操作符元素，则出栈两次，将第一次出栈的元素val2作为该操作符的右操作数，将第二次出栈的元素val1作为该操作符的左操作数，接着将所得结果入栈。继续遍历，并重复以上操作遍历完成后，栈中只剩一个元素，该元素就是后缀表达式的值。

 3.3 代码

class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String str = tokens[i];
if (!isOperator(str)) {
//如果不是是操作符
//则元素入栈
int val = Integer.parseInt(str);//将字符串转化为整型
stack.push(val);
} else {
//如果是操作符
//则弹出栈顶两个元素
//计算结果，并将结果入栈
int val2 = stack.pop();
int val1 = stack.pop();
if (str.equals("+")) {
stack.push(val1 + val2);
}
if (str.equals("-")) {
stack.push(val1 - val2);
}
if (str.equals("*")) {
stack.push(val1 * val2);
}
if (str.equals("/")) {
stack.push(val1 / val2);
}
}
}
//遍历完成后，栈中还有一个元素
//该元素就是后缀表达式的值
return stack.pop();
}
//判断该元素是否为操作符
private boolean isOperator(String str) {
if (str.equals("+") || str.equals("-")
|| str.equals("*") || str.equals("/")) {
return true;
}
return false;
}
}

4、最小栈

. - 力扣（LeetCode）

4.1 思路分析

题目要求我们在O（1）内找到栈中的最小值，

而在Java已有的一个栈中我们只能通过遍历找最小值，时间复杂度为为O（n） 。

所以，我们可以建立两个栈，一个栈dataStack用来存储元素，另一个栈minStack的栈顶存最小值。

minStack栈顶存储最小值数据 每次dataStack添加新数据时，和minStack栈顶元素比较，若<= ，则push入栈（一定要 <= ，因为dataStack中可能有多个相同的最小值，保证pop一次后，minStack依然存储着最小值）当minStack为空时，那么dataStack添加的元素（第一次入栈的元素）一定为最小值当dataStack弹出元素时，我们需要判断这个元素是否为minStack的栈顶元素（最小值），若是，也需要弹出minStack的元素

也就是说， minStack的栈顶元素，就是dataStack的最小值。

4.2 代码

class MinStack {
Stack<Integer> dataStack;//存储所有数据
Stack<Integer> minStack;// 栈顶存储最小值数据 每次添加新数据时，和minStack栈顶元素比较，若<= ，则push进minStack
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
dataStack.push(val);
if (minStack.isEmpty()) {
// 当minStack为空时，直接push进minStack
minStack.push(val);
} else {// 一定要有else 否则，minStack空时，同一个元素会在minStack中push两次
if (val <= minStack.peek()) {
// 一定要 <= ，因为dataStack中可能有多个相同的最小值，保证pop一次，minStack依然存储着最小值
minStack.push(val);
}
}
}
public void pop() {
// 操作总是在 非空栈 上调用
int val = dataStack.pop();
// 当dataStack栈顶元素为最小值时，也要弹出minStack的栈顶元素
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return dataStack.peek();
}
public int getMin() {
// minStack的栈顶元素即为最小值
return minStack.peek();
}
}

Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！

展开全文READ MORE
UDP怎么实现可靠传输 小白的OS Copilot 产品测评

游客 回复需填写必要信息
↑