算法训练营（day11）
栈和队列理论基础
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）
20. 有效的括号
题目链接：https://leetcode.cn/problems/valid-parentheses/description/
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
解题思路
解题过程：
本题使用 队列 进行解答
将字符串中的所有 左括号 全部变成 右括号
将括号一个个放进队列中
如果字符串有效，最终队列应为空，否则为无效字符串
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public boolean isValid(String s) {
char cs;
Deque<Character> deque = new ArrayDeque<>();
if(s.length() % 2 == 1){
return false;
}
for(int i = 0; i < s.length(); i++){
cs = s.charAt(i);
if(cs == '('){
deque.push(')');
}else if(cs == '['){
deque.push(']');
}else if(cs == '{'){
deque.push('}');
}else if(deque.isEmpty() || deque.peek() != cs){
return false;
}else{
deque.pop();
}
}
return deque.isEmpty();
}
}
|
1047. 删除字符串中的所有相邻重复项
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
解题思路
解题过程：
这题的关键点：消除两个相邻的重复项后，重新相邻的两个项是否重复
所以使用 队列 的方式进行求解，避免漏项
解决思路主要是判断 队列的 peek() 节点 和 即将入列的节点 进行比较
- 相同，则将
peek() 节点弹出
- 不相同，则将 节点入列
返回新字符串
详细代码
解法一：使用双端队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public String removeDuplicates(String s) {
Deque<Character> deque = new ArrayDeque<>();
char cs;
for(int i = 0; i < s.length(); i++){
cs = s.charAt(i);
if(deque.isEmpty() || deque.peek() != cs){
deque.push(cs);
}else{
deque.pop();
}
}
String str = "";
while(!deque.isEmpty()){
str = deque.pop() + str;
}
return str;
}
}
|
解法二：使用字符串变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String removeDuplicates(String s) {
StringBuilder sb = new StringBuilder();
int top = -1;
for(int i = 0; i < s.length(); i++){
char cs = s.charAt(i);
if(top >= 0 && sb.charAt(top) == cs){
sb.deleteCharAt(top);
top--;
}else{
sb.append(cs);
top++;
}
}
return sb.toString();
}
}
|
解法三：双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String removeDuplicates(String s) {
char[] cs = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
cs[slow] = cs[fast];
if(slow > 0 && cs[slow] == cs[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(cs, 0, slow);
}
}
|
150. 逆波兰表达式求值
题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
解题思路
解题过程：
本题使用 栈 进行求解
题目的解题核心是：当出现运算符号时，将符号前的整数进行运算
使用栈，能很好的分清 减法 和 除法 的 首末（分子、分母），便于运算
- “+” ，栈依次弹出两个项进行相加
- “-“，减法需要注意先后，首个从栈弹出的值是 被减值
- “*”，栈依次弹出两个项进行相乘
- “/“，除法需要注意 分子分母，首个从栈弹出的值是 分母
- 其他数值的依次纳入栈即可
返回栈最后弹出的值
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String s : tokens){
if("+".equals(s)){
stack.push(stack.pop() + stack.pop());
}else if("-".equals(s)){
stack.push(-stack.pop() + stack.pop());
}else if("*".equals(s)){
stack.push(stack.pop() * stack.pop());
}else if("/".equals(s)){
int mom = stack.pop();
int son = stack.pop();
stack.push(son / mom);
}else{
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
|
