LeetCode Day 34 (Day 33 is rest day) Greedy Algorithm (3/6)

Its 3rd day of greedy algorithm practice.

Question 1

1005. Maximize Sum Of Array After K Negations

Given an integer array nums and an integer k, modify the array in the following way:

• choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

A list of numbers, changed k times, in order to maximise the value at the end of the list, so the number with the largest absolute value among the negative numbers should be changed first, followed by 0, which will maximise the result or have no effect on the sum.

When a series is all positive, it is again important to change the number with the smallest absolute value so that the sum decreases as little as possible. These are all greedy ideas.

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

Question 2

134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

The test case has confirmed that the result is unique, so it can be simply confirmed that there is a solution: that is, if the fuel added is greater than the distance to the petrol station, then the question may have a solution.

When traversing, traversing from beginning to end is suitable for for traversing, while for looping from beginning to end is suitable for while.

Another way to simplify the idea is to keep track of the amount of fuel accumulated from the beginning, and if there is a place where the amount of fuel reaches a negative value, then that place can’t be used as the starting point, or else the fuel will run out.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0  
        totalSum = 0  
        start = 0 
        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]
            
            if curSum < 0: 
                start = i + 1 
                curSum = 0 
        if totalSum < 0:
            return -1  
        return start

Question 3

135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Starting with one side of the traversal, just make sure that for adjacent children, the one with the higher score is assigned one more sugar than the one with the lower score, and the number of sugars can even be less if the adjacent scores are the same.

Then traverse in the opposite direction, making sure that a child with an adjacent score on the other side.

Both directions can’t be traversed at the same time or you’ll lose sight of the other side of the equation

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