LeetCode20 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
- 输入: "()"
- 输出: true
示例 2:
- 输入: "()[]{}"
- 输出: true
示例 3:
- 输入: "(]"
- 输出: false
示例 4:
- 输入: "([)]"
- 输出: false
示例 5:
- 输入: "{[]}"
- 输出: true
思路：
括号不匹配。三种情况：多左括号，多有括号，括号类型不匹配。
往栈中放对应括号的匹配类型，遇到( 在栈放入),之后遇到)的时候消除掉即可，如果有剩余待匹配，说明左括号多了。
如果遇到的是别的类型的括号，说明不匹配。
如果遇到栈匹配空，说明多了有括号
也就是说，左右两种类型的括号，保留一种进行消消乐即可。
代码：
class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
//碰到左括号，就把相应的右括号入栈
if (ch == '(') {
deque.push(')');
}else if (ch == '{') {
deque.push('}');
}else if (ch == '[') {
deque.push(']');
} else if (deque.isEmpty() || deque.peek() != ch) {
return false;
}else {//如果是右括号判断是否和栈顶元素匹配
deque.pop();
}
}
//最后判断栈中元素是否匹配
return deque.isEmpty();
}
}
LeetCode 1047 删除字符串中所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
- 输入："abbaca"
- 输出："ca"
- 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
思路：
不断地遍历字符串，把遍历过的元素放入栈，当前遍历元素和栈顶元素进行比较，如果相同就弹出。
不断地重复遍历结束后，保留的字符串就是相邻没有重复的字符串。
本题提示相邻不重复，重点在相邻两个字。想到用栈数据结构去解决就很轻松。
代码：
class Solution {
public String removeDuplicates(String S) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}
拿字符串做栈：
class Solution {
public String removeDuplicates(String s) {
// 将 res 当做栈
StringBuffer res = new StringBuffer();
// top为 res 的长度
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
// 否则，将该字符 入栈，同时top++
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}
双指针：
class Solution {
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
// 直接用fast指针覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
if(slow > 0 && ch[slow] == ch[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(ch,0,slow);
}
}
标签：deque,ch,代码,随想录,括号,slow,Day11,字符串,top From： https://www.cnblogs.com/dwj-ngu/p/16830686.html