分析

• 本题的考点：BFS。

• 本题相当于给我们一个数轴，然后stones中的值代表该位置有石头，第一次可以跳1步，如果当前可以跳k步，则下一次可以跳k-1、k、k+1步。问我们能否跳到终点。例如题目中的第一个样例：

• 首先，我们使用哈希表hash记录石头在坐标轴上的坐标在stones中的下标，即hash[stones[i]]=i，例如hash[5]=3，代表坐标为5的石头存在，且在stones中的下标为3。

• 设状态(p, k)表示当前在stones中的下标为p的位置，且上一步跳跃了k步，则我们可以从这个状态装移到(hash[stones[p]+k-1], k-1)，(hash[stones[p]+k], k)，(hash[stones[p]+k+1], k+1)。注意k-1、k、k+1要大于0，且坐标为stones[p]+k+i的石头要存在。

• 可以使用BFS解决这个问题，初始状态是(0, 0)。

• 参考网址：网址。

代码

• C++

class Solution {
public:
    typedef pair<int, int> PII;  // (当前在stones中的下标为p的位置，且上一步跳跃了k步)

    bool canCross(vector<int>& stones) {
        int n = stones.size();

        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++) hash[stones[i]] = i;

        // 第一次最多跳1步，第二次最多跳2步，...，第n-1次最多跳n-1步，因此第二维开到n即可
        vector<vector<bool>> st(n, vector<bool>(n, false));  // 判重数组
        queue<PII> q;
        q.push({0, 0});
        st[0][0] = true;
        while (q.size()) {
            auto t = q.front(); q.pop();
            int p = t.first, k = t.second;

            if (p == n - 1) return true;

            for (int i = -1; i <= 1; i++) {
                int nk = k + i;
                // 跳的步数nk要大于0，且坐标stones[p] + nk要存在石头
                if (nk <= 0 || !hash.count(stones[p] + nk)) continue;

                int np = hash[stones[p] + nk];
                if (st[np][nk]) continue;  // 已经被遍历过

                q.push({np, nk});  // (p, k) -> (np, nk)
                st[np][nk] = true;
            }
        }
        return false;
    }
};

• Java

class Solution {

    static class MyPair {
        int p, k;  // (当前在stones中的下标为p的位置，且上一步跳跃了k步)
        public MyPair(int p, int k) {
            this.p = p; this.k = k;
        }
    }

    public boolean canCross(int[] stones) {
        int n = stones.length;

        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++) hash.put(stones[i], i);

        boolean[][] st = new boolean[n][n];
        Queue<MyPair> q = new LinkedList<>();
        q.add(new MyPair(0, 0));
        st[0][0] = true;
        while (!q.isEmpty()) {
            MyPair t = q.remove();
            int p = t.p, k = t.k;

            if (p == n - 1) return true;

            for (int i = -1; i <= 1; i++) {
                int nk = k + i;
                if (nk <= 0 || !hash.containsKey(stones[p] + nk)) continue;

                int np = hash.get(stones[p] + nk);
                if (st[np][nk]) continue;

                q.add(new MyPair(np, nk));
                st[np][nk] = true;
            }
        }
        return false;
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$，n为数组长度。最多有$O(n^2)$个状态，每次只有 3 种转移。

• 空间复杂度：$O(n^2)$。队列和判重数组。