广度优先算法-Jump Game

发表于 分类于
学习笔记

BFS: 广度优先搜索算法（Breadth First Search）, 又叫宽度优先搜索，或横向优先搜索。

搜索顺序为: A B C D E F G

描述

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。请你判断自己是否能够跳到对应元素值为 0 的任意下标处。
注意，不管是什么情况下，你都无法跳到数组之外。

示例 1

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 5 -> 下标 4 -> 下标 1 -> 下标 3
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

示例 2

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。

算法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean bfs(int[] nums, int start) {
    if (start < 0 || start > nums.length || nums[start] == -1) return false;
    Queue q = new LinkedList();
    q.add(start);

    Set set = new HashSet();
    set.add(start);

    while (q.size() > 0) {
        int poll = (int) q.poll();
        if (nums[poll] == 0) return true;
        for (int i : new int[]{-1, 1}) {
            int next = poll + i * nums[poll];
            if (!set.contains(next) && next >= 0 && next < nums.length) {
                q.add(next);
                set.add(next);
            }
        }
    }
    return false;
}

算法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean bfs(int[] nums, int start) {
    if (start < 0 || start >= nums.length || nums[start] == -1)
        return false;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    /*标记已经被访问过*/
    Set<Integer> set = new HashSet<>();
    set.add(start);
    while (!queue.isEmpty()) {
        int poll = queue.poll();
        if (nums[poll] == 0) return true;
        if (poll + nums[poll] < nums.length && !set.contains(poll + nums[poll])) {
            queue.add(poll + nums[poll]);
            set.add(poll + nums[poll]);
        }
        if (poll - nums[poll] >= 0 && !set.contains(poll - nums[poll])) {
            queue.add(poll - nums[poll]);
            set.add(poll - nums[poll]);
        }
    }
    return false;
}