华为OD机试 - 考古学家 - 递归（Java 2024 D卷 200分）

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

有一个考古学家发现一个石碑，但是很可惜发现时其已经断成多段。

原地发现N个断口整齐的石碑碎片，为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数，你能帮忙吗？

备注：如果存在石碑碎片内容完全相同，则由于碎片间的顺序不影响复原后的碑文内容，仅相同碎片间的位置变化不影响组合。

二、输入描述

第一行输入N，N表示石碑碎片的个数

第二行依次输入石碑碎片上的文字内容S共有N组

三、输出描述

输出石碑文字的组合(按照升序排列)，行尾无多余空格

1、输入

3
a b c

2、输出

abc
acb
bac
bca
cab
cba

四、解题思路

我们需要计算复原后的石碑文字组合数，这实际上涉及字符串的全排列问题，并且要去除重复的组合。具体步骤如下：

输入解析：
- 读取石碑碎片的个数 N。
- 读取石碑碎片上的文字内容，并存储在一个列表中。
去重和排序：
- 为了确保结果是唯一且按升序排列的，需要对碎片进行去重和排序。
计算组合：
- 生成所有可能的组合（全排列），并去除重复的组合。
- 使用 set 数据结构来存储这些组合，以自动去重。
输出结果：
- 对组合结果进行排序，并按照要求的格式输出。

五、Java算法源码

public class Test01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取石碑碎片的个数 N
        int N = scanner.nextInt();
        scanner.nextLine(); // 读取换行符

        // 读取石碑碎片上的文字内容
        String[] fragments = new String[N];
        for (int i = 0; i < N; i++) {
            fragments[i] = scanner.next();
        }

        // 关闭Scanner
        scanner.close();

        // 获取复原后的石碑文字组合
        List<String> combinations = getCombinations(fragments);

        // 输出结果
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }

    // 获取复原后的石碑文字组合
    private static List<String> getCombinations(String[] fragments) {
        // 使用Set去重并排序
        Set<String> uniqueCombinations = new TreeSet<>();
        // 用于存储当前组合
        List<String> combination = new ArrayList<>();
        boolean[] visited = new boolean[fragments.length];

        // 生成所有组合
        generateCombinations(fragments, visited, combination, uniqueCombinations);

        return new ArrayList<>(uniqueCombinations);
    }

    // 递归生成所有组合
    private static void generateCombinations(String[] fragments, boolean[] visited, List<String> combination, Set<String> uniqueCombinations) {
        if (combination.size() == fragments.length) {
            // 将当前组合加入Set
            uniqueCombinations.add(String.join("", combination));
            return;
        }

        for (int i = 0; i < fragments.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            combination.add(fragments[i]);
            generateCombinations(fragments, visited, combination, uniqueCombinations);
            // 回溯
            combination.remove(combination.size() - 1);
            visited[i] = false;
        }
    }
}