Leetcode's 302 weekly rematch

For the first time, I did the competition question , Only two and a half , Let's sort out our ideas
2341. How many pairs can an array form

Main idea ：
First step ： Look at the constraints

1. The size of the whole array given in the title is 100, The range of numbers is also [1,100], This shows that you can enumerate the numbers that appear .

The second step ： Look at the content of the topic

1. The title requires the elimination of the same elements in pairs , The first thing I think of is to remove duplicate elements . But if the number of repeating elements is odd , Then you need to keep one . Therefore, the idea will transition to counting the number of times each number appears . After the statistics , If the number of occurrences is divided by 2 zero , You need to remove the number and add this number ; If it's not zero , Add one to the number of remaining elements .

The third step ： Write code

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        res1,res2=0,0
        ls=[0]*101
        for i in nums:
                ls[i]+=1
        for i in ls:
            res1=res1+(i//2)
            res2=res2+(i%2)
        return [res1,res2]        

2342. The maximum sum of digits and equal pairs

Main idea ：
First step ： Look at the constraints
The scope is large, and the overflow problem should be considered .int Maximum 2147483647 Probably $2\ast 10^9$
The second step ： Look at the content of the topic

1. The title requires the maximum sum of statistics and the same number . First of all, it is required to figure out the number of digits and the sum of each number , Then judge whether there are the same digits and , If there is, add it up and compare it with the largest . Finally, return the maximum sum .
2. Count the same elements , The best way is to use the idea of bucket sorting （ Like the first question ）, But because the number is too large , And sparse , Therefore, the method of using a dictionary will be better .
3. First , Define a dictionary , The key is in the character format of the sum of digits , The value is the real value . Then traverse nums, If the sum of digits of a number is not in the dictionary , Just add it to the dictionary . If it exists, add the real value to the value in the dictionary , Determine whether it is the maximum sum （ Here we need to set a current maximum sum for comparison ）, At the same time, keep the largest of the two same values in the dictionary , To ensure that the same value appears later , The sum of addition is the largest .

The third step ： Write code

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        dic={
    }
        res=-1
        for i in nums:
            tmp=sum([int(k) for k in list(str(i))])
            if str(tmp) in dic:
                res=max(res,dic[str(tmp)]+i)
                dic[str(tmp)]=max(dic[str(tmp)],i)  
            else:
                dic[str(tmp)]=i
        return res
        

2343. Query the number K Small numbers


Main idea ：
First step ： Look at the constraints
The maximum length of a string in the list is 100, It exceeds the record range of integer
Cutting position $tri{m}_i$ Within the length of characters
Location selection $k_i$ In the long element of the list
With these conditions, we will know where the boundary of the problem is
The second step ： Look at the content of the topic

1. The title requires the first k The original position of small numbers . This is the problem of designing to an original position .
2. Pay attention to the special situation of the analysis topic , If there are duplicate numbers , The default original location index is small , Less valuable . As shown in the following table , here 1 It's in position 2 Less than 4 It's in position 2. After sorting, the order changes to 【1,2,2,3,4】 If you return to the 3 The original position of small numbers , What should be returned is 4. So just use list.index() There is no way to find the true position of the repeating element . Therefore, you cannot use sorting functions to sort arrays directly , The location should be recorded , Only sort the positions .

Indexes	0	1	2	3	4
value	1	2	3	4	2

3. After understanding the prerequisites , This topic is similar to cardinality sorting . The number of bits cropped is the number of iterations of Radix sorting .
   Therefore, define a bucket size as $[0-9]$. In addition, so set an array loc Record the position of each sort ,$loc[i][j]$ , Indicates that the cutting length is i when , The first j The original position of small numbers

4. Initialize location first , Write the current position to $loc[0][:]$

5. Then take the last bit of all elements and put them into the corresponding bucket , Then press 0-9 Rearrange the array in the order of , Here, only the number sequence after sorting is recorded $loc[1][:]$. Take the above table for example , that loc The composition of is

loc[0]	0	1	2	3	4
Original value	1	2	3	4	2
loc[1]	0	1	4	2	3
Value after sorting	1	2	2	3	4

If the cut is [1,1] Then take $loc[1][1-1]$ That is to say 0

The third step ： Write code

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        m = len(nums[0])
        # vecs[i][j]  Indicates the cardinality order  i  In the middle of the round  j  The subscript corresponding to a small number 
        vecs=[[i for i in range(0,n)]]

        for  i in range(1,m+1):
            B={
    }
            for ele in range(10):
                B[str(ele)]=[]

             #  The first  i - 1  The result of the round , according to  nums  The middle right number  i  digit , Put them into the bucket one by one 
            for x in  vecs[i - 1]:
                B[nums[x][m - i]].append(x);
             #  Connect the results of each bucket , Be the first  i  The result of the round 
            tmp=[]
            for j in range(10):
                for  x in  B[str(j)]:
                    tmp.append(x)
            vecs.append(tmp)


        ans=[]
        for q in  queries:
            ans.append(vecs[q[1]][q[0] - 1])
        return ans

2344. The minimum number of deletions that make the array divisible


Main idea ：
First step ： Look at the constraints

1. Constraints in the topic , Both divisor and dividend are large , It may time out

The second step ： Look at the content of the topic

1. The title request can be returned numsDivide Array divisible nums The smallest element in , The most direct way of thinking is to choose nums The smallest element in , If it can be divisible , Then return the value . If it's not divisible , Then delete the element , Continue to repeat the above steps , The code is as follows

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        count=0
        while len(nums)>0:
            su=0
            k=min(nums)
            for i in numsDivide:
                su+=(i%k)
            if su==0:
                return count
            nums.remove(k)
            count+=1
        return -1     

But if the amount of data is very large , It will time out .
2. Change the way of thinking , If a number can be numsDivide to be divisible by , Then it can also be divided by their greatest common divisor . therefore , First seek numsDivide Maximum common divisor of , Traversal numsDivide The array is converted to divide only by the greatest common divisor .
3. Then go through the array , Find all the numbers that can be divided by the greatest common divisor , Find their minimum value and record it as mn. If mn by 0, So return -1. Otherwise, statistics nums Small and medium mn The number of , That is, the number of elements to be deleted .

The third step ： Write code

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        g=gcd(*numsDivide)
        mn=min([x for x in nums if g%x==0 ], default=0)
        if mn==0:
 			return -1
        return sum([ x< mn for x in nums]) 

Under the supplement python in " * " Usage of （ Reference to the original ）
1. Single star * Used to fetch the list list Or tuples tuple The elements in .
Single star * Only the keys in the dictionary can be read （key）.

a = [1,2]
print(*a)
#  Output  1 2

2. Used to collect redundant values in the list , What we collect is a list .

a,b,*l=[2,3,4,5]
print(a) # 2
print(b) # 3
print(l) # l Is a list of  [4,5] 

3. In the function ,* Represents collection parameters , Put the collected parameters in a tuple tuple Inside .

def printFunc(x,*para):
    print(x)
    print(para)
printFunc(1,2,3)
#  Output 
# 1
# (2, 3)
printFunc(x = 1,2,3,4) # Report errors