华为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
五、解题思路
我们需要计算复原后的石碑文字组合数,这实际上涉及字符串的全排列问题,并且要去除重复的组合。具体步骤如下:
- 输入解析:
- 读取石碑碎片的个数 N。
- 读取石碑碎片上的文字内容,并存储在一个列表中。
- 去重和排序:
- 为了确保结果是唯一且按升序排列的,需要对碎片进行去重和排序。
- 计算组合:
- 生成所有可能的组合(全排列),并去除重复的组合。
- 使用 set 数据结构来存储这些组合,以自动去重。
- 输出结果:
- 对组合结果进行排序,并按照要求的格式输出。
六、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在线答疑。