此篇文章与大家分享关于栈相关的算法
如果有不足的或者错误的请您指出!
目录
- 1.删除字符中的所有相邻重复项
- 1.1解析
- 1.2题解
- 2.比较含退格的字符串
- 2.1解析
- 2.2题解
- 3.基本计算器II
- 3.1解析
- 3.2题解
- 4.字符串解码
- 4.1解析
- 4.2题解
- 5.验证栈序列
- 5.1解析
- 5.2题解
1.删除字符中的所有相邻重复项
题目:删除字符中所有重复项
1.1解析
我们在遍历给定字符串的时候,当前这个元素是否要删除,是由它的前一个元素决定的,如果前一个元素和它相同,那么就删除,反之不删除
而栈的"后进先出"特性就恰好能够满足这类特性
即我们在遍历字符串的时候,判断当前这个元素是不是和栈顶元素相同,如果一样就取出栈顶元素,不一样就把这个元素放到栈里面
但是如果我们真的创建了栈,到时候还需要把字符一个个从栈里面拿出来
不如直接用字符串来模拟栈,直接在字符串上面进行拼接和删除操作
1.2题解
class Solution {
public String removeDuplicates(String ss) {
StringBuffer ret = new StringBuffer();
char[] s = ss.toCharArray();
for(char ch : s){
if(ret.length() != 0 && ch == ret.charAt(ret.length()-1)){
ret.deleteCharAt(ret.length()-1);
}else {
ret.append(ch);
}
}
return ret.toString();
}
}
2.比较含退格的字符串
题目:比较含退格的字符串
2.1解析
因为"退格"需要知道前一个元素的信息,因此也满足栈"后进先出"的特性
因此我们遍历字符串的时候,如果是字符,就直接放入栈里,如果是’#’,就删除栈顶元素
还是和上一道题一样,我们用字符串来模拟栈
2.2题解
class Solution {
public static boolean backspaceCompare(String s, String t) {
return backspace(s).equals(backspace(t));
}
private static String backspace(String ss){
char[] s = ss.toCharArray();
int n = s.length;
StringBuffer ret = new StringBuffer();
for(char ch : s){
if(ch == '#'){
if(ret.length() > 0){
ret.deleteCharAt(ret.length()-1);
}
}else{
ret.append(ch);
}
}
return ret.toString();
}
}
3.基本计算器II
题目:基本计算器II
3.1解析
这道题相比(基本计算器I)来说比较简单,因为不涉及括号
我们遍历题目给定字符串,由于 * / 的优先级是大于 + -的,因此我们遍历数字的时候就会出现4种情况
如果数字前面的字符是’+’,那么这一个数是否现在该被计算是不确定的,因此就要将这个数放入栈中
如果这个数字前面的符号是’-’,那么这一个数是否现在该被计算也是不确定的,因此就要将这个数的相反数放入栈中
如果这个数前面的符号是’*’,那么由于优先级最高,就可以将栈顶元素与这个数相乘,得到的结果在放进栈中
如果这个数前面的符号是’ / ',那么由于优先级最高,就可以将栈顶元素除以这个数,得到的结果在放进栈中
遍历完数组后,再将栈中的元素相加即可得到答案
这样,就能模拟出计算的过程
关于基本计算器I以及其拓展在我的个人主页前缀表达式转中缀表达式有提及
3.2题解
class Solution {
public int calculate(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
char op = '+';
int i = 0;
Stack<Integer> stack = new Stack<>();
while(i < n){
char ch = s[i];
if(ch == ' '){
i++;
}else if(Character.isDigit(ch)){
int tmp = 0;
while(i < n && Character.isDigit(s[i])){
tmp = tmp * 10 + (s[i++] - '0');
}
if(op == '+'){
stack.push(tmp);
}else if(op == '-'){
stack.push(-tmp);
}else if(op == '*'){
stack.push(stack.pop() * tmp);
}else{
stack.push(stack.pop() / tmp);
}
}else{
op = ch;
i++;
}
}
int ret = 0;
while(!stack.isEmpty()){
ret += stack.pop();
}
return ret;
}
}
4.字符串解码
题目:字符串解码
4.1解析
这道题我们在遍历字符串的时候要注意两个信息
(1)’['之前的数字
(2)[]之间的字符串
因此我们要搞两个栈来存储这两个信息
我们用一个包含所有的可能例子来解释
我们用i来遍历字符串
当我们遇到数字的时候,就直接将数字放在栈里面
遇到’[‘的时候,就将’[‘后面的字符串放进栈里
接下来还是数字和[:
当遇到’]'的时候,此时就要将字符串栈顶的字符串复制n遍,n是数字栈顶的数字
注意此时不是将复制完后的字符串放到栈里面去,而是将得到的字符串与栈顶字符串进行拼接
再次遇到],就按照我们上面的复制拼接操作,但是此时拿出字符串后,栈里面为空,复制完拼接的时候就会抛出栈为空的异常,我们可以直接在栈底放一个空字符串,将复制完后的结果直接拼接在空字符串后面即可
当直接遇到字符的时候,说明此时是单独的字符串,直接拼接即可
再次遇到数字和[,按照我们上面操作即可
4.2题解
class Solution {
public static String decodeString(String ss) {
Stack<String> stack1 = new Stack<>();
stack1.add("");
Stack<Integer> stack2 = new Stack<>();
char[] s = ss.toCharArray();
int i = 0;
int n = s.length;
while(i < n){
char ch = s[i];
if(Character.isDigit(ch)){
int tmp = 0;
while(i < n && Character.isDigit(s[i])){
tmp = tmp * 10 + (s[i++] - '0');
}
stack2.add(tmp);
} else if (ch == '[') {
i++;
StringBuffer tmp = new StringBuffer();
while (i < n && Character.isLowerCase(s[i])){
tmp.append(s[i++]);
}
stack1.add(tmp.toString());
} else if (ch == ']') {
int num = stack2.pop();
String str = stack1.pop();
StringBuffer tmp = new StringBuffer(stack1.pop());
while (num-- > 0){
tmp.append(str);
}
stack1.add(tmp.toString());
i++;
} else {
StringBuffer tmp = new StringBuffer();
while (i < n && Character.isLowerCase(s[i])){
tmp.append(s[i++]);
}
StringBuffer str = new StringBuffer(stack1.pop());
str.append(tmp);
stack1.add(str.toString());
}
}
return stack1.pop();
}
}
5.验证栈序列
题目:验证栈序列
5.1解析
思路比较简单,我们只需要自己模拟入栈的过程,每次入栈后都判断入栈元素与出栈元素是否相等,相等则出栈
等到入栈完后,判断出栈数组是否遍历完即可
5.2题解
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int i = 0;
Stack<Integer> stack = new Stack<>();
for(int x : pushed){
stack.push(x);
while(!stack.isEmpty() && popped[i] == stack.peek()){
i++;
stack.pop();
}
}
return i == popped.length;
}
}
