华为OD机试 - 字符串消除 - 栈Stack（Java 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

游戏规则：输入一个只包含英文字母的字符串, 字符串中的两个字母如果相邻且相同,就可以消除。在字符串上反复执行消除的动作, 直到无法继续消除为止,此时游戏结束。输出最终得到的字符串长度。

二、输入描述

输入原始字符串str 只能包含大小写英文字母,字母的大小写敏感, str长度不超过100

三、输出描述

输出游戏结束后，最终得到的字符串长度。

1、输入

2、输出

3、说明

gg可以直接消除得到空串长度为0

四、解题思路

1、list倒序循环中

利用list倒序循环中可以删除元素的特性，删除相邻的相同字符。
如果循环后，有字符抵消，则递归。

2、栈Stack

定义Stack，存储没有抵消的字符
栈顶元素和当前元素一致，则抵消
不一致，则加入栈
输出栈的大小即结果

五、Java算法源码

1、list倒序循环中

public class Test00 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();// 利用list倒序循环中可以删除元素的特性，删除相邻的相同字符List<Character> list = new ArrayList<>();for (int i = 0; i < str.length(); i++) {Character ch = str.charAt(i);list.add(ch);}dfs(list, list.size());System.out.println(list);}private static void dfs(List<Character> list, int preSize) {// 如果剩一个字符则无需再比较if (list.size() <= 1) {return;}// 利用list倒序循环中可以删除元素的特性，删除相邻的相同字符for (int i = list.size() - 1; i > 0; i--) {// 当前字符Character cur = list.get(i);// 前一个字符Character pre = list.get(i - 1);if (cur == pre) {list.remove(i);list.remove(i - 1);break;}}// 如果循环后，有字符抵消，则递归if (preSize != list.size()) {dfs(list, list.size());}}
}

2、栈Stack

public class Test01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();// 存储没有抵消的字符Stack<Character> stack = new Stack<>();for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);// 栈顶元素和当前元素一致，则抵消if(!stack.isEmpty() && stack.peek() == c){stack.pop();}else {// 不一致，则加入栈stack.add(c);}}// 输出栈的大小System.out.println(stack.size());}
}