蓝桥杯关于栈这个数据结构的一个算法题目

发布于:2025-03-21 ⋅ 阅读:(36) ⋅ 点赞:(0)

1.题目概述解释

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

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

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

image-20250320195040291

2.思路分析

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

image-20250320200515303

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();
    }
}

网站公告

今日签到

点亮在社区的每一天
去签到