📒 Blog home page: A professional who advocates learning technology
🍣 Today's article is "game 280 of LeetCode" 🍣
🍣 I hope you can finish reading this article patiently 🍣
🙏 Bloggers are also in the learning stage. If you find any problems, please let us know. Thank you very much 🙏
💗 At the same time, thank you very much for your support 💗
<1> First question
subject
Give you two nonnegative integers num1 and num2.
In each step of operation, if num1 > = num2, you must subtract num2 from num1; Otherwise, you must subtract num1 from > num2.
- For example, if num1 = 5 and num2 = 4, you should subtract num2 from num1, so you get num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1 are obtained.
Returns the operand that makes num1 = 0 or num2 = 0.
Examples
- Example 1:
Input: num1 = 2, num2 = 3 Output: 3 Explanation: - Operation 1: num1 = 2 ，num2 = 3 . because num1 < num2 ，num2 reduce num1 obtain num1 = 2 ，num2 = 3 - 2 = 1 . - Operation 2: num1 = 2 ，num2 = 1 . because num1 > num2 ，num1 reduce num2 . - Operation 3: num1 = 1 ，num2 = 1 . because num1 == num2 ，num1 reduce num2 . here num1 = 0 ，num2 = 1 . because num1 == 0 ，No further action is required. So the total operand is 3.
- Example 2:
Input: num1 = 10, num2 = 10 Output: 1 Explanation: - Operation 1: num1 = 10 ，num2 = 10 . because num1 == num2 ，num1 reduce num2 obtain num1 = 10 - 10 = 0 . here num1 = 0 ，num2 = 10 . because num1 == 0 ，No further action is required. So the total operand is 1.
Tips
- 0 <= num1, num2 <= 10^5
⭐ thinking ⭐
- thinking
This question is a sign in question. My practice is to simulate this process. When num1 > num2, num1 = num1 - num2 and count; When num1 < num2, we count num2 = num2 - num1; If the two numbers are equal, count and exit the loop.
code implementation
class Solution {
public int countOperations(int num1, int num2) {
int cnt = 0;
while(num1 != 0 && num2 != 0){
if(num1 > num2){
num1 = num1 - num2;
}else if(num1 < num2){
num2 = num2 - num1;
}else{
cnt ++;
break;
}
cnt++;
}
return cnt;
}
}
Operation results
<2> Second question
subject
The minimum number of operands to make an array an alternating array
Give you an array num with subscript starting from 0, which is composed of n positive integers.
The array nums is an alternating array if the following conditions are met:
- nums[i - 2] == nums[i], where 2 < = I < = n - 1.
- nums[i - 1] != nums[i], where 1 < = I < = n - 1.
In one step, you can select the subscript i and change num [i] to any positive integer.
Returns the minimum number of operands that make an array an alternating array.
Examples
- Example 1:
Input: nums = [3,1,3,2,4,3] Output: 3 Explanation: One way to turn an array into an alternating array is to convert the array to [3,1,3,1,3,1] . In this case, the operand is 3. It can be proved that when the operand is less than 3, the array cannot be turned into an alternating array.
- Example 2:
Input: nums = [1,2,2,2,2] Output: 2 Explanation: One way to turn an array into an alternating array is to convert the array to [1,2,1,2,1]. In this case, the operand is 2. Note that arrays cannot be converted to [2,2,2,2,2] . Because in this case, nums[0] == nums[1]，The condition of alternating array is not satisfied.
Tips
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 105
⭐ thinking ⭐
- thinking
Because our main purpose here is to count the number of odd and even subscripts, and then select the largest number in the number of odd and even subscripts as the number we want to modify to. Therefore, we need to sort the number of occurrences from large to small. If you use a hash table, you cannot sort by the number of occurrences. After sorting, if the number with the most occurrences is not equal, we can directly use these two numbers; Otherwise, we need to select the number with the largest number of occurrences to find the minimum value and return.
code implementation
class Solution {
public int minimumOperations(int[] nums) {
int[][] cnt1 = new int[100010][2];
int[][] cnt2 = new int[100010][2];
for(int i = 0; i < cnt1.length; i ++){
cnt1[i][0] = i;
cnt2[i][0] = i;
}
for(int i = 0; i < nums.length; i ++){
if(i % 2 == 0){
cnt1[nums[i]][1] ++;
}else if(i % 2 == 1){
cnt2[nums[i]][1] ++;
}
}
Arrays.sort(cnt1,(a1,b1) -> b1[1] - a1[1]);
Arrays.sort(cnt2,(a1,b1) -> b1[1] - a1[1]);
if(cnt1[0][0] != cnt2[0][0]) return nums.length - (cnt1[0][1] + cnt2[0][1]);
return nums.length - Math.max(cnt1[0][1] + cnt2[1][1], cnt1[1][1] + cnt2[0][1]);
}
}
Operation results
<3> Question 3
subject
Take out the smallest number of magic beans
Give you a positive integer array beans, where each integer represents the number of magic beans in a bag.
Please take out some beans from each bag (or not), so that the number of magic beans in the remaining non empty bag (i.e. the bag with at least one magic bean) is equal. Once the magic bean is removed from the bag, you can't put it in any other bag.
Please return to the minimum number of magic beans you need to take out.
Examples
- Example 1:
Input: beans = [4,1,6,5] Output: 4 Explanation: - We took out a magic bean from the bag with a magic bean. The number of magic beans in the remaining bag is:[4,0,6,5] - Then we took out two magic beans from the bag with six magic beans. The number of magic beans in the remaining bag is:[4,0,4,5] - Then we took out one magic bean from the bag with five magic beans. The number of magic beans in the remaining bag is:[4,0,4,4] A total of 1 + 2 + 1 = 4 The number of magic beans in the remaining non empty bag is equal. There is no less than taking out four magic beans.
- Example 2:
Input: beans = [2,10,3,2] Output: 7 Explanation: - We took out two magic beans from one of the bags with two magic beans. The number of magic beans in the remaining bag is:[0,10,3,2] - Then we took out two magic beans from another bag with two magic beans. The number of magic beans in the remaining bag is:[0,10,3,0] - Then we took out three magic beans from the bag with three magic beans. The number of magic beans in the remaining bag is:[0,10,0,0] A total of 2 + 2 + 3 = 7 The number of magic beans in the remaining non empty bag is equal. There is no plan less than taking out seven magic beans.
Tips
- 1 <= beans.length <= 105
- 1 <= beans[i] <= 105
⭐ thinking ⭐
- thinking
What we do here is to enumerate all possible values in the beans array, then set the number less than beans[i] to 0, and reduce the number greater than beans[i] to beans[i]. Here, we preprocess a prefix and array for assistance, and then find the minimum value.
code implementation
class Solution {
public long minimumRemoval(int[] beans) {
/**
This problem is similar to the problem of resetting the sequence of numbers in the weekly competition in acwing. Its problem is the number of operations required to change all numbers into the same number, but here it is that we can operate on numbers in an interval. Its practice is to enumerate numbers in all ranges
*/
long ans = Long.MAX_VALUE;
int len = beans.length;
long[] s = new long[len + 1];
Arrays.sort(beans);
for(int i = 1; i <= len; i ++) s[i] = s[i - 1] + beans[i - 1];
for(int i = 0; i < len; i ++){
ans = Math.min(ans,s[i + 1] + (s[len] - s[i + 1]) - (long)beans[i] * (len - i));
}
return ans;
}
}
Operation results
