蛙跳-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

**难度: hard**

> 内容描述

```
一只青蛙正在过河。这条河被分成x个单元，每个单元可能有一块石头，也可能没有。青蛙可以在石头上跳，但不能跳入水中。

给出一个按升序排列的石头位置列表（单位），确定青蛙是否能够在最后一块石头上着陆过河。最初，青蛙在第一块石头上，并假设第一次跳跃必须是1个单位。

如果青蛙的最后一次跳跃是k个单位，那么它的下一次跳跃必须是k-1、k或k+1个单位。注意青蛙只能向前跳。

注：

石头的数量是≥ 2且小于1100。

每个石头的位置将是一个小于231的非负整数。

第一块石头的位置总是0。

例1：

[0,1,3,5,6,8,12,17]

一共有8块石头。

第0单元的第一块石头，第1单元的第二块石头，

第三单元的第三块石头，等等。。。

第17单元的最后一块石头。

返回true。青蛙可以跳到最后一块石头

1个单位到第二块石头，然后2个单位到第三块石头，然后

2个单位到第四块石头，然后3个单位到第六块石头，

第七石有4个单位，第八石有5个单位。

例2：

[0,1,2,3,4,8,9,11]

返回false。没有办法跳到最后一块石头

第五石和第六石之间的差距太大。
```

## 解题方案

> 思路 1
******- 时间复杂度: O(N)******- 空间复杂度: O(N)******

* 关注点放在数据范围。

* 判断是否能够到达y点（因为问题就是到达最后一个点），需要两个条件：

* 能够到达x点（x<y）
  * x点能够跳到y点

* 由于条件2需要前面一个点的跳动情况，所以这个题的子问题是

`flag[x][y]=true`表示当青蛙能够跳到x，并且能够跳到y点

* 状态转移是

假设`flag[x][y]=true`，枚举所有的z>y，如果`|(z-y) - (y-x)|<=1`，那么`flag[y][z]=true`

* 这里有个需要注意的优化点，可以固定y，枚举x<y，和z>y，这样对于每个y，只需要扫一遍点数组就可以成功执行转移

* 复杂度是o(n^2)

代码：

```java
class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;

if (stones[1] != 1) {
            return false;
        }

boolean[][] flag = new boolean[n][n];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                flag[i][j] = false;
            }
        }

flag[1][0] = true;

for (int i = 1;i < n;i++) {
            int left = i - 1;
            int right = i + 1;

while (left >= 0 && right < n) {
                while (left >= 0 && !flag[i][left]) left--;
                if (left >= 0) {
                    while (right < n && stones[right] - stones[i] <= stones[i] - stones[left] + 1) {
                        if (stones[right] - stones[i] == stones[i] - stones[left] - 1
                                || stones[right] - stones[i] == stones[i] - stones[left]
                                || stones[right] - stones[i] == stones[i] - stones[left] + 1) {
                            flag[right][i] = true;
                        }
                        right++;
                    }
                    left--;
                }
            }
        }

for (int i = 0;i < n;i++) {
            if (flag[n - 1][i]) {
                return true;
            }
        }
        return false;
    }
}
```

该分类下的相关小册推荐：

编程之道-算法面试(下)

编程之道-算法面试(上)

数据结构与算法(下)

数据结构与算法之美

数据结构与算法(上)

业务开发实用算法精讲

算法面试通关 50 讲