共计 1609 个字符，预计需要花费 5 分钟才能阅读完成。
TOP1 跳跃游戏
给定一个非负整数数组，你最后位于数组的第一个地位。数组中的每个元素代表你在该地位能够跳跃的最大长度。判断你是否可能达到最初一个地位。
例如对于 [2,3,1,1,4] 返回真，对于 [3,2,1,0,4] 返回假。
贪婪策略 1 ：如果地位 i 能够达到，那么 i 之前的所有地位肯定能够达到。
def solution(nums):
reach = 0
for i in range(len(nums)):
if i > reach:
return False
reach = max(reach, i + nums[i])
return True贪婪策略 2 ：向前遍历记录能够达到起点的最前的地位。
def solution(nums):
start = len(nums) - 1
for i in range(len(nums)-1, -1, -1):
if i + nums[i] >= start:
start = i
return 0 == startTOP2 跳跃游戏Ⅱ
给定一个非负整数数组，你最后位于数组的第一个地位。数组中的每个元素代表你在该地位能够跳跃的最大长度。你的指标是应用起码的跳跃次数达到数组的最初一个地位。假如你总是能够达到数组的最初一个地位。
例如对于 [2,3,1,1,4] 返回 2。
贪婪策略 1 ：每一次记录能到起点的最前的地位，并更新起点地位。
def solution(nums):
aim = len(nums) - 1
cnt = 0
while aim:
for i in range(len(nums)):
if i + nums[i] >= aim:
aim = i
cnt += 1
break
return cnt贪婪策略 2 ：记录地位 i 步长范畴内哪个地位能达到的间隔最远，此步就走哪个地位。
def solution(nums):
aim, edge, ans = 0, 0, 0
for i in range(len(nums)-1):
aim = max(aim, i + nums[i])
if i == edge:
ans += 1
edge = aim
return ansTOP3 交易股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你能够尽可能地实现更多的交易（屡次交易一支股票）。你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。
例如对于 [7,1,5,3,6,4] 返回 7，对于 [1,2,3,4,5] 返回 4。
贪婪策略：只记录上升段收益。
def solution(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profitTOP4 宰割均衡字符串
在一个「均衡字符串」中，’L’ 和 ‘R’ 字符的数量是雷同的。给出一个均衡字符串 s，请你将它宰割成尽可能多的均衡字符串。返回能够通过宰割失去的均衡字符串的最大数量。
例如对于 ”RLRRLLRLRL” 返回 4，对于 ”RLLLLRRRLR” 返回 3。
贪婪策略：遍历到均衡状态则后果加一。
def solution(s):
ans, balance = 0, 0
for i in s:
balance += 1 if i == 'L' else -1
if not balance: ans += 1
return ansTOP5 散发饼干
假如你是一位很棒的家长，想要给你的孩子们一些小饼干。然而，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 gi，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 sj。如果 sj >= gi，咱们能够将这个饼干 j 调配给孩子 i，这个孩子会失去满足。你的指标是尽可能满足越多数量的孩子，并输入这个最大数值。
贪婪策略：优先满足胃口小的孩子。
def solution(g, s):
g.sort()
s.sort()
i, j = 0, 0
while i < len(g) and j < len(s):
if g[i] <= s[j]: i += 1
j += 1
return i