SONG Shengjie
List: 122.买卖股票的最佳时机II，55. 跳跃游戏，45.跳跃游戏II，1005.K次取反后最大化的数组和
122.买卖股票的最佳时机 IIbest-time-to-buy-and-sell-stock-ii，55. 跳跃游戏jump-game，45.跳跃游戏 IIjump-game-ii，
122.买卖股票的最佳时机 IIbest-time-to-buy-and-sell-stock-ii
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result = 0
for i in range(1, len(prices)):
result += max(prices[i] - prices[i - 1], 0)
return result
55. 跳跃游戏jump-game
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
if len(nums) == 1:
return True
i = 0
while i <= cover:
cover = max(cover, i + nums[i])
if cover >= len(nums) - 1: # 如果覆盖范围能够到达或超过数组的最后一个位置，返回 True
return True
i += 1
return False
45.跳跃游戏 IIjump-game-ii
class Solution:
def jump(self, nums: List[int]) -> int:
cur = 0
ans = 0
cover = 0
if len(nums) == 1:
return 0
for i in range(len(nums)):
cover = max(cover, i + nums[i])
if i == cur:
if cur != len(nums) - 1:
cur = cover
ans += 1
if cur >= len(nums) - 1:
break
else:
break
return ans
优化：
class Solution:
def jump(self, nums: List[int]) -> int:
cur = 0
ans = 0
cover = 0
if len(nums) == 1:
return 0
for i in range(len(nums) - 1):
cover = max(cover, i + nums[i])
if i == cur:
cur = cover
ans += 1
return ans
-
精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一.
-
移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。只要让移动下标，最大只能移动到 nums.size - 2 的地方就可以了.
- 因为当移动下标指向 nums.size - 2 时：如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。
1005.K次取反后最大化的数组和maximize-sum-of-array-after-k-negations
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort(key = lambda x: abs(x), reverse = True)
for i in range(len(nums)):
if nums[i] < 0 and k > 0:
nums[i] *= -1
k -= 1
if k % 2 == 1:
nums[-1] *= -1
result = 0
for i in range(len(nums)):
result += nums[i]
return result