深度优先算法-Jump Game

发表于 分类于
学习笔记

DFS: 深度优先搜索算法（Depth First Search）

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

算法1

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean dfs(int[] nums, int start, Set set) {
    if (start < 0 || start > nums.length || nums[start] == -1) return false;
    if (nums[start] == 0) return true;
    for (int i : new int[]{-1, 1}) {
        int next = start + i * nums[start];
        if (!set.contains(next) && next >= 0 && next < nums.length) {
            set.add(next);
            if (dfs(nums, next, set)) return true;
            set.remove(next);
        }
    }
    return false;
}

算法2

1
2
3
4
5
6
7
public boolean dfs(int[] nums, int start) {
    if (start < 0 || start >= nums.length || nums[start] == -1)
        return false;
    int step = nums[start];
    nums[start] = -1;
    return step == 0 || dfs(nums, start + step) || dfs(nums, start - step);
}