如何从整数数组创建 BFS 算法

Question

有这样一个任务：

有一个整数数组，你需要以最少的步数从数组的第一个元素到最后一个元素。您可以通过两种方式移动：

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 算法来完成，但我不明白在这种情况下如何创建图？

或者也许有其他方法可以解决这个问题？

Answer 1

您实际上不必“创建”图表，因为图表已经隐式编码在输入数组中。这些规则定义了图形的边缘。 在任何给定的索引处，您可以通过检查输入数组来确定哪些是可能的跳转：这些是从当前节点（当前索引）到 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