最新华为OD机试真题-石碑文字组合(200分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 石碑文字组合(200分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

石碑文字组合

问题描述

考古学家 LYA 在一次考古挖掘中发现了一块断裂成 段的石碑,每一段石碑上都刻有一个小写字母。为了破解石碑的内容,LYA 需要将这 段石碑按照一定的顺序进行排列组合。现在请你帮助 LYA 计算出所有可能的石碑文字组合,并按字典序升序输出。

输入格式

第一行包含一个正整数 ,表示石碑碎片的数量,满足 。

第二行包含 个由空格隔开的小写字母,表示每段石碑上的文字内容。

输出格式

按字典序升序输出所有可能的石碑文字组合,每个组合占一行。

样例输入

3
a b c

3
a b a

样例输出

abc
acb
bac
bca
cab
cba

aab
aba
baa

数据范围

题解

本题是一道典型的排列组合问题,可以使用 DFS(深度优先搜索)或回溯法来解决。

具体思路如下:

1. 用一个数组 vis 来标记每个字母是否已经被使用过,初始时所有字母都未被使用。

2. 从第一个位置开始,枚举每个未被使用过的字母,将其加入当前排列,并标记为已使用。

3. 递归处理下一个位置,直到所有位置都被填满,得到一个完整的排列,将其加入答案数组。

4. 回溯时,将当前位置的字母标记为未使用,以便在其他排列中重新使用。

5. 当所有排列都被生成后,对答案数组进行去重和排序,按字典序升序输出即可。

根据上述思路,我们可以很容易地写出 DFS 或回溯的代码。时间复杂度为 ,其中 为石碑碎片的数量。由于 的范围较小,因此该算法可以在规定时间内完成。

参考代码

• Python

def dfs(idx, cur):
    if idx == n:
        ans.append(''.join(cur))
        return
    for i in range(n):
        if not vis[i]:
            vis[i] = True
            cur.append(s[i])
            dfs(idx + 1, cur)
            vis[i] = False
            cur.pop()

n = int(input())
s = input().split()
vis = [False] * n
ans = []
dfs(0, [])
ans = sorted(set(ans))
for a in ans:
    print(a)

• Java

import java.util.*;

public class Main {
    static void dfs(int idx, ArrayList<String> cur, String[] s, boolean[] vis, ArrayList<String> ans, int n) {
        if (idx == n) {
            StringBuilder result = new StringBuilder();
            for (String str : cur) {
                result.append(str);
            }
            ans.add(result.toString());
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                vis[i] = true;
                cur.add(s[i]);
                dfs(idx + 1, cur, s, vis, ans, n);
                vis[i] = false;
                cur.remove(cur.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume newline
        String[] s = scanner.nextLine().split(" ");
        boolean[] vis = new boolean[n];
        ArrayList<String> ans = new ArrayList<>();
        ArrayList<String> cur = new ArrayList<>();
        dfs(0, cur, s, vis, ans, n);
        Collections.sort(ans);
        LinkedHashSet<String> set = new LinkedHashSet<>(ans);
        ans = new ArrayList<>(set);
        for (String a : ans) {
            System.out.println(a);
        }
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

void dfs(int idx, std::vector<std::string>& cur, std::vector<std::string>& s, std::vector<bool>& vis, std::vector<std::string>& ans, int n) {
    if (idx == n) {
        std::string result;
        for (const auto& str : cur) {
            result += str;
        }
        ans.push_back(result);
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            vis[i] = true;
            cur.push_back(s[i]);
            dfs(idx + 1, cur, s, vis, ans, n);
            vis[i] = false;
            cur.pop_back();
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    std::vector<std::string> s(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
    }
    std::vector<bool> vis(n, false);
    std::vector<std::string> ans;
    std::vector<std::string> cur;
    dfs(0, cur, s, vis, ans, n);
    std::sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    for (const auto& a : ans) {
        std::cout << a << std::endl;
    }
    return 0;
}