讨论/题目交流/🏆 第 169 场力扣周赛/
🏆 第 169 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 和为零的N个唯一整数
4 分 - 两棵二叉搜索树中的所有元素
5 分 - 跳跃游戏 III
7 分 - 口算难题

展开讨论
力扣 (LeetCode)发起于 2019-12-29
最近编辑于 2019-12-29

[WeeklyContest]169 Q3 跳跃游戏 III

题目来源

这里有一个非负整数数组 arr,你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时,你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。

注意,不管是什么情况下,你都无法跳到数组之外。

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length

样例

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

算法1

(bfs) T:O(n) S:O(n)

  • 从start这个点出发,进行广度优先遍历,看看当前点idx对应的arr[idx]是不是等于0,若等于0就停止寻找;若找不到就往左走idx-arr[idx]或者往右走idx+arr[idx]。(越界了就不走)
  • 访问过一个节点就不用再访问了,用一个数组vis来标记

C++ 代码

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> vis(n, false);
        
        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int idx = q.front(); q.pop();
            vis[idx] = true;
            if (arr[idx] == 0) return true;
            int left = idx - arr[idx], right = idx + arr[idx];
            if (left >= 0 && left < n && !vis[left]) q.push(left);
            if (right >= 0 && right < n && !vis[right]) q.push(right);
        }
        
        return false;
    }
};

算法2

(dfs) T:O(n) S:O(n)

  • 从start这个点出发,进行深度优先遍历,先看看左边能不能找到等于0的点,若找到了直接返回;若没找到再看看右边能不能找到等于0的点。都没找到就返回false

C++ 代码

class Solution {
public:
    vector<bool> vis;
    
    bool dfs(const vector<int>& arr, int idx) {
        if (arr[idx] == 0) return true;
        vis[idx] = true;
        int left = idx - arr[idx], right = idx + arr[idx];
        bool res = false;
        if (left >= 0 && left < arr.size() && !vis[left]) 
            res = dfs(arr, left);
        if (!res && right >= 0 && right < arr.size() && !vis[right]) 
            res = dfs(arr, right);
        return res;
    }
    
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vis.resize(n, false);
        return dfs(arr, start);
    }
};
1
展开全部 17 讨论