leetcode(力扣) 1005. K 次取反後最大化的數組和 (模拟情況分類)

文章目錄

• ​​題目描述:​​
• ​​思路分析:​​

• ​​完整代碼:​​

題目描述:

給你一個整數數組 nums 和一個整數 k ，按以下方法修改該數組：

選擇某個下标 i 并将 nums[i] 替換為 -nums[i] 。

重複這個過程恰好 k 次。可以多次選擇同一個下标 i 。

以這種方式修改數組後，傳回數組 可能的最大和 。

示例 1：

輸入：nums = [4,2,3], k = 1

輸出：5

解釋：選擇下标 1 ，nums 變為 [4,-2,3] 。

示例 2：

輸入：nums = [3,-1,0,2], k = 3

輸出：6

解釋：選擇下标 (1, 2, 2) ，nums 變為 [3,1,0,2] 。

示例 3：

輸入：nums = [2,-3,-1,5,-4], k = 2

輸出：13

解釋：選擇下标 (1, 4) ，nums 變為 [2,3,-1,5,4] 。

思路分析:

這道題本身不難，但是情況比較多，容易亂。

我寫了一個思路很清晰的if else代碼。。。。。

首先對所給數組進行排序。

明确一點:如果k為偶數，則可以讓數組中所有的數都不變換正負(拿一個數變換2次正負就行)

如果k為奇數，則隻需要變換一個數的正負。

各種情況

• 看排序後的第0個元素是否大于0，如果大于0則直接傳回數組的和。
• 如果最左邊的數小于0 ，則從左往右周遊開始将負數變為整數，執行k次，循環中當k等于0時傳回數組的和。
• 循環完如果k還是大于0則從新排序，再次判斷目前k是奇數還是偶數，偶數直接傳回數組的和，奇數則将最左邊的最小值減去傳回剩下的數的和。

• 直接看最左邊的最小值是否大于0，如果大于0，則将最左邊的最小值減去傳回剩下的數的和。
• 如果最左邊的值小于0，則和k為偶數的情況一樣，則從左往右周遊開始将負數變為整數，執行k次，循環中當k等于0時傳回數組的和。循環完如果k還是大于0則從新排序，再次判斷目前k是奇數還是偶數，偶數直接傳回數組的和，奇數則将最左邊的最小值減去傳回剩下的數的和。

完整代碼:

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        res = 0
        nums.sort()
        if k % 2 == 0:
            # 偶數的情況
            if nums[0] > 0:
                return sum(nums)
            else:
                # 有一個或更多的負值
                for p in range(len(nums)):
                    if nums[p] < 0:
                        nums[p] *= -1
                        k -=1
                        if k == 0:
                            return sum(nums)
                if k > 0:
                    nums.sort()
                    if k % 2 == 0:
                        return sum(nums)
                    else:
                        return sum(nums) - nums[0] - nums[0]
                return sum(nums)
        else:
            # 奇數的情況
            if nums[0] > 0:
                # 全部值都大于0.則值将最小的變成負數
                return sum(nums)- nums[0] - nums[0]
            else:
                # 有一個或更多的負值
                for p in range(len(nums)):
                    if nums[p] < 0:
                        nums[p] *= -1.
                        k -=1
                        if k == 0:
                            return sum(nums)
                if k > 0:
                    nums.sort()
                    if k % 2 == 0:
                        return sum(nums)
                    else:
                        return sum(nums) - nums[0] - nums[0]
                return sum(nums)