一、1047.删除字符串中的所有相邻重复项
题目链接：1047.删除字符串中的所有相邻重复项
题目描述：
题目解析：
- 字符串中相邻字符相同，就要删去，删去之后相邻字符相同也要删去
解题思路：
- 我们使用栈来存储，从前遍历字符串的字符。
- 拿到一个字符，就看栈顶元素是否相同，如果相同就出栈，不同就入栈
- 注意在看栈顶元素前，要看栈是不是空。
- 这里可以使用数组来代替栈。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public String removeDuplicates(String s) {
StringBuffer ret = new StringBuffer();
for(int i = 0; i < s.length(); i++) {
if(ret.length() > 0 && s.charAt(i) == ret.charAt(ret.length() - 1)) ret.deleteCharAt(ret.length() - 1);
else ret.append(s.charAt(i));
}
return ret.toString();
}
}
二、844.⽐较含退格的字符串
题目链接：844. ⽐较含退格的字符串
题目描述：
题目解析：
- 当字符串中是’#‘的时候就将前一个字符删去，删去之后再遇到’#'也要删去前一个字符。
- 判断两个字符串按照上面规则运算后，是否相同
解题思路
- 这根上一道题是一道题，只不过判断条件从前一个字符是否相等，变成了当前字符是不是’#'。
- 我们只需要封装一个方法进行删除就行，最后判断两个字符串调用了方法后是否内容相同即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public boolean backspaceCompare(String s, String t) {
return backspace(s).equals(backspace(t));
}
//返回处理#后的结果
public String backspace(String s) {
StringBuffer ret = new StringBuffer();
for(int i = 0; i < s.length(); i++) {
if(ret.length() > 0 && s.charAt(i) == '#') ret.deleteCharAt(ret.length() - 1);
if(s.charAt(i) != '#') ret.append(s.charAt(i));
}
return ret.toString();
}
}
三、227.基本计算器 II
题目链接：227.基本计算器 II
题目描述：
题目解析：
- 给我们一个字符串，其中只包含"加减乘除和数字和空格"几种字符
- 返回按照数学运算，计算后的数字，这个数字不会超过int范围
解题思路：
- 整体思路：将所有的运算符变成加
- 我们只需要将每个数字前面的运算符使用运算符变量记录下来，
- 当遍历到字符为空格就向后走
- 遍历到是运算符，就将运算符变量更新为这个运算符，向后走
- 遍历到数字，我们使用变量记录下来，再向后遍历看是不是数字，因为在这道题中123这种是三个字符连在一堆表示
- 当变量存储完之后，看前面的运算符变量是什么，是减，就将相反数入栈，是加，直接入栈，是乘和除，就拿栈顶元素进行运算后再入栈。
- 最后将栈中的元素加起来就是结果了。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
char op = '+';
int i = 0;
while(i <s.length()) {
if(s.charAt(i) == ' ') {
i++;
} else if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
int tmp = 0;
while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
tmp = tmp * 10 + (s.charAt(i) - '0');
i++;
}
if(op == '+') stack.push(tmp);
if(op == '-') stack.push(-tmp);
if(op == '*') stack.push(stack.pop() * tmp);
if(op == '/') stack.push(stack.pop() / tmp);
} else {
op = s.charAt(i);
i++;
}
}
int ret = 0;
while(!stack.isEmpty()) {
ret += stack.pop();
}
return ret;
}
}
四、394. 字符串解码
题目链接：394.字符串解码
题目描述：
题目解析：
- 中括号中的字符要重复中括号前面的数字倍
- 数字只会作为倍数出现
解题思路：
- 我们遍历字符串会出现四种情况：字母(指不被中括号包含的)、数字、左括号 ’ [ ’ 、右括号 ’ ] ’
- 我们要将数字与数字对应要重复的字符串对应起来，所以我们使用两个栈分别储存数字和字符串
- 遇到数字的时候，我们就将数字提取出来，放入数字栈中。使用循环遍历拿到每个数字字符（不用注意越界），加在个位即可
- 遇到左括号 ’ [ ’ 时，我们就将左括号和右括号中包含的字符串（不用注意越界因为一定有 ‘ ] ’）放入栈顶
- 遇到右括号 ’ ] ’ 时，我们就拿去两个栈的栈顶元素，重复字符串，拼接在现在的栈顶元素后。
- 遇到字母(指不被中括号包含的)时，拿取这个字符串（此时需要注意越界问题），拼接在现在的栈顶元素后。
- 因为有拼接在栈顶元素，如果字符串开始时就是字母(指不被中括号包含的)，那么会空指针异常，所以在一开始的字符串栈就填入一个空串。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public String decodeString(String s) {
Stack<StringBuffer> stackString = new Stack<>();
stackString.push(new StringBuffer());
Stack<Integer> stackInt = new Stack<>();
int cur = 0;
while(cur < s.length()) {
if(s.charAt(cur) >= '0' && s.charAt(cur) <= '9') { //数字
int tmp = 0;
while(s.charAt(cur) >= '0' && s.charAt(cur) <= '9')
tmp = tmp * 10 + (s.charAt(cur++) - '0');
stackInt.push(tmp);
} else if(s.charAt(cur) == '[') { //左括号 ' [ '
cur++;
StringBuffer tmp = new StringBuffer();
while(s.charAt(cur) >= 'a' && s.charAt(cur) <= 'z')
tmp.append(s.charAt(cur++));
stackString.push(tmp);
} else if(s.charAt(cur) == ']') { //右括号 ' ] '
cur++;
int k = stackInt.pop();
StringBuffer tmp = stackString.pop();
while(k-- != 0)
stackString.peek().append(tmp);
} else { // 字母(指不被中括号包含的)
while(cur < s.length() && s.charAt(cur) >= 'a' && s.charAt(cur) <= 'z')
stackString.peek().append(s.charAt(cur++));
}
}
return stackString.peek().toString();
}
}
五、946. 验证栈序列
题目链接：946. 验证栈序列
题目描述：
题目解析：
- 看popped数组是不是按照pushed数组元素入栈顺序能拿到的顺序
解题思路：
- 遍历pushed数组，元素入栈，如果pushed数组元素与当前popped数字的当前下标元素不同，就入栈
- pushed数组元素与当前popped数字的当前下标元素相同，就出栈直到栈顶元素与popped数字的当前下标元素不同或者栈空为止。
- 最后如果栈还有元素，那么就返回false，反之，返回true。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int cur = 0; //popped当前访问的下标
for(int i = 0; i < pushed.length; i++) {
if(pushed[i] != popped[cur])
stack.push(pushed[i]);
else {
stack.push(pushed[i]);
while(!stack.isEmpty() && stack.peek() == popped[cur]) {
stack.pop();
cur++;
}
}
}
return stack.isEmpty();
}
}