解题思路

  1. 使用栈来模拟消除过程:
    • 遍历字符串中的每个字符
    • 如果栈不为空且当前字符与栈顶字符相同,则消除(弹出栈顶)
    • 否则将当前字符入栈
  2. 最后栈中剩余的字符就是最终结果:
    • 如果栈为空,输出"0"
    • 否则将栈中字符拼接成字符串输出

代码

#include <bits/stdc++.h>
using namespace std;

string solve(string s) {
    stack<char> st;
    
    for(char c : s) {
        if(!st.empty() && st.top() == c) {
            st.pop();  // 如果当前字符与栈顶相同,消除
        } else {
            st.push(c);  // 否则入栈
        }
    }
    
    // 构建结果字符串
    string res = "";
    while(!st.empty()) {
        res = st.top() + res;
        st.pop();
    }
    
    return res.empty() ? "0" : res;
}

int main() {
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}
import java.util.*;

public class Main {
    public static String solve(String s) {
        Stack<Character> st = new Stack<>();
        
        for(char c : s.toCharArray()) {
            if(!st.empty() && st.peek() == c) {
                st.pop();
            } else {
                st.push(c);
            }
        }
        
        // 构建结果字符串
        StringBuilder res = new StringBuilder();
        while(!st.empty()) {
            res.insert(0, st.pop());
        }
        
        return res.length() == 0 ? "0" : res.toString();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(solve(s));
    }
}
def solve(s):
    st = []
    
    for c in s:
        if st and st[-1] == c:
            st.pop()
        else:
            st.append(c)
    
    return ''.join(st) or '0'

# 读取输入
s = input()
print(solve(s))

算法及复杂度分析

  • 算法:栈的基本操作
  • 时间复杂度:,其中是字符串长度
  • 空间复杂度:,最坏情况下需要存储整个字符串

注意事项

  1. 只能消除相邻的相同字符
  2. 需要处理空串的情况,输出 "0"
  3. 构建结果字符串时需要注意顺序
  4. 对于大规模输入,需要注意字符串拼接的效率