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

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

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

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

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

示例 1:

• 输入: [7,1,5,3,6,4]
• 输出: 7
• 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

• 输入: [1,2,3,4,5]
• 输出: 4
• 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例  3:

• 输入: [7,6,4,3,1]
• 输出: 0
• 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

思路：核心是计算每一个极大值和极小值之间，递增部分的增值，那么也可以理解为计算整个数组区间递增部分的增值，所以计算极大值和极小值没有意义，我们只要关注相邻元素之间有递增的部分就可以了，即【只要第二天比前一天有提高，那就第一天买入第二天卖出】，这就是贪心的思路。

引代码随想录的解释，更清晰易懂：

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

代码实现如下：

class Solution:

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

        res = 0

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

            if prices[i] > prices[i-1]:

                res += prices[i] - prices[i-1]

        return res

规范代码：（更简洁）

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

动态规划:

class Solution:

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

        length = len(prices)

        dp = [[0] * 2 for _ in range(length)]

        dp[0][0] = -prices[0]

        dp[0][1] = 0

        for i in range(1, length):

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方

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

        return dp[-1][1]

55. 跳跃游戏

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

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

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

示例  1:

• 输入: [2,3,1,1,4]
• 输出: true
• 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例  2:

• 输入: [3,2,1,0,4]
• 输出: false
• 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路：

问题转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例，试试贪心！

代码实现如下：

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

       # 超时
       '''
       dp = [0] * len(nums)
       dp[0] = 1
       for i in range(len(nums)):
           if dp[i] == 0:
               return False
           for j in range(1, nums[i]+1):
               if i+j < len(nums):
                   dp[i+j] = 1
       return True
       #if dp[-1] == 1:
       #    return True
       #else:
       #    return False
       '''

规范代码：

class Solution:

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

        cover = 0

        if len(nums) == 1: return True

        i = 0

        # python不支持动态修改for循环中变量,使用while循环代替

        while i <= cover:

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

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

            i += 1

        return False

For循环写法：

## for循环class Solution:

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

        cover = 0

        if len(nums) == 1: return True

        for i in range(len(nums)):

            if i <= cover:

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

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

        return False

45.跳跃游戏 II

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

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

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

示例:

• 输入: [2,3,1,1,4]
• 输出: 2
• 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳  1  步，然后跳  3  步到达数组的最后一个位置。

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

错误思路： 想尝试用回溯，时间会超时，所以尝试剪枝，每次尝试取当前位置最远的步长，以为这样跳到的结果就一定是最少次数的，没有考虑当前位置到当前位置最短的步长位置【之间】可能会存在更大的步长，这应该是错误原因。本题一刷失败，看解析。

正确思路：

每一步都判断自己是否还在上一步更新的范围之内，同时更新这一步能够到达的最远距离范围。如果发现当前位置超出了上一步更新的范围，说明已经要走第二步，将【上一步】的范围更新成【第二步】能够到达的最远距离范围，而从现在开始（此时已经开始第二步）更新的就是【再下一步（第三步）】的最远距离范围，以此循环可以得到结果。

如果看不懂，学习传送门：

https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html#%E6%80%9D%E8%B7%AF

错误代码：

class Solution:
   def jump(self, nums: List[int]) -> int:
       if len(nums) == 1:
           return 0
       self.min = float('inf')
       if self.backtracking(nums, 0, 0):
           return self.min

   def backtracking(self, nums: List[int], start: int, cur:int):
       if start >= len(nums)-1:
           #self.min = min(self.min, cur)
           self.min = cur
           return True

       if cur >= self.min:
           return

       for i in range(nums[start]+1, 1, -1):
           if self.backtracking(nums, start+i, cur+1):
               return True

规范代码：

class Solution:

    def jump(self, nums):

        if len(nums) == 1:

            return 0

        

        cur_distance = 0  # 当前覆盖最远距离下标

        ans = 0  # 记录走的最大步数

        next_distance = 0  # 下一步覆盖最远距离下标

        

        for i in range(len(nums)):

            next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖最远距离下标

            if i == cur_distance:  # 遇到当前覆盖最远距离下标

                ans += 1  # 需要走下一步

                cur_distance = next_distance  # 更新当前覆盖最远距离下标（相当于加油了）

                if next_distance >= len(nums) - 1:  # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束

                    break

        

        return ans

        

贪心（版本二）

class Solution:

    def jump(self, nums):

        cur_distance = 0  # 当前覆盖的最远距离下标

        ans = 0  # 记录走的最大步数

        next_distance = 0  # 下一步覆盖的最远距离下标

        

        for i in range(len(nums) - 1):  # 注意这里是小于len(nums) - 1，这是关键所在

            next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖的最远距离下标

            if i == cur_distance:  # 遇到当前覆盖的最远距离下标

                cur_distance = next_distance  # 更新当前覆盖的最远距离下标

                ans += 1

        

        return ans

贪心（版本三） 类似‘55-跳跃游戏’写法

class Solution:

    def jump(self, nums) -> int:

        if len(nums)==1:  # 如果数组只有一个元素，不需要跳跃，步数为0

            return 0

        

        i = 0  # 当前位置

        count = 0  # 步数计数器

        cover = 0  # 当前能够覆盖的最远距离

        

        while i <= cover:  # 当前位置小于等于当前能够覆盖的最远距离时循环

            for i in range(i, cover+1):  # 遍历从当前位置到当前能够覆盖的最远距离之间的所有位置

                cover = max(nums[i]+i, cover)  # 更新当前能够覆盖的最远距离

                if cover >= len(nums)-1:  # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置，直接返回步数+1

                    return count+1

            count += 1  # 每一轮遍历结束后，步数+1

动态规划

class Solution:

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

        result = [10**4+1] * len(nums)  # 初始化结果数组，初始值为一个较大的数

        result[0] = 0  # 起始位置的步数为0

        for i in range(len(nums)):  # 遍历数组

            for j in range(nums[i] + 1):  # 在当前位置能够跳跃的范围内遍历

                if i + j < len(nums):  # 确保下一跳的位置不超过数组范围

                    result[i + j] = min(result[i + j], result[i] + 1)  # 更新到达下一跳位置的最少步数

        return result[-1]  # 返回到达最后一个位置的最少步数

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

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

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

示例 1：

• 输入：A = [4,2,3], K = 1
• 输出：5
• 解释：选择索引 (1) ，然后 A 变为 [4,-2,3]。

示例 2：

• 输入：A = [3,-1,0,2], K = 3
• 输出：6
• 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：

• 输入：A = [2,-3,-1,5,-4], K = 2
• 输出：13
• 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：

• 1 <= A.length <= 10000
• 1 <= K <= 10000
• -100 <= A[i] <= 100

思路：

本题贪心的思路是，首先对负数进行反转，而负数里最优先反转的就是负数中最小的数（绝对值越大负数越小）。所以我们首先进行第一次排序，然后根据所给的k（即反转次数）尽可能给从小到大的负数进行反转。另一种情况是所有负数都反转完但是反转次数k还没用完，此时要找出所有正数的最小值，所以再次进行排序，然后将所有的反转次数都给最小的一个数（如果所剩翻转为偶数，结果不影响，依然全部是正数；如果是奇数，被翻转为负数的数也是绝对值最小的数）

代码实现如下：

class Solution:

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

        nums.sort()

        cur = 0

        while cur < len(nums) and nums[cur] < 0 and k > 0:

            nums[cur] *= -1

            cur += 1

            k -= 1

        nums.sort()

        while k > 0:

            nums[0] *= -1

            k -= 1

        return sum(nums)

规范代码：

class Solution:

    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:

        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A

        for i in range(len(A)):  # 第二步：执行K次取反操作

            if A[i] < 0 and K > 0:

                A[i] *= -1

                K -= 1

        if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反

            A[-1] *= -1

        result = sum(A)  # 第四步：计算数组A的元素和

        return result

原文地址：https://blog.csdn.net/weixin_47681529/article/details/142886571

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！