算法练习笔记——栈的常用方法以及算法练习
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
常用方法介绍
Stack<Character> characters = new Stack<>();
//判断栈是否为空
boolean empty = characters.empty();
//将a压入栈底同时也返回a
Character push = characters.push('a');
//返回栈顶的元素但是并不会删除它
Character peek = characters.peek();
//返回栈顶的元素并将它删除
Character pop = characters.pop();
//在堆栈中搜索a如果发现了则返回它相对于栈顶
//的偏移量。否则返回-1。
int search = characters.search('a');
boolean empty1 = characters.isEmpty();
力扣练习
力扣 20. 有效的括号
解法一
class Solution {
Stack<Character> characters = new Stack<>();
public boolean isValid(String s) {
char[] chars = s.toCharArray();
for(int i=0;i<s.length();i++)
{
if(chars[i]=='(') characters.push(')');
else if(chars[i]=='{') characters.push('}');
else if(chars[i]=='[') characters.push(']');
else if(characters.isEmpty()||chars[i]!=characters.pop()) return false;
}
return characters.isEmpty();
}
}
思路
利用到了栈的后入先出的特性
利用左半边的进行判断。如果与之对应就将对应的入栈下次如果不是左边的就将栈里面的与之比较相同出栈。
力扣 32. 最长有效括号
class Solution {
public int longestValidParentheses(String s) {
int maxans=0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
if(s.length()==0||s.length()==1){
return 0;
}
char[] chars = s.toCharArray();
for(int i=0;i<s.length();i++){
if(chars[i]=='(') stack.push(i);
else{
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}
else{
maxans = Math.max(maxans, i-stack.peek());
}
}
}
return maxans;
}
}
思路分析
首先我的第一反应是用栈当遇到时将其入栈遇到时将栈顶元素弹出这样可以实现的匹对
但是需要的是找出记录出长度和找出最长字符串
我们先定义一个maxans 即最长字符串
接下来我们需要找出最长字符串
我们可以先将字符串转为数组利用其元素下标求出最长字符串
思路就是我们可以将元素下标入栈记录下最后一个不匹配的元素下标这样两次做差就可以求出在每一次都用数学函数找出最大的数据记录
由于第一次没有元素我们可以先将-1入栈