[leetcode]1306.跳跃游戏II

本题目一看题目是一道搜索题,可以用深度优先搜索或者使用广度优先搜索,但是看了一下题目中给定的数字的范围<=5*10^4次方。

这个数量级直接使用深搜会超时,那就使用广度优先搜索好了。

广搜相对来说比较简单,主要是队列入出,分支判断,跳出标准,以上三点基本就能写出来了。

队列直接使用c++内置的队列queue就好了,分支判断主要是包括任何一个坐标他既可以+arr[idx],也可以-arr[i],这就很明白了,就两个分支嘛。

跳出标准就是走到一个点,其下标所在的数组元素值为0即可。

为了防止重复进入某个坐标导致死循环,可以维护一个visit数组,该数组用来记录所有找过的坐标就好了,只要是搜过的坐标,就不需要继续搜了,可以直接跳过。

清楚这几点就很容易写出该题,简单的C语言代码如下,可以从该题了解到如何使用queueu,如何在c++中直接使用容器来方便的做题。

题目的意思是给个数组和初始下标,一直搜索,看存不存在一条路径idx+arr[idx]或者idx-arr[idx】作为新位置,找到一个位置元素为0.

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        init_visit(arr.size());
        return bfs(arr, start);
    }

private:
    bool bfs(vector<int> &arr, int start) {
        queue<int> que;
        int idx;
        int nw_idx;

        que.push(start);
        while (!que.empty()) {
            idx = que.front();
            que.pop();

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

            visit[idx] = true;
            nw_idx = idx + arr[idx];
            if (nw_idx < arr.size() && !visit[nw_idx]) {
                que.push(idx + arr[idx]);
            }

            nw_idx = idx - arr[idx];
            if (nw_idx >= 0 && !visit[nw_idx]) {
                que.push(idx - arr[idx]);
            }
        }
        return false;
    }

    void init_visit(int n) {
        int i;

        for (i = 0; i < n; i++) {
            visit.push_back(false);
        }
    }

    vector<bool> visit;
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode]1306.跳跃游戏II

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/224.html

相关文章