122.买卖股票的最佳时机II
题目链接122. 买卖股票的最佳时机 II - 力扣（LeetCode）
思路
这个题感觉和之前一个题有点像，就是摆动序列，但是又有点不太一样
本题的核心规则：
可以无限次买卖
任何时候最多持有 1 股
同一天可以买了再卖
求最大利润
只要后一天价格 > 前一天价格，就把这两天的差价赚到手。所有上涨日的差价加起来 = 最大利润。
为什么正确？连续上涨（1→2→3→4→5），每天赚差价：(2-1)+(3-2)+(4-3)+(5-4) = 5-1，和一次买卖结果完全一样
两个题的区别：
股票题：只赚涨的钱，跌的不碰
摆动序列：交替涨跌都算，统计最长长度
提交
很神奇，我以为会是很复杂的手段，结果和我想的不一样，有一种四两拨千斤的感觉
仿佛大脑的褶皱被抚平
class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 # 从第2天开始遍历 for i in range(1, len(prices)): # 只要今天比昨天贵，就赚差价 if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit55. 跳跃游戏
题目链接55. 跳跃游戏 - 力扣（LeetCode）
思路
首先，我没看懂题的意思？又开始阅读理解了
规则：
数组
nums[i]：在位置i最多能跳几步起点：下标
0目标：判断能不能到达最后一个下标
示例 1： 输入：nums = [2,3,1,1,4]
输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
我懂了，每个数组位置数字，是最多能跳几步
核心思想
用一个变量
max_reach记录当前能跳到的最远位置遍历数组，每到一个位置，就更新最远能跳到哪
如果遍历的位置超过了最远可达位置，说明卡住了，直接返回
false如果最远位置 >= 最后一个下标，直接返回
true
一句话：只要当前位置还能跳到，就不断更新最远跳跃距离。
提交
class Solution: def canJump(self, nums: List[int]) -> bool: max_reach = 0 # 记录当前能跳到的最远下标 n = len(nums) for i in range(n): # 如果当前位置都跳不到，直接失败 if i > max_reach: return False # 更新最远能跳到的位置 max_reach = max(max_reach, i + nums[i]) # 已经能跳到终点，提前返回 if max_reach >= n - 1: return True return True45.跳跃游戏II
题目链接45. 跳跃游戏 II - 力扣（LeetCode）
思路
这简直就是55跳跃游戏的plus版本
核心逻辑：不关心每一步具体跳到哪个位置，只关心当前能到达的最远位置，当遍历到当前跳跃的边界时，必须进行一次跳跃，同时更新边界为新的最远位置。
三个关键变量：
jumps：记录最小跳跃次数（最终结果）current_end：当前这一步能到达的最远边界farthest：遍历过程中能到达的全局最远位置
遍历规则：
遍历数组（不需要遍历最后一个元素，因为到了最后一个元素就已经到达终点）
每遍历一个位置，更新能到达的最远位置
farthest当遍历到
current_end时，说明必须跳一步，jumps+1，并把current_end更新为farthest
以nums = [2,3,1,1,4]为例：
- 初始：
jumps=0, current_end=0, farthest=0 - i=0：
farthest = max(0, 0+2) = 2i == current_end→jumps=1，current_end=2
- i=1：
farthest = max(2, 1+3) = 4
- i=2：
farthest = max(4, 2+1) = 4i == current_end→jumps=2，current_end=4（已经到达终点，退出）
- 最终返回
2
提交
class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) jumps = 0 # 记录跳跃次数 current_end = 0 # 当前跳跃的边界 farthest = 0 # 能到达的最远位置 # 不需要遍历最后一个元素，因为已经到达终点 for i in range(n - 1): # 更新最远能到达的位置 farthest = max(farthest, i + nums[i]) # 到达当前边界，必须跳一次 if i == current_end: jumps += 1 current_end = farthest # 优化：如果已经能跳到终点，直接提前退出 if current_end >= n - 1: break return jumps1005.K次取反后最大化的数组和
题目链接1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
思路
依旧还是先做阅读理解
k是指可以选择k个数字将他们的正负号反转，但是具体反转那个不知道。
有不同的反转方案
我们要得到最佳方案，就是这些方法里面数组之和最大的那个结果
第一版思路：通过66/84
可以先把数组排序，我们反转数组里面较小的数字
对于正数：反转之后减的最少，那就是反最小的正数
对于负数：反转之后加的最大，反负更多的，也就是更小的负数
比如【4,2,3】k=1，排序【2,3,4】就是反转2
【2，-3，-1，5，-4】k=2，排序【-4，-3，-1,2,5】反转-4，-3
但是有一种特殊情况 就是有0的：
因为题目说有些下标是可以多次反转的
那我们把负的反过来之后，还有次数就反转0
这里正数部分应该单独处理
比如把正数反转之后，我们应该找修改数组后的最小值反转
而不是继续遍历反转
提交
from typing import List class Solution: def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: # 从小到大排序，优先翻转最小的负数（收益最大） nums.sort() for i in range(len(nums)): if nums[i]<0: # 翻转当前最小负数为正数，消耗一次翻转次数 nums[i] = -nums[i] k -= 1 if k == 0: # 翻转次数用完，直接退出 break elif nums[i]==0: # 遇到0，剩余次数全部翻转0，总和不变 k = 0 break else: # 后面全是正数，无需继续翻转 break if k>0 and k%2==1: # 剩余奇数次翻转，必须翻转一次最小值（损失最小） num=min(nums) index=nums.index(num) nums[index]=-nums[index] return sum(nums)
