H-吐泡泡_ Java解法_牛客竞赛语法入门班数组栈、队列和stl习题

H 吐泡泡

题目

原题链接，可提交代码

题目描述

小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。）
例如:ooOOoooO经过一段时间以后会变成oO。

输入描述

数据有多组，处理到文件结束。
每组输入包含一行仅有’O’与’o’组成的字符串。

输出描述

每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

示例1
输入

ooOOoooO
1

输出

oO
1

说明
自左到右进行合并

备注

对于100%的数据，
字符串的长度不超过100。

---

题目大意

• 读入n行 包含 o 和 O 的字符串
• 两个相邻 o 可以合并成 一个 O
• 两个相邻 O 就消除
• 输出最后结果

---

解题思路

1. 使用栈来进行模拟
   由于小泡泡和大泡泡相邻时会融合，因此可以使用栈来模拟这个过程。遍历字符串，如果当前字符和栈顶字符相同，则融合，即将栈顶字符弹出；否则，将当前字符入栈。遍历完成后，栈中剩余的字符就是小鱼儿吐出的泡泡经过融合后所剩余的泡泡。
2. 不使用栈，直接在循环里处理
   使用循环遍历字符串的方式，通过不断地在字符串中查找相邻的小泡泡或大泡泡，然后进行融合或爆破的操作。

---

参考代码Java（栈）

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            Stack stack = new Stack<>(); // 创建一个字符类型的栈，用于模拟泡泡的融合过程
            String s = scanner.next(); // 读取输入的字符串
            int len = s.length(); // 字符串的长度
            
            // 遍历字符串中的每个字符
            for (int i = 0; i < len; i++) {
                stack.push(s.charAt(i)); // 将当前字符入栈

                // 当栈中元素个数大于1时，进行比较和融合的操作
                while (stack.size() > 1) {
                    char c = stack.pop(); // 弹出栈顶元素
                    char d = stack.pop(); // 弹出次顶元素

                    // 如果栈顶的两个元素相等且都为小泡泡"o"，则将它们融合成大泡泡"O"，并将大泡泡入栈
                    if (c == d && c == 'o') {
                        stack.push('O');
                    } 
                    // 如果栈顶的两个元素不相等，或者有一个为大泡泡"O"，则将它们按原顺序重新入栈，并中断当前循环
                    else if (c != d) {
                        stack.push(d);
                        stack.push(c);
                        break;
                    }
                }
            }
            
            StringBuilder sb = new StringBuilder();
            
            // 将栈中剩余的元素依次出栈，并将出栈的元素追加到字符串构建器中
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            
            String s1 = sb.reverse().toString(); // 反转字符串构建器中的字符序列，得到最终结果字符串
            System.out.println(s1); // 输出结果字符串
        }
        
        scanner.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

首先，创建一个Stack对象来模拟小鱼儿吐泡泡的过程。

1. 从输入中读取字符串String s。 使用一个循环遍历字符串中的每个字符。 在循环中，将当前字符入栈。
2. 检查栈的大小是否大于1，即是否有足够的元素进行比较和融合。
3. 如果栈顶的两个元素相等且都为小泡泡"o"，则将它们出栈，并将大泡泡"O"入栈。
4. 如果栈顶的两个元素不相等，或者有一个为大泡泡"O"，则将它们按原顺序重新入栈，并中断当前循环。
5. 循环结束后，栈中剩余的元素就是小鱼儿吐出的泡泡经过融合后的结果。
6. 创建一个StringBuilder对象，从栈顶开始依次出栈，并将出栈的元素追加到字符串构建器中。
7. 将字符串构建器中的字符序列反转，得到最终结果字符串。
8. 输出结果字符串。

这段代码的思路是利用栈的后进先出（LIFO）特性来模拟泡泡的融合过程。通过不断入栈、比较、出栈的操作，可以将相邻的小泡泡融合成大泡泡，同时将相邻的大泡泡爆掉。最终，栈中剩余的元素即为融合后剩余的泡泡序列。

---

参考代码Java（循环遍历字符串）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s = scanner.next(); // 读取输入的字符串
            StringBuilder sb = new StringBuilder(s);  // 使用StringBuilder保存字符串方便进行插入和删除操作
            
            // 遍历字符串中的每个字符
            for (int i = 1; i < sb.length(); i++) {
                // 判断当前字符和前一个字符的情况
                if ('o' == sb.charAt(i - 1) && 'o' == sb.charAt(i)) {
                    sb.setCharAt(i - 1, 'O'); // 将前一个字符替换为大泡泡"O"
                    sb.delete(i, i + 1); // 删除当前字符（小泡泡"o"）
                    i = 0;  // 从头开始遍历字符串，因为有可能新生成的大泡泡和前面的泡泡继续融合
                } else if ('O' == sb.charAt(i - 1) && 'O' == sb.charAt(i)) {
                    sb.delete(i - 1, i + 1); // 删除前一个字符和当前字符（两个大泡泡）
                    i = 0;  // 从头开始遍历字符串，因为有可能新生成的大泡泡和前面的泡泡继续融合
                }
            }
            
            System.out.println(sb.toString()); // 输出最终结果字符串
        }
        scanner.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

具体来说，代码中使用了一个循环来遍历字符串的每个字符。在每次循环中，判断当前字符和前一个字符的关系，分为以下两种情况：

• 如果前一个字符是小泡泡’o’且当前字符也是小泡泡’o’，则进行融合操作。将前一个字符改为大泡泡’O’，然后从字符串中删除当前字符。接着将循环控制变量i重置为0，从头开始继续遍历字符串，以确保融合之后的泡泡继续与它前面的泡泡进行判断和操作。
• 如果前一个字符是大泡泡’O’且当前字符也是大泡泡’O’，则进行爆破操作。直接从字符串中删除前一个字符和当前字符。同样地，将循环控制变量i重置为0，以便重新开始遍历。

这样循环直到遍历完整个字符串，得到的结果就是小鱼儿吐出的泡泡经过融合或爆破操作后所剩余的泡泡。