蓝桥杯（和栈相关的算法题目）

1.题目概述解释

找出来这个字符串里面重复出现的字符，类似于这个消消乐的游戏；

示例一里面的这个bb是连续的并且是一样的这个字符，因此删除bb，删除之后发现这个aa有一次相邻了，所以这个aa也需要删除，以此类推下去，最后返回的是我们的这个字符串里面的剩余的内容；

这个可以使用栈这个数据结构进行模拟，下面简单的说明一下；

fig:

2.思路分析

1. 把a放到栈里面去；
2. b放进去，发现和这个时候栈顶元素a不一致，直接进入；
3. 第三个元素放进去，发现这个时候栈顶的元素和他一样，这个时候删除的是我们的栈顶元素，也就是弹出栈顶元素；
4. 这个时候栈里面只剩下了a元素；
5. c进入，发现和这个时候的栈顶元素不一样，直接进入；
6. 第二个c进去的时候发现等于栈顶元素，此时栈顶元素弹出即可；
7. 这个时候再次只剩下了a元素在我们的容器里面；
8. 这个时候进来了一个a，和我们的栈顶元素一样，弹出；
9. 这个时候的容器里面没有任何元素了；
10. bd按照上面的这个过程依次进入，最后这个容器里面的这个bd就是我们需要返回的；
11. 上面的这个就是使用栈进行模拟的整个流程，接下来我们看一下这个编码实现；
12. 编码实现的过程中，我们是使用的数组这个进行模拟，不需要真实的栈，让这个新的元素和我们的这个字符串里面的最后一个元素比较，最后这个字符串里面的元素就是我们需要返回的内容；

fig:

3.代码解析

1. ret用来存储我们的最后结果；
2. 因为需要遍历，所以我们把这个参数string转换为字符数组，这样才可以使用范围for进行遍历数组；
3. for循环里面判断这个ret里面的元素个数（不可以是空的），因为我们后面有-1的操作，空的话不用比较，直接放进去就可以了；
4. 不是空的话，就让这个新的元素和我们的这个字符串里面的最后一个元素比较，相同就弹出，不同就append进去；
5. 最后把这个ret转换为数组就可以了；

class Solution { public String removeDuplicates(String _s) { StringBuffer ret = new StringBuffer(); char[] s=_s.toCharArray(); for(char ch:s){ if(ret.length()>0&&ch==ret.charAt(ret.length()-1)){ ret.deleteCharAt(ret.length()-1); } else{ ret.append(ch); } } return ret.toString(); } }