华为OD机试 - 字符串化繁为简（Java 2024 C卷 200分）

在这里插入图片描述

目录

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

专栏导读

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

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

一、题目描述

给定一个输入字符串，字符串只可能由英文字母 (‘a’‘z’、‘A’‘Z’ )和左右小括号 (‘(’、‘)’)组成。当字符里存在小括号时，小括号是成对的，可以有一个或多个小括号对，小括号对不会嵌套，小括号对内可以包含1个或多个英文字母，也可以不包含英文字母。当小括号对内包含多个英文字母时，这些字母之间是相互等效的关系，而且等效关系可以在不同的小括号对之间传递，即当存在’a’和’b’等效和存在’b’和’c’ 等效时，‘a’ 和 ‘c’ 也等效，另外，同一个英文字母的大写字母和小写字母也相互等效 (即使它们分布在不同的括号对里)。

需要对这个输入字符串做简化，输出一个新的字符串，输出字符串里只需保留输入字符串里的没有被小括号对包含的字符(按照输入字符串里的字符顺序) ，并将每个字符替换为在小括号对里包含且字典序最小的等效字符。
如果简化后的字符串为空，请输出为"0"。

示例：

输入字符串为"never(dont)give(run)up(f)()“，初始等效字符集合为(‘d’,‘o’,‘n’,‘t’)、(‘r’,‘u’,‘n’)，由于等效关系可以传递，因此最终等效字符集合为(‘d’,‘o’,‘n’,‘t’,‘r’,‘u’)，将输入字符串里的剩余部分按字典序最小的等效字符替换后得到"devedgivedp”。

二、输入描述

输入为 1 行，代表输入字符串。

三、输出描述

输出为 1 行，代表输出字符串。

1、输入

(abd)demand(fb)for

2、输出

aemanaaor

3、说明

等效字符集为(‘a’,‘b’,‘d’,‘f’)，输入字符串里没有被小括号包含的子字符串集合为 “demandfor”，将其中字符替换为字典序最小的等效字符后输出为：“aemanaaor”。

四、解题思路

  1. 遍历输入字符串；
  2. 判断字符：
    • 如果是（，表示括号内字符开始标识符；
    • 如果是），括号内字符结束标识符；
    • 如果不是（），判断其是否是括号内字符；
      • 如果是括号内字符，放入括号内字符数组bracketsArr；
      • 否则放入非括号内字符builder；
  3. 遍历括号内字符数组bracketsArr，获取字典序最小的等效字符；
    • 如果未取到字典表最小的灯效字符；
    • 按字典表从小到大排序后，如果括号内数组不为空，则为字典序最小的等效字符；
    • 如果取到字典表最小的灯效字符，则将不是最小的等效字符替换为最小的等效字符；
  4. 每个字符替换为在小括号对里包含且字典序最小的等效字符；
  5. 输出替换后的字符串。

五、Java算法源码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String input = sc.nextLine();
    // 是否是括号内字符
    boolean inBracketsFlag = false;
    // 非括号内字符
    StringBuilder builder = new StringBuilder();
    // 括号内字符，放入数组，方便排序
    char[] bracketsArr = new char[input.length()];
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        if(c == '('){// 括号内字符开始标识符
            inBracketsFlag = true;
            continue;
        }else if(c == ')'){// 括号内字符结束标识符
            inBracketsFlag = false;
            continue;
        }else {
            if(inBracketsFlag){// 括号内字符
                bracketsArr[i] = c;
            }else {// 非括号内字符
                builder.append(c);
            }
        }
    }

    /**
     * key：括号内非字典序最小的等效字符
     * value：括号内字典序最小的等效字符
     */
    Map<Character,Character> map = new HashMap<>();
    // 获取字典序最小的等效字符
    Arrays.sort(bracketsArr);
    // 字典序最小的等效字符
    char minChar = '\u0000';
    for (int i = 0; i < bracketsArr.length; i++) {
        // 如果未取到字典表最小的灯效字符
        if(minChar == '\u0000'){
            // 按字典表从小到大排序后，如果括号内数组不为空，则为字典序最小的等效字符
            if(bracketsArr[i] != '\u0000'){
                minChar = bracketsArr[i];
                continue;
            }
        }else {// 如果取到字典表最小的灯效字符，则将不是最小的等效字符替换为最小的等效字符
            map.put(bracketsArr[i],minChar);
        }
    }

    // 每个字符替换为在小括号对里包含且字典序最小的等效字符
    StringBuilder resultBuilder = new StringBuilder();
    for (int i = 0; i < builder.length(); i++) {
        char c = builder.charAt(i);
        if(map.containsKey(c)){
            resultBuilder.append(map.get(c));
        }else{
            resultBuilder.append(c);
        }
    }

    System.out.println(resultBuilder);
}

六、效果展示

1、输入

()happy(xyz)new(wxy)year(tT)

2、输出

happTneTTear

3、说明

  1. 获取括号内字符：xyzwxytT —> xyzwT
  2. 获取字典序最小的等效字符T；
  3. 拼接非括号内字符：happynewyear；
  4. 将非括号内每个字符替换为在小括号对里包含且字典序最小的等效字符：happTneTTear

在这里插入图片描述


🏆下一篇：华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

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

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

在这里插入图片描述