#055 Jump Game题解
典型的贪心算法题目
题目描述
Given
an array
of non-negative integers, you are initially positioned
at the first index
of the array.
Each
element in the array represents your maximum jump
length at that position.
Determine
if you are able
to reach
the last index.
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
l=len(nums)
r=
0
i=
0
while (i<l
and i<=r):
r = max(r,i+nums[i])
i=i+
1
return r>=l-
1
#120 Triangle题解
一道动态规划的数组题。
题目描述
Given
an array
of non-negative integers, you are initially positioned
at the first index
of the array.
Each
element in the array represents your maximum jump
length at that position.
Determine
if you are able
to reach
the last index.
Example
1:
Input: [
2,
3,
1,
1,
4]
Output:
true
Explanation: Jump
1 step
from index
0 to 1,
then 3 steps
to the last index.
Example
2:
Input: [
3,
2,
1,
0,
4]
Output:
false
Explanation: You will always arrive
at index
3 no matter what. Its maximum
jump
length is
0, which makes
it impossible
to reach
the last index.
解题思路就是写好状态转移的式子。
"""
@author: novic
"""
class Solution(object):
def minimumTotal(self, triangle):
"""
写出递归表达式就可以了
"""
n = len(triangle)
dp = triangle[n-
1]
for i
in range(n-
2,-
1,-
1):
for j
in range(
0,i+
1):
dp[j] = min( dp[j], dp[j+
1] ) + triangle[i][j]
return dp[
0]
#134 Gas Station
贪心算法题
题目描述
There are N gas stations along a circular route,
where the amount
of gas
at station i
is gas[i].
You have a car
with an unlimited gas tank
and it costs cost[i]
of gas
to travel
from station i
to its next station (i+
1). You begin
the journey
with an empty tank
at one
of the gas stations.
Return
the starting gas station's index
if you can travel
around the circuit once, otherwise
return -
1.
Note: The solution
is guaranteed
to be unique.
解答
class Solution:
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
if (sum(gas)<sum(cost)):
return -
1
l = len(gas)
end=
0
start=l-
1
sums = gas[start] - cost[start]
while (end <start):
if (sums>=
0):
sums = sums+ gas[end] - cost[end]
end = end +
1
else:
start = start -
1
sums = sums + gas[start] - cost[start]
if (sums>=
0):
return start
else:
return -
1
