难度: 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点(因为问题就是到达最后一个点),需要两个条件:
由于条件2需要前面一个点的跳动情况,所以这个题的子问题是
flag[x][y]=true
表示当青蛙能够跳到x,并且能够跳到y点
状态转移是
假设flag[x][y]=true
,枚举所有的z>y,如果|(z-y) - (y-x)|<=1
,那么flag[y][z]=true
这里有个需要注意的优化点,可以固定y,枚举x
复杂度是o(n^2)
代码:
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;
}
}