每日一题(LeetCode)----栈和队列--删除字符串中的所有相邻重复项
----栈和队列--删除字符串中的所有相邻重复项)
每日一题(LeetCode)----栈和队列–删除字符串中的所有相邻重复项
1.题目（1047. 删除字符串中的所有相邻重复项）
-
给出由小写字母组成的字符串
S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。提示：
1 <= S.length <= 20000S仅由小写英文字母组成。
2.解题思路
思路一：使用栈
1.我们先创建一个栈
2.遍历一遍字符串，每遍历到一个字符，我们就将这个元素与栈顶元素进行比较 如果和栈顶元素一样，那么我们就删除栈顶元素，然后遍历下一个字符 如果和栈顶元素不一样，那么我们将当前元素放入到栈中，然后遍历下一个字 符 注意：如果栈中没有元素，那么我们直接将当前遍历到的元素放入栈中
3.把栈中元素放入到结果字符串中，然后返回结果字符串即可
思路二：双指针
1.我们先创建两根指针指向字符串的第一个元素和第二个元素
2.移动右指针，每移动一次，就判断当前两根指向的字符是否相等， 如果不相等左指针的下一个就变为右指针指向的字符，然后左指针向后移动一位， 如果相等左指针就向前移动一位 注意：当左指针左移之后不指向字符串中的元素时，下一次我们就直接让左指针的下一个就变为右指针指向的字符，然后左指针向后移动一位
3.使用resize函数将原有字符串进行缩小，得到结果子字符串
思路来源:Ecstatic Pasteur8rw
链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
3.写出代码
思路一的代码
class Solution {
public:string removeDuplicates(string s) {stack<char> qe;for (auto v : s) {if (qe.empty()) {qe.push(v);}else if(!qe.empty()) {if (qe.top() == v) {qe.pop();}else {qe.push(v);}}}string res="";if (!qe.empty()) {int length = qe.size();while (!qe.empty()) {res+= qe.top();qe.pop();}}reverse(res.begin(), res.end());return res;}
};
思路二的代码
class Solution {
public:string removeDuplicates(string s) {if(s.size()<2){return s;}int left=0;int right=1;int length=s.size();for(right=1;right<length;){if(left<0||s[left]!=s[right]){s[++left]=s[right];}else{left--;} right++;}s.resize(left+1);return s;}
};