栈(删除字符串中的所有相邻元素)(1)

一.题目1047. 删除字符串中的所有相邻重复项 - 力扣LeetCode二.思路讲解2.1 思路讲解首先这道题如果横着看可能不太容易想到解法但如果你竖着看是不是很像消消乐游戏在消消乐中当出现相同元素方块时我们需要手动点击消除。但这里会自动消除只要出现相邻的相同元素它们就会立即被消除然后上面的元素相当于方块就会掉下来填补空缺接着可能会引发新的相邻相同从而重复消除和下落的过程直到无法再消除为止。这种自动消消乐的机制实际上就是我们需要模拟的核心逻辑。我们可以借助栈这种数据结构来实现遍历原始序列每次将当前元素与栈顶元素比较如果相同则说明两者可以消除栈顶元素弹出相当于消除当前元素也不入栈如果不同则将当前元素压入栈中。这样一次遍历就完成了所有消除栈中剩余的元素就是最终结果。不改我们可以只借用栈的思想而不采取栈这个数据结构我们可以通过字符串来实现因为题目不是要返回字符串吗用字符串来实现其实就相当于我们用数组模拟哈希表一样三.代码演示class Solution { public: string removeDuplicates(string s) { int n s.size(); string ret ; ret s[0];//先把第一个元素加进去 int cur 0;//指向ret最右边的元素 for(int i 1; i n;i) { if(ret.size() 0 || ret[cur] ! s[i]) { ret s[i]; cur; } else { ret.pop_back();//删除最右边元素 cur--; } } return ret; } };四.代码讲解一、初始化结果字符串我们使用一个字符串ret来模拟栈它存储当前消除后的结果。首先将原字符串的第一个字符s[0]加入ret中作为初始栈底。同时定义一个指针cur指向ret的最后一个元素的下标即栈顶位置初始化为 0。二、遍历剩余字符从下标 i 1 开始遍历原字符串s的每一个字符。对于每个字符s[i]进行以下判断如果ret为空 或者 当前字符与栈顶字符不同即ret.size() 0 || ret[cur] ! s[i]说明当前字符不会与栈顶字符消除因此将其压入栈中即ret s[i]同时栈顶指针cur。否则说明当前字符与栈顶字符相同需要消除。此时将栈顶字符弹出即ret.pop_back()同时栈顶指针cur--。这样每次比较的都是当前字符与栈顶元素符合相邻消除的规则。三、返回结果遍历结束后ret中存储的就是所有无法被消除的字符即最终结果。直接返回ret即可。四、关键细节栈的模拟用string的尾端作为栈顶push_back相当于入栈pop_back相当于出栈非常直观。指针cur的作用用于快速访问栈顶元素避免每次都用ret.back()但这里其实也可以用ret.back()直接获取代码中自己维护了cur指针也是可行的。注意cur始终指向ret的最后一个字符下标。边界处理当ret为空时直接压入字符无需比较。