算法专题：栈
目录
1. 删除字符串中的所有相邻重复项
1.1 算法原理
解法: 使用栈模拟, 实现"消消乐"(使用字符串模拟栈)
满足以下任一条件入栈:
- 栈为空
- s[i]和栈顶元素不相同
满足以下条件出栈:
- s[i]和栈顶元素相同
1.2 算法代码
class Solution {
public String removeDuplicates(String s) {
// 字符串模拟栈结构
StringBuilder stack = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int len = stack.length();
// 栈为空 || ch 和栈顶元素不相同 => 入栈
if(len == 0 || stack.charAt(len - 1) != ch) stack.append(ch);
// ch 和栈顶元素相同 => 出栈
else stack.deleteCharAt(len - 1);
}
return stack.toString();
}
}2. 844. 比较含退格的字符串
2.1 算法原理
本题思路与第一题相同,
- 当 s[i] 为 '#' 时, 出栈
- 当 s[i] 不为 '#' 时, 入栈
- 最后比较经过退格处理后的两个字符串是否相同
2.2 算法原理
class Solution {
public boolean backspaceCompare(String s, String t) {
return strOpera(s).equals(strOpera(t));
}
public String strOpera(String s) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '#') {
// 出栈
if(stringBuilder.length() >= 1) stringBuilder.deleteCharAt(stringBuilder.length() - 1);
}
else {
// 入栈
stringBuilder.append(ch);
}
}
return stringBuilder.toString();
}
}3. 基本计算器 II
3.1 算法原理
解法: 利用栈模拟运算过程
分类讨论:
1. s[i] 是运算符 => op = s[i] (记录运算符)
2. s[i] 是数字字符 , 把数字提取出来: tmp += s[i] - '0' (可能s[i + 1]仍为数字字符, 需循环处理)
- op == '+' => stack.push(tmp);
- op == '-' => stack.push(-tmp);
- op == '*' => stack.push(stack.pop() * tmp);
- op == '/' => stack.push(stack.pop() / tmp);
3. 最终, 返回栈中所有元素的和
注意:
需要处理空格字符!!
3.2 算法代码
class Solution {
public int calculate(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
char op = '+';
int tmp = 0;
Stack<Integer> stack = new Stack<>();
int i = 0;
while(i < n) {
if(s[i] == ' ') {
i++;
}else if(isOperator(s[i])) {
op = s[i++];
}else {
tmp = s[i] - '0';
while(i + 1 < n && !isOperator(s[i + 1]) && s[i + 1] != ' ') {
tmp *= 10;
tmp += s[i + 1] - '0';
i++;
}
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);
i++;
}
}
int ret = 0;
for(int x : stack) ret += x;
return ret;
}
public boolean isOperator(char ch) {
if(ch == '+' || ch == '-' || ch == '*' ||ch == '/') return true;
return false;
}
}4. 字符串解码
4.1 算法原理
解法: 栈模拟
- 遇见数字 => 放入"数字栈"
- 遇见 '[' => 将 '[' 后的字母字符串提取出来, 放入 "字符串栈"
- 遇见 ']' => 取 "字符串栈" 栈顶元素和 "数字栈" 栈顶元素进行解析,并拼接到 "字符串栈" 栈顶元素后
- 遇见单独的字符串 => 拼接到 "字符串栈" 栈顶元素后
4.2 算法代码
class Solution {
public String decodeString(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
Stack<Integer> intStack = new Stack<>();
Stack<String> stringStack = new Stack<>();
// 预处理 => 当栈为空时
stringStack.push("");
int i = 0;
while(i < n) {
if(s[i] > '0' && s[i] < '9') {
int tmp = 0;
while(i < n && s[i] >= '0' && s[i] <= '9') {
tmp = tmp * 10 + (s[i++] - '0');
}
intStack.push(tmp);
}else if(s[i] == '[') {
i++;
StringBuilder sb = new StringBuilder();
while(i < n && s[i] >= 'a' && s[i] <= 'z') sb.append(s[i++]);
stringStack.push(sb.toString());
}else if(s[i] == ']') {
StringBuilder sb = new StringBuilder();
int x = intStack.pop();
String str = stringStack.pop();
while(x-- != 0) {
sb.append(str);
}
stringStack.push(stringStack.pop() + sb.toString());
i++;
}else {
StringBuilder sb = new StringBuilder();
while(i < n && s[i] >= 'a' && s[i] <= 'z') sb.append(s[i++]);
stringStack.push(stringStack.pop() + sb.toString());
}
}
return stringStack.pop();
}
}5. 验证栈序列
5.1 算法原理
解法: 使用 栈 模拟.
- 一边进栈, 一边判断是否需要出栈.
对 pushed 中的元素进行进栈操作, 将栈顶元素和 popped[i] 比较, 若不相等则一直进栈, 若相等则出栈, 并判断是否需要循环出栈.
5.2 算法代码
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int i = 0, n = popped.length;
for(int x : pushed) {
stack.push(x);
while(!stack.isEmpty() && stack.peek() == popped[i]) {
stack.pop();
i++;
}
}
return i == n;
}
}END
原文地址：https://blog.csdn.net/2401_83595513/article/details/143439077
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！