• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[每日一题] leetcode 403. 青蛙过河

开发技术 开发技术 2周前 (04-29) 6次浏览

因为数据太大,但数据量少,因此可以用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();
    }
};

 


程序员灯塔
转载请注明原文链接:[每日一题] leetcode 403. 青蛙过河
喜欢 (0)