因为数据太大,但数据量少,因此可以用map先建立映射关系
再用二维set,其中set[i]表示第i个石块所能跳的距离数组
二维vector会超时,set去重就可以了
然后遍历每个石块,并求出其所能到达石块 所能跳的距离
最后判断第n - 1个石块是否有能跳的步数即可
class Solution { public: set<int> V[2020]; map<int, int> M; bool canCross(vector<int>& stones) { int n = stones.size(); int cnt = 0; for(int i = 0; i < n; i++) M[stones[i]] = i; V[0].insert(1); set<int>::iterator it; for(int i = 0; i < n; i++) { for(it = V[i].begin(); it != V[i].end(); it++) { if(M.count(stones[i] + *it) != 0) { V[M[stones[i] + *it]].insert(*it); if(*it - 1 != 0) V[M[stones[i] + *it]].insert(*it - 1); V[M[stones[i] + *it]].insert(*it + 1); } } } return V[n - 1].size(); } };