文章目录
- 题目描述:
- 思路分析:
- 完整代码:
题目描述:
给你一个整数数组 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)