Monday, December 22, 2014

[LeetCode]Jump Game II

类似Jump Game 的第一种解法,我们采用类似BFS的解法,还是BFS找最短路径的问题。
首先如果A的len为1的话。我们直接返回0。之后我们维护step来表示BFS的深度,初始化为1,同时维护一个right bound,初始化为A[0],i初始化为0。进入循环,每次check一下right bound是否大于等于len - 1,如果是的话,return step。否则从i到right bound看最远能到的值,更新right bound,如果发现新的rightbound 和老的right bound一样,说明我们没法前进了,break 返回 -1。如果不是的话,更新right bound,step++,重复之前的步骤。

代码如下:

No comments:

Post a Comment