笔试题总结
两道笔试题，在这里总结下
1.小明闯关打怪
1）题目大致如下：
小明要闯关打怪，每个关卡小明有可能获得一些能量。
小明可以根据利用能量跳过关卡，但是跳过关卡会消耗能量，每跳一个关卡消耗一个能量。
小明最终的目的是到达最后一关Boss关卡，要判断小明是否能到达。
例如：
总共有五个关卡，能量值分别是2、1、0、1、2。
第一个关卡的能量是2，小明在第一个关卡可以获得两个能量。
他可以选择跳过两个关卡直接跳到第三关，但是第三关的能量值是0，小明消耗了原本的能量，能量总数为0，这时他就无法继续闯关到最后一关了；
但是小明也可以选择跳过一个关卡，到第二关，这时它消耗了一个能量，又获得了第二关的1个能量，总共又2个能量，这时他可以选择跳过两个关卡到达第四关，再凭借第四关获得的1个能量到达最后一关。
2）输入：
输入一行数据，以空格分隔，每个值代表每一关可以获得的能量值。
2 1 0 1 2
3）输出：
如果能到达最后一关，返回true，如果不能返回false。
true
解决思路：
在每个关卡，小明需要决定是否跳跃以及跳跃多远，这个过程具有递归性质，因为每次跳跃后，小明都会到达一个新的位置，并面临同样的决策。
由于关卡顺序固定，所以是单项跳跃，使得问题具有图的结构，每个关卡是一个节点。
我们需要找到一条跳跃的路径，使得小明能够走到最后一个节点。
深度优先搜索是一个优选，它可以递归的探索所有的路径，如果走到了死胡同就回溯，寻找其他路径。
function canReachBossSimplified(energies) {
const n = energies.length;
function dfs(currentPos, currentEnergy) {
if (currentPos === n - 1) {
return true;
}
currentEnergy += energies[currentPos];
for (let jump = 1; jump <= currentEnergy && currentPos + jump < n; jump++) {
if (dfs(currentPos + jump, currentEnergy - jump)) { // 跳跃，并递归判断是否能到达boss
return true;
}
}
return false;
}
return dfs(0, 0);// 开始
}
const energies = [2, 1, 0, 1, 2];
const result = canReachBossSimplified(energies);
console.log(result); // true2.切换名字
1）题目大致如下：
要将原始名字转换为新名字，但是每次只能从名字列表中挑选，而且每次只能改变其中的一个字符，判断最终能否成功转换为新名字，如果可以则输入转换的每一步过程，如果有多种情况则将每种情况都输出，如果不能转换则输出null。
2）输入：
第一行为原始名字，第二行为要变成的新名字，第三行为名字列表
dog
cat
cot dot cat
3）输出：
如果可以转换就输出改变的过程：
dog dot cot cat
其他示例：
nummm
nubub
nummn nubum numnm nubub
不能转换，输出：
null
输入：
hello
hodee
helle hedle hedde hodee hodde hedee
输出：
hello helle hedle hedee hodee
hello helle hedle hedde hodde hodee
解决思路：
要求找到是否能成功转换为新名字，如果能则要输出每一步过程，即需要找到从初始状态到目标状态的最少转换步骤，广度优先搜索是优选，因为它可以逐层遍历状态空间，保证首先找到的是最短路径。
function findTransformations(original, target, dictionary) {
const queue = [[original, []]]; // 队列中的每个元素是一个数组，包含当前名字和转换步骤
// queue结构：
// queue = [["dog", []], ["dot", ["dog", "dot"]], ["cot", ["dog", "dot", "cot"]], ["cat", ["dog", "dot", "cot", "cat"]]]
const visited = new Set([original]); // 记录已访问的名字
const results = []; // 存储所有可能的转换路径
while (queue.length > 0) {
// 数组的解构赋值，从数组中提取值，并将这些值分别赋给变量 current 和 steps
const [current, steps] = queue.shift();
// 尝试修改当前名字的每一个字符
for (let i = 0; i < current.length; i++) {
for (let j = 0; j < 26; j++) {
const newChar = String.fromCharCode(97 + j); // 生成a-z的字符
const newName = current.slice(0, i) + newChar + current.slice(i + 1);
if (newName === target) {
// 找到了一条转换路径
results.push([...steps, newName]);
} else if (!visited.has(newName) && dictionary.includes(newName)) {
// 如果新名字在字典中且未被访问过，则加入队列继续搜索
queue.push([newName, [...steps, newName]]);
visited.add(newName);
}
}
}
}
if (results.length === 0) {
return "null";
} else {
// 将每条路径的转换步骤连接起来
return results.map(path => path.join(" ")).join(", ");
}
}
// 示例输入
const original1 = "dog";
const target1 = "cat";
const dictionary1 = ["dot", "cot", "cat"];
console.log(findTransformations(original1, target1, dictionary1)); // 输出: dog dot cot cat
const original2 = "nummm";
const target2 = "nubub";
const dictionary2 = ["nummn", "nubum", "numnm", "nubub"];
console.log(findTransformations(original2, target2, dictionary2)); // 输出: nummm nummn numnm nubub
const original3 = "hello";
const target3 = "hodee";
const dictionary3 = ["hodee", "helle", "hedle", "hedde", "hodde", "hedee"];
console.log(findTransformations(original3, target3, dictionary3)); // 输出: hello helle hedle hedde hedee hodee, hello helle hedle hedde hodde hodee