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

li508q / 2024-10-13 / 原文

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

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

LeetCode 55. 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        curr = cover = 0
        while curr <= cover:
            cover = max(cover, curr + nums[curr])
            if cover >= n - 1:
                return True
            curr += 1
        return False

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

LeetCode 45. 跳跃游戏 II

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        res = 1
        curr = cover = 0
        while curr <= cover:
            for i in range(curr, cover + 1):
                if cover < i + nums[i]:
                    cover = i + nums[i]
                    curr = i
            if cover >= n - 1:
                return res
            res += 1

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

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort(key = lambda x: abs(x), reverse = True)
        idx = 0
        while k > 0 and idx < n:
            if nums[idx] <= 0:
                nums[idx] = - nums[idx]
                k -= 1
            idx += 1
        if k % 2 == 1:
            nums[-1] *= -1
        return sum(nums)