Day 9:1306 跳跃游戏III

1306 跳跃游戏III

• 1. 题目描述
• 2. 解题思路
• 3. 代码实现(DFS)
• 4. 代码实现(BFS)

1. 题目描述

1306 跳跃游戏III

2. 解题思路

1. 使用dfs或bfs的思想来进行遍历;
2. 使用used数组来表示当前位置是否被访问过。

3. 代码实现(DFS)

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> used(n, false);
        
        function<bool(int)> dfs = [&](int idx) {
            if (idx < 0 || idx >= n))
                return false;
  			
  			if(used[idx])
  				return false;
                
            if (arr[idx] == 0)
                return true;
  
            used[idx] = true;
            
            return dfs(idx - arr[idx]) || dfs(idx + arr[idx]);
        };
        
        return dfs(start);
    }
};

4. 代码实现(BFS)

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> used(n, false);

        queue<int> que;
        que.push(start);

        while (!que.empty()) {
            auto it = que.front();
            que.pop();

            // 下标超出范围
            if (it < 0 || it >= n)
                continue;
                
            // 当前位置下标已访问过
            if (used[it])
                continue;

            if (arr[it] == 0)
                return true;

            used[it] = true;

            que.push(it + arr[it]);
            que.push(it - arr[it]);
        }
        return false;
    }
};