python每日一题 贪心算法

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

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

意思就是我可以将这个数组中的k个元素进行加负号的变换 首先我先找数组中是负数的 找到我就给加上一个负号 将这个下标统计下来 然后如果负数的已经没了 看剩下的是 奇数还是偶数 如果是偶数 那么就直接将数组的所有值加起来就行（这样一看 貌似也不需要统计下标 因为是多变的）如果是奇数 看有没有0 如果有0的话 那么也可以直接返回数组和 如果没0 那么就找一个最小的正数 将其变为负数 统计数组和

OK 那么思路就是 先将数组中的所有元素变为正数 并且记录一个正数的最小值 先记下来  如果有元素 0 那么也记录下来 之后就不用再遍历一次了

然后看剩下的K是奇数还是偶数 如果是偶数 那不用管  如果是奇数 如果有0 那么直接统计 如果没有 将那个正数最小值加上一个负号 然后进行统计 （其实也可以在变为正数的时候直接统计和）

然后我就发现了问题 如果k的数目还没有数组中的负数多咋办 这样其实应该先将负数最小的先变为正的再说 

那不如直接对数组进行排序 排序之后从负数那边开始 将负数变为正数  然后如果全部变成正数 如果没0的话 只能对正数最小的进行消耗 那么再进行一次排序 即可 我有点担心这个会超出运行时间 但是还是先试试

class Solution(object):def largestSumAfterKNegations(self, nums, k):nums=sorted(nums)#首先进行排序Cl_0=Falsefor i in range(len(nums)):if nums[i]<0 :if k>=1:nums[i]=-nums[i]k-=1else:return sum(nums)elif nums[i]==0:Cl_0 = Truebreakelse:breakif Cl_0==True:return sum(nums)#如果没0,但是剩余的k是偶数个if k%2==0:return sum(nums)else:nums = sorted(nums)nums[0]=-nums[0]return sum(nums)solution=Solution()
result=solution.largestSumAfterKNegations([4,-2,-3],1)
print(result)

没超出运行时间 运行速度100% 思路就是先把负数变成正的 如果k不够 那直接return sum 就行 如果K够了 有0的话最好 如果没有0 那么就找一个正数最小的 

还好我今天的收尾是选择一个我擅长的并且简单的 不然又要破防了 大家晚安~