Code Caprice Algorithm Training Camp Day 33 || 1005. Array Sum Maximized After K Negations || 134. Gas Station || 135. Distributing Candy
1005. The array sum maximized after K times inversion
Topic introduction:
Given an integer array nums and an integer k , modify the array as follows:
- Select some subscript i and replace nums[i] with -nums[i] .
Repeat this process exactly k times. The same subscript i can be selected multiple times.
After modifying the array in this way, return the largest possible sum of the array.
Example 1:
enter: nums = [4,2,3], k = 1 Output: 5 Explanation: Select subscript 1 , nums becomes [4,-2,3] .
Example 2:
enter: nums = [3,-1,0,2], k = 3 Output: 6 Explanation: select subscript (1, 2, 2) ，nums becomes [3,1,0,2] .
Example 3:
enter: nums = [2,-3,-1,5,-4], k = 2 Output: 13 Explanation: select subscript (1, 4) ，nums becomes [2,3,-1,5,4] .
Personal thoughts:
- Sort the array first, then reverse the negative numbers according to the starting subscript
- If the number of negative numbers > k, the k number is reversed normally, and then the remaining elements can be traversed
- The number of negative numbers < k, after reversing all negative numbers, check whether the remaining times are odd or even
- If it is an even number, there is no need to reverse
- If it is an odd number, you only need to reverse a positive number, compare the absolute value of the current element and the previous element, and reverse the smaller one
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int result = 0;
Arrays.sort(nums);
int i = 0;
for (; i < k && i < nums.length; i++) {
if (nums[i] >= 0)
break;
nums[i] = Math.abs(nums[i]);
result += nums[i];
}
if ((k - i) % 2 == 1) {//odd number of inversions left
//1. The array has been traversed (it must be a negative number, that is, its absolute value is the smallest) ---> reverse the last one
//2.1 The array has not been traversed completely, compare the absolute value of the two values at the positive and negative boundaries, and the absolute value of the negative number is larger
//2.2 The first number of the array is a positive number, at the boundary, the absolute value of the positive number is large
if (i >= nums.length || i > 0 && nums[i] > nums[i - 1])
result -= 2 * nums[i - 1];
else nums[i] *= (-1);
}
//iterate over remaining elements
for (; i < nums.length; i++) {
result += nums[i];
}
return result;
}
}
Solution analysis:
Sort the array by absolute value, traverse from the larger side, and reverse when encountering a negative number
If there are more reversal times at the end, then perform different operations depending on whether the number of times is odd or even
Odd numbers reverse the last number, even numbers do not
134. Gas station
Topic introduction:
There are n gas stations on a loop, and the i-th gas station has gas[i] liters of gasoline.
You have a car with unlimited fuel tank capacity, and it takes cost[i] liters of gasoline to drive from the i-th gas station to the i+1-th gas station. You start off from one of the gas stations, starting with an empty tank.
Given two integer arrays gas and cost , return the number of the gas station at the time of departure if you can drive around the loop, otherwise return -1 . If a solution exists, it is guaranteed to be unique.
Example 1:
enter: gas = [1,2,3,4,5], cost = [3,4,5,1,2] output: 3 Explanation: From Gas Station 3(Indexed at 3 places)Go and get 4 liters of petrol. At this time the fuel tank has = 0 + 4 = 4 Liters of gasoline Drive to gas station 4, now the tank has 4 - 1 + 5 = 8 Liters of gasoline Drive to gas station 0, at this time the tank has 8 - 2 + 1 = 7 Liters of gasoline Drive to gas station 1, now the tank has 7 - 3 + 2 = 6 Liters of gasoline Drive to gas station 2, now the tank has 6 - 4 + 3 = 5 Liters of gasoline Driving to gas station 3, you need to consume 5 liters of gasoline, just enough to get you back to gas station 3. Therefore, 3 can be the starting index.
Example 2:
enter: gas = [2,3,4], cost = [3,4,3] output: -1 Explanation: You can't start from gas station 0 or 1 because there isn't enough gas to get you to the next gas station. We start from gas station 2 and get 4 liters of petrol. At this time the fuel tank has = 0 + 4 = 4 Liters of petrol Drive to gas station 0, at this time the fuel tank has 4 - 3 + 2 = 3 Liters of petrol Drive to gas station 1, at this time the tank has 3 - 3 + 3 = 3 Liters of petrol You can't go back to gas station 2, because the return trip takes 4 liters of gas, but you only have 3 liters of gas in your tank. So, no matter what, you can't drive around the loop.
Personal thoughts:
First, we need to use several parameters to record some key information
int result = 0;//Record departure subscript int excess_sum = 0;//After traversing the whole process, the remaining oil int[] excess_gas = new int[gas.length];//Record the difference between refueling and fuel consumption at each place int[] sum_gas = new int[gas.length];//The current subscript records the remaining oil from a certain point to the current point
Then, we traverse the whole process through a for loop, and constantly refresh the sum_gas during the process. When it is negative, re-determine the starting point and continue the loop process
If there is a certain point that can go through the entire cycle, it must be encountered during the traversal process; conversely, the result at the end of the traversal is not necessarily the result, we have to see whether the excess_sum is non-negative
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int result = 0;//Record departure subscript
int excess_sum = 0;//After traversing the whole process, the remaining oil
int[] excess_gas = new int[gas.length];//Record the difference between refueling and fuel consumption at each place
int[] sum_gas = new int[gas.length];//The current subscript records the remaining oil from a certain point to the current point
for (int i = 0; i < gas.length; i++) {
excess_gas[i] = gas[i] - cost[i];
sum_gas[i] = i == 0 ? excess_gas[i] : excess_gas[i] + sum_gas[i - 1];
excess_sum += excess_gas[i];
if (sum_gas[i] < 0) {
sum_gas[i] = 0;
result = i + 1;
}
}
return excess_sum >= 0 ? result : -1;
}
}
Solution analysis:
Method 1: A very ingenious method, but not greedy, just understand
- Situation 1: If the sum of gas is less than the sum of cost, no matter where you start from, you must not be able to run around
- Situation 2: rest[i] = gas[i]-cost[i] is the oil left in one day, i starts to calculate and accumulate from 0 to the last station, if the accumulation does not show a negative number, it means that starting from 0, the oil has not been cut off However, then 0 is the starting point.
- Situation 3: If the accumulated minimum value is a negative number, the car will start from a non-zero node, from the back to the front, to see which node can fill up the negative number, and the node that can fill up the negative number is the starting node. Conversely, if traversing the point in positive order can fill in the smallest negative number, then the whole journey must be completed later, because the whole is enough oil
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int min = INT_MAX; // Starting from the starting point, the minimum amount of fuel in the tank
for (int i = 0; i < gas.size(); i++) {
int rest = gas[i] - cost[i];
curSum += rest;
if (curSum < min) {
min = curSum;
}
}
if (curSum < 0) return -1; // Case 1
if (min >= 0) return 0; // Case 2
// Case 3
for (int i = gas.size() - 1; i >= 0; i--) {
int rest = gas[i] - cost[i];
min += rest;
if (min >= 0) {
return i;
}
}
return -1;
}
};
Method 2: Similar to my idea, but the code has been optimized a lot
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int result = 0;//Record departure subscript
int excess_sum = 0;//After traversing the whole process, the remaining oil
int curSum = 0;//The current subscript records the remaining oil from a certain point to the current point
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
excess_sum += gas[i] - cost[i];
if (curSum < 0) {
curSum = 0;
result = i + 1;
}
}
return excess_sum >= 0 ? result : -1;
}
}
135. Handing out candy
Topic introduction:
n children stand in a row. You are given an integer array ratings representing each child's rating.
You need to distribute candy to these children according to the following requirements:
- Each child is assigned at least 1 candy.
- The child with the higher score of two adjacent children gets more candies.
Please distribute candies to each child, calculate and return the minimum number of candies that need to be prepared.
Example 1:
enter: ratings = [1,0,2] Output: 5 Explanation: You can distribute 2, 1, and 2 candies to the first, second, and third child, respectively.
Example 2:
enter: ratings = [1,2,2]
Output: 4
Explanation: You can distribute 1, 2, and 1 candy to the first, second, and third child, respectively.
The third child only gets 1 candy, which satisfies the two conditions in the problem.
Personal thoughts:
My idea is to mark from the starting point, traverse the relative up and down position of each point of the mark, the subscript 0 is 0, the larger one is +1 than the previous number, and the small one is -1,
However, the handling of equality is more complicated. Think of anti-monotonic change (), but if you encounter many consecutive children with the same grades, you have to consider it again. The time reason directly depends on the problem solution
Solution analysis:
Note: The title says that if it is bigger than the adjacent one, it will get more candies than him. If they are the same, there is no such restriction. Adjacent to this condition we can divide into two sides to consider
We can compare one side first and then compare the other side. If a traversal compares both sides at the same time, it will definitely be out of balance.
Local optimum: As long as the child on the right is bigger than the child on the left, the child on the right will get one more candy. Global optimum: Among the adjacent children, the right child with a higher score will get more candies than the left child.
step:
- We first traverse in positive order from the first position, compare to the right, and get the global optimum of only one side, but at this time the condition for comparing to the left is not satisfied
- Traversing in reverse order from the end and comparing to the left can also get the results one by one. In the process, we need to keep the larger result compared with the result of the forward order traversal (it can meet the conditions of adjacent comparison)
The leftward comparison cannot traverse from the first part, otherwise the process of the first step will be repeated, which is meaningless
class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
for (int i = 0; i < candy.length; i++) {
if (i > 0 && ratings[i] > ratings[i - 1])
candy[i] = candy[i - 1] + 1;
else candy[i] = 1;
}
for (int i = candy.length - 1; i > 0; i--) {
if (ratings[i] < ratings[i - 1])
candy[i - 1] = Integer.max(candy[i] + 1, candy[i - 1]);
}
int nums = 0;
for (int i = 0; i < candy.length; i++) {
nums += candy[i];
}
return nums;
}
}