难度: Hard
原题连接
内容描述
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
The number of stones is ≥ 2 and is < 1,100.
Each stone's position will be a non-negative integer < 231.
The first stone's position is always 0.
Example 1:
[0,1,3,5,6,8,12,17]
There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.
Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11]
Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.
思路 1 - 时间复杂度: O(N^3)- 空间复杂度: O(N^2)******
这个题目肯定要用dp来做的
然后我开始找了一个方法，就是让dp[x][y]代表我们可以到达stone x，我们是否可以到达z
所以初始值就是dp[0][1] = 1
如果dp[x][y] == 1的话，并且对于一个z大于y，如果abs((stones[z] - stones[y]) - (stones[y) - stones[x)) <= 1，
那么dp[y][z] = 1
但是超时了
class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
if stones[1] != 1:
return False
dp = [[0] * len(stones) for i in range(len(stones))]
dp[0][1] = 1
for y in range(1, len(stones)):
for x in range(y):
for z in range(y+1, len(stones)):
if not dp[x][y]:
continue
else:
if abs((stones[z]-stones[y])-(stones[y]-stones[x])) <= 1:
if z == len(stones)-1:
return True
dp[y][z] = 1
for i in range(len(dp)):
if dp[i][-1]:
return True
return False思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******
于是想到了另外一种dp，用一个字典,存的key和value分别是stone 的位置和从该位置能跳的步数的set
初始值位置0的value只有1，那么初始位置1的value有(0,1,2)
最后我们看看，如果有哪个位置和其value中的任意一个步数的和可以凑齐最后一个位置，那么最后一个位置可达
但是这样不是很好判断，其实如果最后一个位置对应的value set非空的话也说明最后一个位置可达，因为不可达我们一定对其无操作，其value set必为空
beats 66.77%
class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
lookup = {}
for i in range(len(stones)):
lookup[stones[i]] = set()
lookup[0].add(1)
for i in range(len(stones)):
for step in lookup[stones[i]]:
if step > 0 and stones[i] + step in lookup:
# lookup[stones[i]+step] = lookup[stones[i]+step].union(set([step-1,step,step+1]))
lookup[stones[i]+step].update([step-1,step,step+1])
return len(lookup[stones[-1]]) > 0或者将value看作可以到达该key的步数，beats 47.71%
class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
lookup = {}
for i in range(len(stones)):
lookup[stones[i]] = set()
lookup[0].add(0)
for i in range(len(stones)):
for k in lookup[stones[i]]:
for step in (k-1,k,k+1):
if step > 0 and stones[i] + step in lookup:
lookup[stones[i]+step].add(step)
return len(lookup[stones[-1]]) > 0