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

不念不忘少年蓝@ 2024-05-04 08:12 85阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

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

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

### 一、题目描述 ###

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

### 二、输入描述 ###

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

### 三、输出描述 ###

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

#### 1、输入 ####

#### 2、输出 ####

#### 3、说明 ####

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

### 四、解题思路 ###

1、list倒序循环中

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

2、栈Stack

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

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

### 六、效果展示 ###

#### 1、输入 ####

nezhaahZe

#### 2、输出 ####

#### 3、说明 ####

![在这里插入图片描述][0ef6da0ea2964cb88844e45f70c1c9b6.bmp_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

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

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/04/1c1c312806f746eba2ff4c7f1d39fb1f.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[0ef6da0ea2964cb88844e45f70c1c9b6.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/0ef6da0ea2964cb88844e45f70c1c9b6.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/04/0607e89282924640a843de272436a66b.gif