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

122.买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

---

class Solution:

    def maxProfit(self, prices: List[int]) -> int:

        result=0

        for i in range(1,len(prices)):

            result+=max(prices[i]-prices[i-1],0)

        return result

55.跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

---

class Solution:

    def canJump(self, nums: List[int]) -> bool:

        if len(nums)==1: return True

        cover=0

        i=0

        while i<=cover:

            cover=max(i+nums[i],cover)

            if cover>=len(nums)-1: return True

            i+=1

        return False

45.跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明: 假设你总是可以到达数组的最后一个位置

---

class Solution:

    def jump(self, nums: List[int]) -> int:

        if len(nums)==1: return 0

        cur=0

        next=0

        ans=0

        for i in range(len(nums)):

            next=max(next,i+nums[i])

            if i==cur:

                ans+=1

                cur=next

                if cur>=len(nums)-1:

                    break

        return ans 

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

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

以这种方式修改数组后，返回数组可能的最大和。

---

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:

                #如果直接用i的话，局部变量改变不影响原值

                nums[i]*=-1

                k-=1

        if k%2==1:

            nums[-1]*=-1

        return sum(nums)