每日一题——删除字符串中的所有相邻重复项

删除字符串中的所有相邻重复项

题目链接

思路

• 这是一道用栈解决的典型题目
  
• 我们先来看看栈的基本性质：

• 栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端为栈底。
  
• 栈中的数据元素遵守后进先出原则
  
• 压栈：栈的插入操作称为进栈/压栈/入栈，其位置在栈顶
  
• 出栈：栈的删除操作称为出栈，其位置也在栈顶
  
  

• 这题其实和有效括号序列类似，都是对字符进行匹配，如果匹配成功那就进行删除
  
• 而这题匹配成功的条件就是相邻的两个字符是相等的，那么我们就可以用一个循环，来遍历整个字符串，然后再将每次遍历的字符和前一个字符进行比较，如果相等就删除。
  
• 那么，我们怎么保存遍历字符的前面一个元素呢？就是用的栈

• 遍历字符串，如果栈为空或遍历的字符与前面的不相等，那就将这个字符入栈
• 否则，如果与前面的字符（栈顶元素）相等，那就将栈顶元素出栈（即相当于匹配成功，将这两个字符删除）

• 我们以字符串“abbaca”为例，看一下完整的过程：
  
  

实现代码

char * removeDuplicates(char * s){
    int len = strlen(s);
    char* stack = (char *)malloc(sizeof(char) * (len + 1)); //申请返回的字符串的内存
    int top = 0;  //栈顶指针置零
    for(int i = 0; i < len; i++)
    {
        //如果栈不为空或遍历元素等于栈顶元素，出栈
        if(top > 0 && s[i] == stack[top - 1])
            top--;
        //否则，入栈
        else
            stack[top++] = s[i];
    }
    stack[top] = 0; //确定新字符串结束位置
    return stack; //返回新的字符串
}