|
1 | | -# Time: O(n) |
| 1 | +# Time: O(n) ~ O(n^2) |
2 | 2 | # Space: O(n) |
3 | 3 |
|
4 | 4 | # A frog is crossing a river. The river is divided into x units and |
@@ -44,63 +44,13 @@ def canCross(self, stones): |
44 | 44 | :type stones: List[int] |
45 | 45 | :rtype: bool |
46 | 46 | """ |
47 | | - lookup = {} |
48 | | - for k, v in enumerate(stones): |
49 | | - lookup[v] = k |
50 | | - |
51 | | - dp = [False for _ in xrange(len(stones))] |
52 | | - dp[0] = True |
53 | | - for i in xrange(len(stones)): |
54 | | - if dp[i]: |
55 | | - for k in (i-1, i, i+1): |
56 | | - if stones[i] + k in lookup: |
57 | | - dp[lookup[stones[i] + k]] = True |
58 | | - return dp[-1] |
59 | | - |
60 | | - |
61 | | -# Time: O(nlogn) |
62 | | -# Space: O(n) |
63 | | -# DP with binary search |
64 | | -class Solution2(object): |
65 | | - def canCross(self, stones): |
66 | | - """ |
67 | | - :type stones: List[int] |
68 | | - :rtype: bool |
69 | | - """ |
70 | | - def findNextStones(stones, i): |
71 | | - next_stones = [] |
72 | | - for k in (i-1, i, i+1): |
73 | | - j = bisect.bisect_left(stones, stones[i] + k) |
74 | | - if j != len(stones) and stones[j] == stones[i] + k: |
75 | | - next_stones.append(j) |
76 | | - return next_stones |
77 | | - |
78 | | - dp = [False for _ in xrange(len(stones))] |
79 | | - dp[0] = True |
80 | | - for i in xrange(len(stones)): |
81 | | - if dp[i]: |
82 | | - for j in findNextStones(stones, i): |
83 | | - dp[j] = True |
84 | | - return dp[-1] |
85 | | - |
86 | | - |
87 | | -# Time: O(n^2) |
88 | | -# Space: O(n) |
89 | | -class Solution3(object): |
90 | | - def canCross(self, stones): |
91 | | - """ |
92 | | - :type stones: List[int] |
93 | | - :rtype: bool |
94 | | - """ |
95 | | - dp = [False for _ in xrange(len(stones))] |
96 | | - dp[0] = True |
97 | | - |
98 | | - for i in xrange(1, len(stones)): |
99 | | - for j in reversed(xrange(i)): |
100 | | - if stones[i] - stones[j] > j + 1: |
101 | | - break |
102 | | - if dp[j] and ((stones[i] - stones[j]) in ([j-1, j, j+1] if i != 1 else [1])): |
103 | | - dp[i] = True |
104 | | - break |
105 | | - |
106 | | - return dp[-1] |
| 47 | + if stones[1] != 1: |
| 48 | + return False |
| 49 | + lookup = {s: set() for s in stones} |
| 50 | + lookup[1].add(1) |
| 51 | + for i in stones[:-1]: |
| 52 | + for j in lookup[i]: |
| 53 | + for k in xrange(j-1, j+2): |
| 54 | + if k > 0 and i+k in lookup: |
| 55 | + lookup[i+k].add(k) |
| 56 | + return bool(lookup[stones[-1]]) |
0 commit comments