Day 34 贪心：1005. K次取反, 134. 加油站, 135. 分发糖果

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

• 思路
  • example
  • 可以多次选择同一个下标 i 。
  • 排序 + 贪心
    • 负数（取反），非负数 （取决于频率）
      • [-1,-2,3] ----> [1,2,3] --> [-1,2,3] (k=3)
    • 计算负数个数
    • 负数取反
    • 新数组最小数字处理（取决于剩余次数的奇偶）
• 复杂度. 时间：O(n logn) 排序

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        negative_cnt = 0
        for i in range(n):
            if nums[i] < 0:
                negative_cnt += 1
            else:
                break 
        for i in range(min(negative_cnt, k)):
            nums[i] = - nums[i]
        rest = k - min(negative_cnt, k)
        if rest % 2 == 0:
            return sum(nums)
        return sum(nums) - 2*min(nums)

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort() # !!!
        n = len(nums)
        cnt = 0 
        for i in range(n):
            if nums[i] < 0:
                cnt += 1
        for i in range(min(cnt, k)):
            nums[i] = -nums[i] 
        k -= min(cnt, k)
        if k % 2 == 0:
            return sum(nums) 
        else:
            return sum(nums) - 2*min(nums)

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()  
        n = len(nums)  
        neg_cnt = 0
        for i in range(n):
            if nums[i] < 0:
                neg_cnt += 1
            else:
                break  
        sum_ = sum(nums)  
        for i in range(min(neg_cnt, k)):
            nums[i] = -nums[i]
            sum_ += 2*(nums[i]) 
        k -= neg_cnt  
        if k <= 0:
            return sum_ 
        if k % 2 == 0:
            return sum_ 
        return sum_ - 2*min(nums)

• 桶计数 + 贪心，时间: O(n+201)
  • 利用 -100 <= nums[i] <= 100

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        res = sum(nums)
        table = collections.defaultdict(int)
        for num in nums:
            table[num] += 1
        for num in range(-100, 0):
            if table[num] > 0:
                freq = min(table[num], k)
                res -= 2*freq*num 
                table[num] -= freq 
                table[-num] += freq 
                k -= freq 
                if k == 0:
                    return res 
        for num in range(0, 101):
            if table[num] > 0:
                if k % 2 == 0:
                    return res 
                else:
                    res -= 2*num  
                    return res 

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        sum_ = sum(nums)
        freq = collections.defaultdict(int)   
        for num in nums:
            freq[num] += 1 
        for num in range(-100, 0):
            if freq[num] == 0:
                continue   
            times = min(k, freq[num]) 
            sum_ -= 2*num*times  
            freq[num] -= times  
            freq[-num] += times  
            k -= times  
            if k == 0:
                return sum_  
        for num in range(0, 101):
            if freq[num] == 0:
                continue 
            if k % 2 == 0:
                return sum_  
            else:
                return sum_ - 2*num 

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        n = len(nums) 
        sum_ = sum(nums) 
        table = collections.defaultdict(int) 
        for i in range(n):
            table[nums[i]] += 1
        for num in range(-100, 0):
            if table[num] == 0: #!!!
                continue 
            freq = min(k, table[num]) 
            table[num] -= freq #!!!
            table[-num] += freq #!!!
            sum_ -= 2*freq*num
            k -= freq 
            if k == 0:
                return sum_ 
        for num in range(0, 101):
            if table[num] > 0:
                if k % 2 == 0:
                    return sum_ 
                else:
                    return sum_ - 2*num 

• 大根堆/小根堆

TBA

134. 加油站

• 思路
  • example
  • 如果题目有解，该答案即为唯一答案。
  • 暴力法: 遍历每一个加油站当作起点。模拟跑圈。
• 复杂度. 时间：, 空间:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for i in range(len(gas)):
            rest = gas[i] - cost[i]
            nxt = (i+1) % len(gas)
            while rest > 0 and nxt != i: 
                rest += gas[nxt] - cost[nxt]
                nxt = (nxt+1) % len(gas)
            if rest >= 0 and nxt == i: 
                return i 
        return -1

• 贪心法
  • time: , space:
  • if sum(gas) < sum(cost): return -1 否则必有答案。
  • 假设index为答案，则必有index, index+1, ..., index+k中剩余和 >= 0, 并且对之间的每个指标，剩余都是 >= 0
    • 从i出发顺序遍历，一旦碰到j，使得当前剩余和 < 0,说明i,..., j-1全部不可能是起始点。（反证法）

    • 所以实际只需一次遍历即可。

      
      

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1 
        n = len(gas)
        balance = 0
        index = 0
        for i in range(n):
            balance += gas[i] - cost[i] # “到达”i+1时的balance
            if balance < 0:
                balance = 0
                index = i + 1
        return index 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas) 
        diff = [0 for _ in range(n)]
        for i in range(n):
            diff[i] = gas[i] - cost[i] 
        if sum(diff) < 0:
            return -1
        balance = 0
        start = 0
        for i in range(n):
            balance += diff[i] # can we reach station i+1?
            if balance < 0:
                balance = 0 # restart, stations start, ..., i cannot be the answer
                start = i+1 
        return start 

135. 分发糖果

• 思路

  • example

  • 返回需要准备的 最少糖果数目

    
    

  • 从左到右遍历，依据左邻居信息更新candy数组。

  • 从右到左遍历，依据右邻居信息更新candy数组。

    
    
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candys = [1 for _ in range(len(ratings))]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                candys[i] = candys[i-1] + 1
            # else: candys[i] = 1
        for i in range(len(ratings)-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candys[i] = max(candys[i], candys[i+1]+1)
        return sum(candys)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)  
        candies = [1 for _ in range(n)]
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candies[i] = candies[i-1] + 1
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                if candies[i] < candies[i+1] + 1:
                    candies[i] = candies[i+1] + 1
        return sum(candies)

• 小根堆?

TBA