122.买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
- 输入: [1,2,3,4,5]
- 输出: 4
- 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
- 输入: [7,6,4,3,1]
- 输出: 0
- 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
- 1 <= prices.length <= 3 * 10 ^ 4
- 0 <= prices[i] <= 10 ^ 4
思路：核心是计算每一个极大值和极小值之间，递增部分的增值，那么也可以理解为计算整个数组区间递增部分的增值，所以计算极大值和极小值没有意义，我们只要关注相邻元素之间有递增的部分就可以了，即【只要第二天比前一天有提高，那就第一天买入第二天卖出】，这就是贪心的思路。
引代码随想录的解释，更清晰易懂：
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
代码实现如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
res += prices[i] - prices[i-1]
return res
规范代码：（更简洁）
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
动态规划:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
return dp[-1][1]
55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
- 输入: [2,3,1,1,4]
- 输出: true
- 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
- 输入: [3,2,1,0,4]
- 输出: false
- 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
思路：
问题转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！
代码实现如下：
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums) <= 1:
return True
far = 0 + nums[0]
for i in range(1, len(nums)):
if i > far:
return False
far = max(far, i + nums[i])
if far >= len(nums)-1:
return True
# 超时
'''
dp = [0] * len(nums)
dp[0] = 1
for i in range(len(nums)):
if dp[i] == 0:
return False
for j in range(1, nums[i]+1):
if i+j < len(nums):
dp[i+j] = 1
return True
#if dp[-1] == 1:
# return True
#else:
# return False
'''
规范代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
if len(nums) == 1: return True
i = 0
# python不支持动态修改for循环中变量,使用while循环代替
while i <= cover:
cover = max(i + nums[i], cover)
if cover >= len(nums) - 1: return True
i += 1
return False
For循环写法：
## for循环class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
if len(nums) == 1: return True
for i in range(len(nums)):
if i <= cover:
cover = max(i + nums[i], cover)
if cover >= len(nums) - 1: return True
return False
45.跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
- 输入: [2,3,1,1,4]
- 输出: 2
- 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
错误思路： 想尝试用回溯，时间会超时，所以尝试剪枝，每次尝试取当前位置最远的步长，以为这样跳到的结果就一定是最少次数的，没有考虑当前位置到当前位置最短的步长位置【之间】可能会存在更大的步长，这应该是错误原因。本题一刷失败，看解析。
正确思路：
每一步都判断自己是否还在上一步更新的范围之内，同时更新这一步能够到达的最远距离范围。如果发现当前位置超出了上一步更新的范围，说明已经要走第二步，将【上一步】的范围更新成【第二步】能够到达的最远距离范围，而从现在开始（此时已经开始第二步）更新的就是【再下一步（第三步）】的最远距离范围，以此循环可以得到结果。
如果看不懂，学习传送门：
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html#%E6%80%9D%E8%B7%AF
错误代码：
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
self.min = float('inf')
if self.backtracking(nums, 0, 0):
return self.min
def backtracking(self, nums: List[int], start: int, cur:int):
if start >= len(nums)-1:
#self.min = min(self.min, cur)
self.min = cur
return True
if cur >= self.min:
return
for i in range(nums[start]+1, 1, -1):
if self.backtracking(nums, start+i, cur+1):
return True
规范代码：
class Solution:
def jump(self, nums):
if len(nums) == 1:
return 0
cur_distance = 0 # 当前覆盖最远距离下标
ans = 0 # 记录走的最大步数
next_distance = 0 # 下一步覆盖最远距离下标
for i in range(len(nums)):
next_distance = max(nums[i] + i, next_distance) # 更新下一步覆盖最远距离下标
if i == cur_distance: # 遇到当前覆盖最远距离下标
ans += 1 # 需要走下一步
cur_distance = next_distance # 更新当前覆盖最远距离下标（相当于加油了）
if next_distance >= len(nums) - 1: # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束
break
return ans
贪心（版本二）
class Solution:
def jump(self, nums):
cur_distance = 0 # 当前覆盖的最远距离下标
ans = 0 # 记录走的最大步数
next_distance = 0 # 下一步覆盖的最远距离下标
for i in range(len(nums) - 1): # 注意这里是小于len(nums) - 1，这是关键所在
next_distance = max(nums[i] + i, next_distance) # 更新下一步覆盖的最远距离下标
if i == cur_distance: # 遇到当前覆盖的最远距离下标
cur_distance = next_distance # 更新当前覆盖的最远距离下标
ans += 1
return ans
贪心（版本三） 类似‘55-跳跃游戏’写法
class Solution:
def jump(self, nums) -> int:
if len(nums)==1: # 如果数组只有一个元素，不需要跳跃，步数为0
return 0
i = 0 # 当前位置
count = 0 # 步数计数器
cover = 0 # 当前能够覆盖的最远距离
while i <= cover: # 当前位置小于等于当前能够覆盖的最远距离时循环
for i in range(i, cover+1): # 遍历从当前位置到当前能够覆盖的最远距离之间的所有位置
cover = max(nums[i]+i, cover) # 更新当前能够覆盖的最远距离
if cover >= len(nums)-1: # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置，直接返回步数+1
return count+1
count += 1 # 每一轮遍历结束后，步数+1
动态规划
class Solution:
def jump(self, nums: List[int]) -> int:
result = [10**4+1] * len(nums) # 初始化结果数组，初始值为一个较大的数
result[0] = 0 # 起始位置的步数为0
for i in range(len(nums)): # 遍历数组
for j in range(nums[i] + 1): # 在当前位置能够跳跃的范围内遍历
if i + j < len(nums): # 确保下一跳的位置不超过数组范围
result[i + j] = min(result[i + j], result[i] + 1) # 更新到达下一跳位置的最少步数
return result[-1] # 返回到达最后一个位置的最少步数
1005.K次取反后最大化的数组和
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1：
- 输入：A = [4,2,3], K = 1
- 输出：5
- 解释：选择索引 (1) ，然后 A 变为 [4,-2,3]。
示例 2：
- 输入：A = [3,-1,0,2], K = 3
- 输出：6
- 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
- 输入：A = [2,-3,-1,5,-4], K = 2
- 输出：13
- 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
- 1 <= A.length <= 10000
- 1 <= K <= 10000
- -100 <= A[i] <= 100
思路：
本题贪心的思路是，首先对负数进行反转，而负数里最优先反转的就是负数中最小的数（绝对值越大负数越小）。所以我们首先进行第一次排序，然后根据所给的k（即反转次数）尽可能给从小到大的负数进行反转。另一种情况是所有负数都反转完但是反转次数k还没用完，此时要找出所有正数的最小值，所以再次进行排序，然后将所有的反转次数都给最小的一个数（如果所剩翻转为偶数，结果不影响，依然全部是正数；如果是奇数，被翻转为负数的数也是绝对值最小的数）
代码实现如下：
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort()
cur = 0
while cur < len(nums) and nums[cur] < 0 and k > 0:
nums[cur] *= -1
cur += 1
k -= 1
nums.sort()
while k > 0:
nums[0] *= -1
k -= 1
return sum(nums)
规范代码：
class Solution:
def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
A.sort(key=lambda x: abs(x), reverse=True) # 第一步：按照绝对值降序排序数组A
for i in range(len(A)): # 第二步：执行K次取反操作
if A[i] < 0 and K > 0:
A[i] *= -1
K -= 1
if K % 2 == 1: # 第三步：如果K还有剩余次数，将绝对值最小的元素取反
A[-1] *= -1
result = sum(A) # 第四步：计算数组A的元素和
return result
标签：return,游戏,nums,int,self,len,II,prices,跳跃 From： https://blog.csdn.net/weixin_47681529/article/details/142886571