Leetcode 302 weekly games

The first question is ：6120. How many pairs can an array form

I'll give you a subscript from 0 The starting array of integers nums . In one step , You can do the following ：

    from nums elect Two equal Integers
    from nums Remove these two integers , To form a Number pair

Please come in nums Perform this operation several times on until it cannot be continued .

Returns a subscript from 0 Start 、 The length is 2 Array of integers for answer As the answer , among answer[0] Is the number of pairs formed ,answer[1] It's right nums Try to count the number of integers left after the above operation

Example 1：

Input ：nums = [1,3,2,1,3,2,2]
Output ：[3,1]
explain ：
nums[0] and nums[3] Form a number pair , And from nums Remove ,nums = [3,2,3,2,2] .
nums[0] and nums[2] Form a number pair , And from nums Remove ,nums = [2,2,2] .
nums[0] and nums[1] Form a number pair , And from nums Remove ,nums = [2] .
Cannot form more pairs . A total of 3 Pairs of numbers ,nums The rest of the world is 1 A digital .

  Their thinking ：

Simply put, pair the numbers in the array , See how many pairs you can count at the same time, and how many single dogs are left .

Open a hash table to calculate the number of occurrences of each number , The matching number is divided by 2 Round down , Finally, the number of single dogs is the array length minus logarithmic multiplication 2.

Code ：

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        unordered_map<int, int> hash;
        for(auto x:nums) hash[x] ++ ;
        vector<int> res(2);
        for(auto [k,v]: hash)
            res[0] += v / 2;// Round the pairing number 
        res[1] = nums.size() - res[0] * 2;
        return res;
    }
};

The second question is ：6164. The maximum sum of digits and equal pairs

I'll give you a subscript from 0 Starting array nums , The elements in the array are just Integers . Please choose two subscripts i and j（i != j）, And nums[i] The digits and And   nums[j] The digit sum of is equal .

Please find all the subscripts that meet the conditions i and j , Find out and return to nums[i] + nums[j] What you can get Maximum .

Example 1：

Input ：nums = [18,43,36,13,7]
Output ：54
explain ： Number pairs that meet the conditions (i, j) by ：
- (0, 2) , The digit sum of the two numbers is 9 , Add up to get 18 + 36 = 54 .
- (1, 4) , The digit sum of the two numbers is 7 , Add up to get 43 + 7 = 50 .
So the maximum sum that can be obtained is 54 .

  Their thinking ：

Let's start with violence , Enumerate two pairs , Judge whether the digits and are equal , Equal to maintain the maximum value of the answer . The time complexity of violence n^2,

Think back and forth , Fix a number first , Calculate the sum of its bits , Then, find the digit and the equal number in front , I hope the two numbers are the largest , In other words, find the largest number between the first digit and the equal digit , Adopt hash table optimization , use The hash table stores the maximum value of the corresponding digit sum , Finally, just check the hash table , In this way, the time complexity is reduced to nlogn

Code

class Solution {
public:
    int maximumSum(vector<int>& nums) {
      int res = -1;
      unordered_map<int, int> hash;// The maximum value corresponding to the sum of each digit 
      for(auto x: nums) {
          int s = 0,y = x;//s Is the sum of the digits ,y For each number 
          while(y) s += y % 10,y /= 10;// Calculate digit sum 
          if(hash.count(s)) res = max(res, x + hash[s]);// lookup s Whether digit sum exists , Update the answer if it exists 
          hash[s] = max(hash[s], x);// Finally, let's see which of the digits and the equivalent digits is the largest 
      }
      return res;
    }
};

Third question ：6121. Query the number K Small numbers

I'll give you a subscript from 0 Starting string array nums , Each of these strings Equal length And contains only numbers .

Give you another subscript from 0 Start with a two-dimensional integer array queries , among queries[i] = [ki, trimi] . For each queries[i] , You need ：

    take nums Each number in tailoring To the rest Far right trimi One digit .
    In the cropped numbers , find nums pass the civil examinations ki Small numbers correspond to Subscript . If the two cut numbers are the same , So subscript smaller The number of is regarded as a smaller number .
    take nums Restore each number in to the original string .

Please return a length and queries Equal array answer, among answer[i] It's No i Results of this query .

Tips ：

    Cut to the rest x Digit means constantly deleting the leftmost digit , Until the rest x One digit .
    nums The string in may have a leading 0 .

Example 1：

Input ：nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
Output ：[2,2,1,0]
explain ：
1. Cut to just 1 After a few digits ,nums = ["2","3","1","4"] . The smallest number is 1 , Subscript to be 2 .
2. Cut to the left 3 After a few digits ,nums There is no change . The first 2 The small number is 251 , Subscript to be 2 .
3. Cut to the left 2 After a few digits ,nums = ["02","73","51","14"] . The first 4 The small number is 73 , Subscript to be 1 .
4. Cut to the left 2 After a few digits , The minimum number is 2 , Subscript to be 0 .
   Be careful , Number after clipping "02" The value is 2 .

Tips ：

    1 <= nums.length <= 100
    1 <= nums[i].length <= 100
    nums[i] Numbers only .
    all nums[i].length The length of identical .
    1 <= queries.length <= 100
    queries[i].length == 2
    1 <= ki <= nums.length
    1 <= trimi <= nums[0].length

Their thinking ：

It's actually quite difficult , But its data range is relatively small , So the idea here is still violence .

Save keywords with a stable sort , utilize pair A double keyword , The first keyword is string , The second keyword is subscript .

Look at the code first

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size();//n Represents the array length ,m Is the number of inquiries 
        vector<pair<string, int>> strs(n);
        for(int i = 0; i < n; i ++ ) strs[i] = {nums[i], i};// Enumerate various strings 
        vector<int> res;
        for(auto& q: queries){// Sort the strings in each query 
            int k = q[0], trim = q[1];
            sort(strs.begin(), strs.end(), [&](pair<string, int>& a,pair<string, int>& b) {// Pay attention to adding quotation ！！！！！！！
                for(int i = a.first.size() - trim; i < a.first.size(); i ++ )
                    if(a.first[i] < b.first[i])// Compare the dictionary order of two characters , The first string is smaller , return true
                        return true;
                    else if(a.first[i] > b.first[i])
                        return false;
                return a.second < b.second;// If the two are the same , Just compare their subscripts 
            });
            res.push_back(strs[k-1].second);// Last return subscript 
        }
        return res;
    }
};

Let's talk about the comparison function here ,return true It means to judge whether a Put it in b In front of

Fourth question ：6122. The minimum number of deletions that make the array divisible

Here are two arrays of positive integers nums and numsDivide . You can start your nums Delete any number of elements .

Please return to make nums in Minimum Elements can be divisible numsDivide Of all elements in least Number of deletions . If you can't get such an element , return -1 .

If y % x == 0 , Then we say integer x to be divisible by y

Example 1：

Input ：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output ：2
explain ：
[2,3,2,4,3] The smallest element in is 2 , It cannot be divisible numsDivide All elements in .
We from nums Delete in 2 Size is 2 The elements of , obtain nums = [3,4,3] .
[3,4,3] The smallest element in the is 3 , It can be divisible numsDivide All elements in .
Can prove that 2 Is the minimum number of deletes .

Tips ：

    1 <= nums.length, numsDivide.length <= 105
    1 <= nums[i], numsDivide[i] <= 109

  Their thinking ：

What is said in the title can Divide all the elements in the array It means that all elements can be divided greatest common divisor , So first find the greatest common divisor , Then enumerate later .

Code implementation ：

class Solution {
public:
    int gcd(int a, int b){// Find the greatest common divisor 
        return b ? gcd(b, a % b) : a;
    }
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        int d = 0;
        for(auto x: numsDivide) d = gcd(d, x);

        int res = 0;
        sort(nums.begin(), nums.end());
        for(int i = 0;i < nums.size(); i ++ ){
            if(d % nums[i] == 0) break;// After sorting, enumerate from front to back to see if it can be divided by the maximum common divisor , If not, delete 
            res ++ ;
        }

        if(res == nums.size()) res = -1;
        return res;
    }
};

ha-ha lc302 end