代码随想录算法训练营|122、买卖股票的最佳时机II 55、跳跃游戏 45、跳跃游戏II 1005、K次取反后最大化的数组和

目录122. 买卖股票的最佳时机 II题目描述题目例子解题思路55. 跳跃游戏解题思路题目例子解题思路45. 跳跃游戏 II题目描述题目例子解题思路1005. K 次取反后最大化的数组和 - 力扣LeetCode题目描述题目例子解题思路122. 买卖股票的最佳时机 II题目描述给你一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而你可以在同一天多次买卖该股票但要确保你持有的股票不超过一股。返回你能获得的最大利润。题目例子prices [7,1,5,3,6,4]输出7在第二天价格为1时买入第三天价格为5时卖出利润为4第四天价格为3时买入第五天价格为6时卖出解题思路当前只有一只股票并且每天只有买或卖的操作所以股票两天为一个交易单位计算每两天之间的利润差当利润为正数时由于当天只有买或卖操作所以直接将利润的正数相加即可若利润差为[0,1,2,-1]那么12就是收取的利润则第一天买第三天卖若利润差为[0,1,-1,2]那么12就是收取的利润则第一天买第二天卖第三天买第四天卖完全不用担心同一天出现用一天买卖的情况局部最优收集每天的正利润全局最优求最大利润值class Solution: def maxProfit(self, prices: List[int]) - int: res 0 for i in range(len(prices) - 1,-1,-1): prices[i] prices[i] - prices[i - 1] prices[0] 0 for i in range(len(prices)): if prices[i] 0: res prices[i] return res时间复杂度O(n)空间复杂度O(1)55. 跳跃游戏解题思路给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。题目例子nums [2,3,1,1,4]输出True先跳1步再跳三步nums [1,1,1]输出True跳一步再跳一步再跳一步nums [3,2,1,0,4]输出False不管怎么跳都到不了最后一步解题思路左脚踩右脚看能飞升到哪一步比如说例子1最大跳两步那么当前的范围是在[0,2]最大飞升到了下标2在这个范围里找右脚i1时可以跳三步此时范围是在[1,4]此时飞升到了下标4再看例子2左脚为下标0右脚踩一步到下标1左脚再站在下标1上右脚再踩一步到下标2也跳到了末尾再看例子3左脚为下标0右脚最大踩到了下标3在该区间里找左脚的落脚点下标为1右脚踩到下标3下标为2右脚踩到了下标3无法更进一步故返回Falseclass Solution: def canJump(self, nums: List[int]) - bool: index 0 cur 0 for i in range(len(nums)): if i index: cur i nums[i] index max(cur,index) if index len(nums) - 1: return True continue return False时间复杂度O(n),空间复杂度O(1)45. 跳跃游戏 II题目描述给定一个长度为n的0 索引整数数组nums。初始位置在下标 0。每个元素nums[i]表示从索引i向后跳转的最大长度。换句话说如果你在索引i处你可以跳转到任意(i j)处0 j nums[i]且i j n返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。题目例子nums [2,3,1,1,4]输出2从下标0跳到下标1再从下标1跳到下标4解题思路**局部最优统计每次最远覆盖范围全局最优最远覆盖范围的个数next_ max(next_,i nums[i])计算当前范围能覆盖的最远范围count用来统计当前范围的个数最后不需要再进行1class Solution: def jump(self, nums: List[int]) - int: if len(nums) 1: return 0 cur next_ 0 count 0 for i in range(len(nums)): next_ max(next_,i nums[i]) if i cur: count 1 cur next_ if next_ len(nums) - 1: break return count时间复杂度O(n)空间复杂度O(1)1005. K 次取反后最大化的数组和 - 力扣LeetCode题目描述给你一个整数数组nums和一个整数k按以下方法修改该数组选择某个下标i并将nums[i]替换为-nums[i]。重复这个过程恰好k次。可以多次选择同一个下标i。以这种方式修改数组后返回数组可能的最大和。题目例子nums [4,2,3],k 1输出5将2取反-2数组为nums[4,-2,3]结果为5解题思路对绝对值大的负数进行取反对绝对值小的正数进行取反特别注意的是当数组中只有正数时偶数次取反的结果是相同的只有奇数次才能取反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: k - 1 nums[i] * -1 #剩余k此时数组中都为正数取绝对值最小的进行取反 if k % 2 1: nums[-1] * -1 k - 1 return sum(nums)