您现在的位置是：首页 >技术杂谈 >代码随想录算法训练营第三十三天| 贪心算法02网站首页技术杂谈

122. 买卖股票的最佳时机II

本题解法很巧妙， 本题大家可以先自己思考一下然后再看题解，会有惊喜！

题目及解析：代码随想录

这道题挺容易的，一次ac，每次后一天减前一天是否有正收益，有即累加，可得到最大利益

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=0
        for i in range(1,len(prices)):
            profit=max(prices[i]-prices[i-1]+profit,profit)
        return profit

55. 跳跃游戏

本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解

代码随想录

count用来表示当前能到达的最远距离，遍历数组，比较count和在当前位置能跳到的最远距离的大小

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        count=0
        for i in range(len(nums)):
            if i<=count:
                count=max(count,i+nums[i])
            if count>=len(nums)-1:
                return True
        return False

45. 跳跃游戏II

本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。

代码随想录

max_length表示当前点能到达的最远距离，end表示最远距离，只要是i<end，那计数就只用加1，如果i==end，那么end就需要往后挪，如果end到达末尾，则返回计数

class Solution:
    def jump(self, nums: List[int]) -> int:
        max_length=0
        count=0
        end=0
        for i in range(len(nums)-1):
            max_length=max(max_length,i+nums[i])
            if i==end:
                count+=1
                end=max_length
                if end>=len(nums)-1:
                    return count
        return count

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

本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。

代码随想录

 注意点：

1. 对nums进行排序时，要按绝对值大小排序

2. 遍历数组要从末到首，这样可以保证翻转时为绝对值最大的负数

3. 若有多余的k，为奇数时则翻转最小的，为偶数不动

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=abs)
        for i in range(len(nums)-1,-1,-1):
            if k>0 and nums[i]<0:
                nums[i]=-nums[i]
                k-=1
        if k%2!=0:
            nums.sort()
            nums[0]=-nums[0]
        return sum(nums)