Leetcode weekly The 280 game of the week is still difficult for the special game of the week's beauty team ~ simple simulation + hash parity count + sorting simulation traversal

Content of this article ：leetcode Once a week . Zhou saidI 280 Weekly match Meituan special It's still difficult ~ Simple simulation + Hash parity count + Sort simulation traversal

Article column ：leetcode Clock in the week 《 Clock in every week 》

Recent updates ：2022 year 1 month 30 Japan leetcode Once a week . Zhou saidI 278 Weekly match Netease special session Sure enough, the question is very difficult But you can still brush Simple order + Traverse Double pointer + The prefix and

Personal profile ： A Junior Program ape in two colleges , In the spirit of paying attention to the foundation , Clock in algorithm , Sharing technology as a personal experience summary blogger , Although you may be lazy sometimes , But I will stick to it , If you like blog posts very much , Suggest looking at the following line ~（ Crazy hints QwQ）

give the thumbs-up Collection Leaving a message. One key, three links _{Care program ape , From you and me}

Write it at the front

Here comes Xiaofu , Today, we will update the weekly competition column , Today, Xiao Fu played weekly for the fifth time

The first 280 Weekly match ——2022-02-13

T1.6004. obtain 0 The number of operations

subject

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

A simple simulation question ：

• It can be simulated directly
• It should be noted that ： Only in num1 and num2 Is greater than 0 Under the circumstances Can be simulated

Code implementation

class Solution {
    
    public int countOperations(int num1, int num2) {
    
        int count = 0 ;
        while (num1 > 0 && num2 > 0){
    
            if (num1 >= num2)
                num1 = num1 - num2;
            else num2 = num2 - num1;
            count ++ ;
        }
        return count;
    }
}

Execution results

T2.6005. The minimum number of operands to make an array an alternating array

subject

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：

Example 2：

 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 3：

 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 <= 10^5
1 <= nums[i] <= 10^5

Ideas

Ideas and investigation points of this topic ：

• The idea of this question is actually very simple, mainly based on HashMap Record strange / The number of digits in even digits , Find out The number of numbers of the maximum quantity and the second largest quantity
• If The current odd digit is inconsistent with the maximum number of digits on the even digit Then directly use Total length of digits Subtract the sum of the two It can be concluded that Number of digits to be modified
• On the contrary, if two numbers with the largest number are the same You need to get the minimum operand If only Compare when the sum of the largest number and the next largest number is the largest, the number of times can be minimized So we need to calculate The maximum number of odd digits And Even bits a large number of digits The sum of the And The maximum number of even digits And Odd bits, large bits The sum of the Take the maximum value , Then we subtract the maximum value from the current length , Then the minimum operand is obtained .

Code implementation

class Solution {
    
    public int minimumOperations(int[] nums) {
    
        int n = nums.length;
        HashMap<Integer,Integer> even = new HashMap<>();
        HashMap<Integer,Integer> odd = new HashMap<>();
        for(int i=0;i<n;i++) {
    
            if(i%2==0) {
    
                // Record the number of each digit on the even digit 
                even.put(nums[i],even.getOrDefault(nums[i],0)+1);
            } else {
    
                // Record the number of each digit on the odd digit 
                odd.put(nums[i],odd.getOrDefault(nums[i],0)+1);
            }
        }
        // Find two map The two numbers with the most and the second most in key and val
        int[][] evenMaxAndSubMax = check(even);
        int[][] oddMaxAndSubMax = check(odd);
        // If the current two largest numbers key inequality   That is to say  1 != 2  In the case of   Current length   Subtract their frequency respectively   Is the number of positive integers that need to be changed 
        if(evenMaxAndSubMax[0][0] != oddMaxAndSubMax[0][0]) {
    
            n-= evenMaxAndSubMax[0][1];
            n-= oddMaxAndSubMax[0][1];
        } else {
     //  On the contrary, if two numbers with the largest number are the same   You need to get the minimum operand   If we compare the sum of the largest number and the next largest number, we can minimize the number 
            n-= Math.max(evenMaxAndSubMax[0][1]+oddMaxAndSubMax[1][1],oddMaxAndSubMax[0][1]+evenMaxAndSubMax[1][1]);   
        }
        return n;
    }
    
    int[][] check(HashMap<Integer,Integer> map) {
    
        int[][] maxAndSubMax = new int[2][2];
        // For each number 
        for(Integer key:map.keySet()) {
    
            // Get the current number key Of val
            int val = map.get(key);
            // Find the first two numbers of the number and store them in an array   Save their  key  And  val || res[0][0]  Is the largest number of numbers key res[0][0]  Is the largest number of numbers val
            if(val>maxAndSubMax[0][1]) {
    
                maxAndSubMax[1][0] = maxAndSubMax[0][0];
                maxAndSubMax[1][1] = maxAndSubMax[0][1];
                maxAndSubMax[0][0] = key;
                maxAndSubMax[0][1] = val;
            } else if(val>maxAndSubMax[1][1]){
    // There are many times key  And  val
                maxAndSubMax[1][0] = key;
                maxAndSubMax[1][1] = val;
            }
        }
        return maxAndSubMax;
    }
}

Execution results

T3.6006. Take out the smallest number of magic beans

subject

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 .

Tips

1 <= beans.length <= 10^5
1 <= beans[i] <= 10^5

Ideas

The idea of this problem is relatively simple ：

• But you will find that this problem is simple but The order of magnitude it gives is too large , The return value is a long Then there must be the possibility of timeout .
• Let's talk about ideas first :
• utilize ( Sort + The prefix and ) To solve
• We can put each bag first If all bags are empty, record if all bags are set to zero So here The value obtained is the maximum value of beans , We asked for The minimum value must be below it .
• Set the scroll variable Traverse through enumeration get Every time bring The number of magic beans in each bag is beans[i] Number of hours The number of beans you need to take out

Code implementation

class Solution {
    
    public long minimumRemoval(int[] beans) {
    
        Arrays.sort(beans);
        int n = beans.length;
        long res = Long.MAX_VALUE;
        long sum = 0 ;
        // It can be understood as the maximum value of magic beans   Take out all   All zeros 
        for (int bean : beans){
    
            sum += bean;
        }

        // Enumeration traversal   get   Every time   bring   The number of magic beans in each bag is  beans[i]  Number of hours   The number of beans you need to take out  
        for (int i = 0 ;i< n;i++){
    
            // Rolling variable records the minimum value   It's this beans [i] * (n-i);
            res = Math.min(res,sum-(long)beans[i] * (n-i));
        }
        return res;
    }   
}

Execution results

At the end

Xiaofu clocked in the fifth weekly race 2022-02-13

Try to solve the problems you can do All done That's all right.

I overslept today It's only half an hour when I get up =-=

This week's competition By the way, two questions

The third question has been overtime Directly break the defense

So it's still a good weekly experience

Last

Make progress every day Harvest some every day

May you A successful career Learn something

If it feels good Don't forget to click three times ~