day24-数据结构力扣

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时说明必须跳一步jumps1并把current_end更新为farthest以nums [2,3,1,1,4]为例初始jumps0, current_end0, farthest0i0farthest max(0, 02) 2i current_end→jumps1current_end2i1farthest max(2, 13) 4i2farthest max(4, 21) 4i current_end→jumps2current_end4已经到达终点退出最终返回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】k1排序【2,3,4】就是反转2【2-3-15-4】k2排序【-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 k0 and k%21: # 剩余奇数次翻转必须翻转一次最小值损失最小 nummin(nums) indexnums.index(num) nums[index]-nums[index] return sum(nums)