代码随想录算法训练营第二十八天 | 买卖股票的最佳实际、跳跃游戏、K次取反后最大化的数组和

买卖股票的最佳时机：

        这里可以得到当有利润就会卖出得到当前的股票，然后就是向后移动一位就可以了，判断卖出那天买入，后一天卖出会不会有收益，有收益就加上，因为同一天的买入和卖出相当于没有操作，因此逻辑性不变，详细代码如下所示：

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""if len(prices) <=1:return 0count = 0pre = 0cur = 1while(pre<len(prices)-1):if prices[cur] - prices[pre] > 0:count += prices[cur] - prices[pre]pre+=1cur+=1return count

跳跃游戏

        这里的思路是不断更新覆盖范围，看覆盖大小是不是一在更新，如果说覆盖范围到达最后的元素，那么符合，但是如果到了覆盖范围的最后一个还没有到达目的地，那么就不可行，直接返回False，详细代码如下所示：

class Solution(object):def canJump(self, nums):""":type nums: List[int]:rtype: bool"""if len(nums)<=1:return Truecover = 0index = 0while(index<=cover):cover = max(cover,nums[index]+index)if cover >= len(nums) - 1:return Trueindex+=1return False

K次取反后最大化的数组和

        思路如下，我觉得还是比较好的：

        1.​​预处理排序​​：先排序，再按策略翻转，避免重复计算最小值。
        2.​​优先处理负数​​：先翻转所有负数（因为翻转负数能直接增加总和）。
        3.​​剩余次数的数学处理​​：若剩余翻转次数 k 为奇数，只需翻转当前最小元素一次。

详细代码如下所示：

class Solution(object):def largestSumAfterKNegations(self, nums, k):nums.sort()  # 排序，O(n log n)# 第一阶段：优先翻转所有负数for i in range(len(nums)):if nums[i] < 0 and k > 0:nums[i] = -nums[i]k -= 1# 第二阶段：若剩余k为奇数，翻转当前最小元素（可能是0）if k % 2 == 1:nums.sort()  # 重新排序找到最小值nums[0] = -nums[0]return sum(nums)  # 总和计算，O(n)

        由于浏览器清空内存之后，原有代码会消失，因此此处链接放的是代码随想录的链接。