(0)前言
通过局部最优得到全局最优解。
55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
思路：维护一个变量 k, 为最远可以跳的位置
class Solution:
def canJump(self, nums: List[int]) -> bool:
k = 0
for i,num in enumerate(nums):
if i>k:
return False
k = max(k,i+nums[i])
return True
45. 跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
class Solution:
def jump(self, nums: List[int]) -> int:
pos = len(nums)-1
steps = 0
while pos>0:
for i in range(pos):
if i+nums[i]>=pos:
pos = i
steps += 1
break
return steps
517. 超级洗衣机
class Solution:
def findMinMoves(self, machines: List[int]) -> int:
n = len(machines)
tot = sum(machines)
if tot%n != 0:
return -1
avg = tot//n
ans, cur = 0, 0
for num in machines:
num -= avg
cur += num
ans = max(ans, num, abs(cur))
return ans
