华为OD机试真题 - 考古学家 - 递归（Python/JS/C/C++ 2024 D卷 200分）

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

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

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

二、输入描述

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

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

三、输出描述

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

四、测试用例

1、输入

3
a b c

2、输出

abc
acb
bac
bca
cab
cba

3、输入

3
a b ab

4、输出

aabb
abab
abba
baab
baba

五、解题思路

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

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

六、Python算法源码

from itertools import permutationsdef get_combinations(fragments):# 使用 set 去重并排序unique_combinations = set()# 生成所有组合for perm in permutations(fragments):unique_combinations.add(''.join(perm))# 返回排序后的列表return sorted(unique_combinations)def main():# 读取石碑碎片的个数 NN = int(input())# 读取石碑碎片上的文字内容fragments = []for _ in range(N):fragments.append(input().strip())# 获取复原后的石碑文字组合combinations = get_combinations(fragments)# 输出结果for combination in combinations:print(combination)if __name__ == "__main__":main()

七、JavaScript算法源码

function getCombinations(fragments) {// 使用 Set 去重并排序let uniqueCombinations = new Set();// 生成所有组合function generateCombinations(currentCombination, visited) {if (currentCombination.length === fragments.length) {uniqueCombinations.add(currentCombination.join(''));return;}for (let i = 0; i < fragments.length; i++) {if (visited[i]) continue;visited[i] = true;currentCombination.push(fragments[i]);generateCombinations(currentCombination, visited);// 回溯currentCombination.pop();visited[i] = false;}}generateCombinations([], Array(fragments.length).fill(false));// 返回排序后的数组return Array.from(uniqueCombinations).sort();
}function main() {// 读取石碑碎片的个数 Nconst N = parseInt(prompt("Enter the number of fragments:"));// 读取石碑碎片上的文字内容let fragments = [];for (let i = 0; i < N; i++) {fragments.push(prompt("Enter fragment:").trim());}// 获取复原后的石碑文字组合let combinations = getCombinations(fragments);// 输出结果for (let combination of combinations) {console.log(combination);}
}// 调用 main 函数
main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>// 定义一个结构体来存储字符串集合
typedef struct {char **data;int size;int capacity;
} StringSet;// 初始化字符串集合
StringSet* createSet(int capacity) {StringSet *set = (StringSet*)malloc(sizeof(StringSet));set->data = (char**)malloc(sizeof(char*) * capacity);set->size = 0;set->capacity = capacity;return set;
}// 检查字符串是否在集合中
bool contains(StringSet *set, const char *str) {for (int i = 0; i < set->size; i++) {if (strcmp(set->data[i], str) == 0) {return true;}}return false;
}// 将字符串添加到集合中
void add(StringSet *set, const char *str) {if (!contains(set, str)) {set->data[set->size] = strdup(str);set->size++;}
}// 释放集合内存
void freeSet(StringSet *set) {for (int i = 0; i < set->size; i++) {free(set->data[i]);}free(set->data);free(set);
}// 生成所有组合
void generateCombinations(char **fragments, bool *visited, char *currentCombination, int depth, int n, StringSet *uniqueCombinations) {if (depth == n) {add(uniqueCombinations, currentCombination);return;}for (int i = 0; i < n; i++) {if (visited[i]) continue;visited[i] = true;strcat(currentCombination, fragments[i]);generateCombinations(fragments, visited, currentCombination, depth + 1, n, uniqueCombinations);currentCombination[strlen(currentCombination) - strlen(fragments[i])] = '\0'; // 回溯visited[i] = false;}
}int compareStrings(const void *a, const void *b) {return strcmp(*(const char **)a, *(const char **)b);
}int main() {int N;// 读取石碑碎片的个数 Nscanf("%d", &N);// 读取石碑碎片上的文字内容char **fragments = (char**)malloc(sizeof(char*) * N);for (int i = 0; i < N; i++) {fragments[i] = (char*)malloc(sizeof(char) * 100);scanf("%s", fragments[i]);}// 初始化集合用于存储组合StringSet *uniqueCombinations = createSet(10000);// 存储当前组合char currentCombination[1000] = "";bool visited[N];memset(visited, 0, sizeof(visited));// 生成所有组合generateCombinations(fragments, visited, currentCombination, 0, N, uniqueCombinations);// 对组合进行排序qsort(uniqueCombinations->data, uniqueCombinations->size, sizeof(char*), compareStrings);// 输出结果for (int i = 0; i < uniqueCombinations->size; i++) {printf("%s\n", uniqueCombinations->data[i]);}// 释放内存freeSet(uniqueCombinations);for (int i = 0; i < N; i++) {free(fragments[i]);}free(fragments);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>using namespace std;// 生成所有组合
void generateCombinations(vector<string>& fragments, vector<bool>& visited, string& currentCombination, set<string>& uniqueCombinations) {if (currentCombination.size() == fragments.size() * fragments[0].size()) {uniqueCombinations.insert(currentCombination);return;}for (int i = 0; i < fragments.size(); i++) {if (visited[i]) continue;visited[i] = true;currentCombination += fragments[i];generateCombinations(fragments, visited, currentCombination, uniqueCombinations);// 回溯currentCombination.erase(currentCombination.size() - fragments[i].size());visited[i] = false;}
}vector<string> getCombinations(vector<string>& fragments) {set<string> uniqueCombinations;string currentCombination;vector<bool> visited(fragments.size(), false);generateCombinations(fragments, visited, currentCombination, uniqueCombinations);return vector<string>(uniqueCombinations.begin(), uniqueCombinations.end());
}int main() {int N;// 读取石碑碎片的个数 Ncin >> N;// 读取石碑碎片上的文字内容vector<string> fragments(N);for (int i = 0; i < N; i++) {cin >> fragments[i];}// 获取复原后的石碑文字组合vector<string> combinations = getCombinations(fragments);// 输出结果for (const string& combination : combinations) {cout << combination << endl;}return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。