当前位置：首页 > web >正文

考古学家 - 华为OD统一考试(JavaScript 题解)

web 2025/8/1 1:18:02

alt

题目描述

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

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

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

输入描述

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

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

输出描述

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

示例1

输入：
3
a b c输出：
abc
acb
bac
bca
cab
cba

示例2

输入：
3
a b a输出：
aab
aba
baa

示例3

输入：
3
a b ab输出：
aabb
abab
abba
baab
baba

题解

这是一个典型的排列组合问题，可以使用回溯算法来生成所有可能的组合。

代码大致描述：

读取石碑碎片的个数n和每个碎片的文字内容ss。
创建一个用于标记是否使用过的数组used和一个用于存储当前组合的容器collect，以及 rs 存储结果。
调用backtrack函数进行回溯，生成所有可能的排列组合。
在backtrack函数中，检查当前组合的长度是否等于石碑碎片的个数n，如果是则拼接成字符串并存入 rs 中。
递归调用backtrack函数，尝试不同的组合。
在每次递归调用前，标记当前石碑碎片为已使用，以防止重复使用。
递归调用后，将标记恢复，进行下一轮尝试。

这样，通过回溯算法，可以遍历所有可能的排列组合，最终可以生成所有的石碑文字组合，然后排序输出。

JavaScript

const rl = require('readline').createInterface({input: process.stdin,
});
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;// Author: code5bug
void (async function () {// 读取输入const n = parseInt(await readline());const ss = (await readline()).split(' ');// 初始化变量const used = new Array(n).fill(false); // 标记元素是否被使用const collect = []; // 当前收集的组合const rs = new Set(); // 存储所有不重复的组合结果// 回溯函数function backtrack() {if (collect.length === n) {// 组合完成rs.add(collect.join(''));return;}for (let i = 0; i < n; i++) {// 元素被使用或与前一个相同则跳过if (used[i] || (i > 0 && ss[i - 1] === ss[i])) continue;used[i] = true;collect.push(ss[i]);backtrack(); // 递归collect.pop();used[i] = false;}}backtrack(); // 开始回溯// 输出结果，按字典序排序console.log([...rs].sort().join('\n'));rl.close();
})();