有这样一个任务:
有一个整数数组,你需要以最少的步数从数组的第一个元素到最后一个元素。您可以通过两种方式移动:
1 种方式:您可以在相邻数字之间移动。也就是说,如果一个数字在第 i 个位置,那么从中您可以得到第 i -1 个数字或第 i +1 个数字。
2方式:如果第i个数在数组中出现了两次或多次,那么就可以将这些相等数之间的区间内的所有数字都跳转(也就是说,比如元素2和5相等,那么就可以立即跳转从第二个元素跳转到第五个元素,绕过元素 3 和 4)。
示例1:
输入数据:3 5 2 2 5
输出数据:2
示例2:
输入数据:11 -86 -86 201 11 86 86 86 3 201
输出数据:3
据我了解,这可以使用 BFS 算法来完成,但我不明白在这种情况下如何创建图?
或者也许有其他方法可以解决这个问题?
您实际上不必“创建”图表,因为图表已经隐式编码在输入数组中。这些规则定义了图形的边缘。 在任何给定的索引处,您可以通过检查输入数组来确定哪些是可能的跳转:这些是从当前节点(当前索引)到 BFS 树的子节点的边。
为了避免一遍又一遍地扫描数组中的重复值,首先收集具有相同值的索引是有意义的,这样对于给定值,您可以查找具有相同值的索引列表,并且这样做比再次检查整个阵列更有效。
这是 JavaScript 中的实现——我没有使用该语言的任何高级功能:
function solve(arr) {
const n = arr.length;
// Preprocessing to improve efficiency:
// gather the indices occupied by each distinct value
const map = new Map(); // A hashmap keyed by input values, giving list of indices
for (let i = 0; i < n; i++) {
const val = arr[i];
if (!map.has(val)) map.set(val, []); // assign an empty array to this value
map.get(val).push(i); // Add the current index to this list
}
// Main BFS algorithm
let currLevel = [0]; // Start at index 0; this is the first level
const visited = new Set(); // Set of indices that have been visited
visited.add(0);
let depth = 0;
while (true) {
let nextLevel = [];
for (let i of currLevel) { // Traverse indices at the same level of the BFS tree
if (i == n - 1) return depth; // Bingo!
// Get the possible jumps to the same value elsewhere:
const children = map.get(arr[i]);
// Also consider just stepping one step forward
children.push(i + 1);
for (let child of children) {
if (visited.has(child)) continue; // Don't visit a second time
visited.add(child);
nextLevel.push(child);
}
}
currLevel = nextLevel;
depth++;
}
}
// Example call:
let test = [1,3,8,9,10,11,2,4,12,1,2,5,6,7,4];
console.log(solve(test)); // 5
我使用了这个不那么简单的输入作为示例:
[1,3,8,9,10,11,2,4,12,1,2,5,6,7,4]
...因为最短路径涉及向后跳跃:
[1,3,8,9,10,11,2,4,12,1,2,5,6,7,4]
└────────────────────┐ 1. jump to other 1
└─┐ 2. step forward
┌────────┘ 3. jump to other 2
└─┐ 4. step forward
└──────────────┐ 5. jump to other 4
done