[1306] 跳跃游戏 III

dfs

details

function canReach(arr, start) {
    // 深度优先搜索的递归函数
    function dfs(index) {
        // 越界或者访问过当前索引，直接返回 false
        if (index < 0 || index >= arr.length || visited[index]) {
            return false;
        }

        // 如果当前索引处的值是 0，返回 true
        if (arr[index] === 0) {
            return true;
        }

        // 标记当前索引已访问
        visited[index] = true;

        // 尝试向左跳跃和向右跳跃
        return dfs(index + arr[index]) || dfs(index - arr[index]);
    }

    // 用于记录已访问的索引
    let visited = new Array(arr.length).fill(false);

    // 从起始索引开始搜索
    return dfs(start);
}

bfs

Javascript

var canReach = function (arr, start) {
    let n = arr.length;
    let visited = new Array(n).fill(false);
    let queue = [start];

    while (queue.length > 0) {
        let current = queue.shift();

        if (arr[current] === 0) {
            return true;
        }

        if (visited[current]) {
            continue;
        }

        visited[current] = true;

        let nextPos1 = current + arr[current];
        let nextPos2 = current - arr[current];

        if (nextPos1 < n && !visited[nextPos1]) {
            queue.push(nextPos1);
        }

        if (nextPos2 >= 0 && !visited[nextPos2]) {
            queue.push(nextPos2);
        }
    }

    return false;
};