Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.
The title
1753. Maximum score for removing stones
You are playing a single player game and are presented with three piles of pebbles of size A, B and C.
Each round you take a stone from two different non-empty piles and add one point to your score. The game stops when there are two or more empty heaps.
Given three integers A, B, and C, return the maximum score you can get.
Example 1:
Input: A = 2, b = 4, c = 6 Output: 6 Explanation: The initial state of the pebble is (2, 4, 6), and the optimal operation is: So let's take the pebbles from the first and third heaps, and now we have (1, 4, 5) pebbles from the first and third heaps, so let's take the pebbles from the second and third heaps, So we're going to have (0, 2, 2) -- we're going to have (0, 1, 1) -- we're going to have (0, 0, 0) -- we're going to have (0, 0, 0).Copy the codeExample 2:
Input: A = 4, b = 4, c = 6 Output: 7 Explanation: The initial state of the pebble is (4, 4, 6), and the optimal operation is: So let's take the pebbles from the first and second heaps, and now we have (3, 3, 6) -- let's take the pebbles from the first and third heaps, So we're going to have (0, 3, 3) -- we're going to have (0, 2, 2) -- we're going to have (0, 1, 1) -- we're going to have (0, 0, 0) -- we're going to have (0, 0, 0).Copy the codeExample 3:
Input: A = 1, b = 8, C = 8 Output: 8 Explanation: The optimal set of operations is to take 8 consecutive turns from the second and third heap until they are empty. Notice that since the second and third piles are empty, the game is over and we can't continue to take pebbles from the first pile.Copy the code
Tip:
1 <= a, b, c <= 105
Train of thought
- The problem of eliminating stones is usually solved by greed. What is greed? That you can eliminate with large values rather than small values;
- We can first order the three elements directly, and then determine the boundary condition, that is, the sum of the first two numbers is less than the third number, then directly return the sum of the first two numbers can be;
- We take the maximum and we subtract the minimum, and we figure out how many elements we need to keep, and there may or may not be anything left in the middle, but anyway, when we subtract the difference, we find that the minimum is now the maximum. Then do the same until you have two elements
0Can.
implementation
/ * * *@param {number} a
* @param {number} b
* @param {number} c
* @return {number}* /
var maximumScore = function(a, b, c) {
let result = 0;
let arr = [a, b, c].sort((a, b) = > a - b);
// Both of them add up
if (arr[0] + arr[1] <= arr[2]) {
return arr[0] + arr[1];
}
while (arr.length > 1) {
// When the maximum value is equal to 1, it is the last time to eliminate
if (arr[arr.length - 1= = =1) {
return result + 1;
}
// Eliminate the Max - min difference each time
let temp = arr[arr.length - 1] - arr[0];
// When the maximum and minimum values are equal, the last time to eliminate
if (temp === 0) {
// If all three numbers are equal, the last two numbers divide half to eliminate the first number, and then they kill each other
// In this way, both parts are less than half of each other
if (arr.length === 3) {
result += Math.floor(arr[0] / 2);
}
return result + arr[0];
}
// The result accumulates
result += temp;
// The last two elements perform elimination
arr[arr.length - 1] -= temp;
arr[arr.length - 2] -= temp;
// remove values equal to 0
arr = arr.filter(v= > v > 0);
// The minimum value is now the maximum value
arr.length > 1 && arr.push(arr.shift());
}
return result;
};
Copy the codeThe first version of the code, the idea has been realized, but as a result of writing a lot of redundant code, it seems not intuitive, so the code to do a simplification and optimization.
Code optimization
/ * * *@param {number} a
* @param {number} b
* @param {number} c
* @return {number}* /
var maximumScore = function(a, b, c) {
let result = 0;
let arr = [a, b, c].sort((a, b) = > a - b);
// Both of them add up
if (arr[0] + arr[1] <= arr[2]) {
return arr[0] + arr[1];
}
while (arr.length === 3) {
// Eliminate the Max - min difference each time
let temp = arr[arr.length - 1] - arr[0];
// When the maximum and minimum values are equal, the last time to eliminate
if (temp === 0) {
return result + arr[0] + Math.floor(arr[0] / 2);
}
// The result accumulates
result += temp;
// The last two elements perform elimination
arr[arr.length - 1] -= temp;
arr[arr.length - 2] -= temp;
// If only two digits are left, return directly
if (arr[arr.length - 2= = =0) {
return result +arr[arr.length - 1];
}
// The minimum value is now the maximum value
arr.push(arr.shift());
}
return result;
};
Copy the codeThe results of
Looking for a regular
Of course, this problem can also be eliminated by using the method of finding rules in mathematics. We will find that when the sum of the first two numbers is greater than the third number, only one will be eliminated if the final sum is odd, and only one will be eliminated if the sum is even. Therefore, we can directly take all values and round down.
Mathematical code
/ * * *@param {number} a
* @param {number} b
* @param {number} c
* @return {number}* /
var maximumScore = function(a, b, c) {
let arr = [a, b, c].sort((a, b) = > a - b);
// Both of them add up
if (arr[0] + arr[1] <= arr[2]) {
return arr[0] + arr[1];
}
return Math.floor((arr[0] + arr[1] + arr[2) /2);
};
Copy the codeIf you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.