Game 280 of leetcode week

Blog's front page ： Those who advocate learning technology
Today's article is 《LeetCode The first 280 Weekly match 》
I hope you guys can finish reading this article patiently
Bloggers are also in the learning stage , If problems are found , Please inform , Thank you very much
At the same time, thank you very much for your support

<1> The first question is

subject

obtain 0 The number of operations

Here are two for you non-negative Integers num1 and num2 .
Each step operation in , If num1 >= num2 , You have to use num1 reduce num2 ; otherwise , You have to use > num2 reduce num1 .

• for example ,num1 = 5 And num2 = 4 , Should use the num1 reduce num2 , therefore , obtain num1 = 1 and num2 = 4. However , If num1 = 4 And num2 = 5 , After one step operation , obtain num1 = 4 and num2 = 1 .

Return to make num1 = 0 or num2 = 0 Of Operands .

Example

• Example 1：

 Input ：num1 = 2, num2 = 3
 Output ：3
 explain ：
-  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 more action is required .
 So the total operand is  3 .

• Example 2：

 Input ：num1 = 10, num2 = 10
 Output ：1
 explain ：
-  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 more action is required .
 So the total operand is  1 .

Tips

• 0 <= num1, num2 <= 10^5

Ideas

• Ideas

This question is a sign in question , My approach is to simulate this process , When num1 > num2 when , it num1 = num1 - num2 And count ; When num1 < num2 when , We will num2 = num2 - num1 And count ; 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;
    }
}

Running results

<2> The second question is

subject

The minimum number of operands to make an array an alternating array

I'll give you a subscript from 0 Starting array nums , The array consists of n It's made up of four positive integers .
If the following conditions are met , The array nums It's a Alternating array ：

• nums[i - 2] == nums[i] , among 2 <= i <= n - 1 .
• nums[i - 1] != nums[i], among 1 <= i <= n - 1 .

In one step operation in , You can choose the subscript i And will nums[i] change by any Positive integer .
Returns the that makes the array an alternating array The minimum number of operands .

Example

• Example 1：

 Input ：nums = [3,1,3,2,4,3]
 Output ：3
 explain ：
 One way to turn an array into an alternating array is to convert the array to  [3,1,3,1,3,1] .
 under these circumstances , The operands are  3 .
 Can prove that , Operands are less than  3  Under the circumstances , Cannot make an array into an alternating array .

• Example 2：

 Input ：nums = [1,2,2,2,2]
 Output ：2
 explain ：
 One way to turn an array into an alternating array is to convert the array to  [1,2,1,2,1].
 under these circumstances , The operands are  2 .
 Be careful , Array 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

Ideas

• Ideas

Because our main purpose here is to count the numbers of odd and even subscripts , Then select the number with the largest 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 , Then you can't sort by the number of occurrences . After the sorting , Then if the number of occurrences is not equal , We use these two numbers directly ; Otherwise, we need to choose 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]);
    }
}

Running results

<3> Third question

subject

Take out the smallest number of magic beans

To give you one just An array of integers beans , Each integer represents the number of magic beans in a bag .
Please... From each bag take out Some beans （ It's fine too Don't take out ）, Make the rest Non empty In the bag （ namely At least also One Magic bean bag ） Number of magic beans equal . Once the magic beans are removed from the bag , You can't put it in any other bag .
Please return to where you need to take out the magic beans Minimum number .

Example

• Example 1：

 Input ：beans = [4,1,6,5]
 Output ：4
 explain ：
-  We never had  1  Take it out of a magic bean bag  1  A magic bean .
   The number of magic beans left in the bag is ：[4,0,6,5]
-  Then we have  6  Take it out of a magic bean bag  2  A magic bean .
   The number of magic beans left in the bag is ：[4,0,4,5]
-  Then we have  5  Take it out of a magic bean bag  1  A magic bean .
   The number of magic beans left in the bag is ：[4,0,4,4]
 A total of  1 + 2 + 1 = 4  A magic bean , The number of magic beans left in the non empty bag is equal .
 Nothing is better than taking out  4  A plan with fewer magic beans .

• Example 2：

 Input ：beans = [2,10,3,2]
 Output ：7
 explain ：
-  We never had  2  Take it out of one of the bags of magic beans  2  A magic bean .
   The number of magic beans left in the bag is ：[0,10,3,2]
-  Then we have... From another  2  Take it out of a magic bean bag  2  A magic bean .
   The number of magic beans left in the bag is ：[0,10,3,0]
-  Then we have  3  Take it out of a magic bean bag  3  A magic bean .
   The number of magic beans left in the bag is ：[0,10,0,0]
 A total of  2 + 2 + 3 = 7  A magic bean , The number of magic beans left in the non empty bag is equal .
 Nothing is better than taking out  7  A plan with fewer magic beans .

Tips

• 1 <= beans.length <= 105
• 1 <= beans[i] <= 105

Ideas

• Ideas

And what we have here is enumeration beans All possible values in the array , Then it will be less than beans[i] The number of is set to 0, Will be bigger than the beans[i] The number of drops to beans[i]. Here we are preprocessing out a Prefixes and arrays To assist , Then it is to find the minimum .

Code implementation

class Solution {
    
    public long minimumRemoval(int[] beans) {
    
        /**  This problem is similar to  acwing  A problem of resetting the sequence of numbers in the weekly competition in . Its problem is the number of operations required to change all numbers into the same number , But here he is, we can manipulate numbers in an interval , Its practice there is to enumerate the numbers of 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;
    }
}

Running results