Leetcode skimming - game 280

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/count-operations-to-obtain-zero
analysis
The simulation will time out if it is carried out directly according to the topic , So we need to simplify it . We assume that num1 Than num2 Much larger , Then you have to subtract many times , Until the reduced number ratio num2 Xiaozhi , The last number is the original num1 % num2, The number of times they directly subtract is num1 / num2, We can simulate according to this feature .
Code

class Solution {
    
public:
    int countOperations(int num1, int num2) {
    
        int cnt=0;
        if(num1 == 0 || num2 == 0){
    
            return 0;
        }
        if(num1 < num2){
    
            int tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        while(num1 % num2){
    
            cnt += num1 / num2;
            int tmp = num1 % num2;
            num1 = num2;
            num2 = tmp;
        }
        cnt += num1 / num2;
        return cnt;
    }
};

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-operations-to-make-the-array-alternating
analysis
According to the topic, we can change our thinking to find the most positions that do not need to be replaced , In this way, the position that needs to be modified is minimized , We count the number of odd and even digits respectively , Then calculate according to the situation that it is not replaced at most .
Code

class Solution {
    
public:
    int minimumOperations(vector<int>& nums) {
    
        vector<int> a, b;
        map<int, int> ma, mb;
        if(nums.size()==1){
    
            return 0;
        }
        for(int i=0; i < nums.size(); i++){
    
            if(i % 2 == 0){
    
                if(ma[nums[i]]==0){
    
                    a.push_back(nums[i]);
                }
                ma[nums[i]]++;
            }else{
    
                if(mb[nums[i]]==0){
    
                    b.push_back(nums[i]);
                }
                mb[nums[i]]++;
            }
        }
        int mxa=0, mxb=0;
        int aa, bb, ans=0;
        for(int i=0; i < a.size(); i++){
    
            if(mxa < ma[a[i]]){
    
                mxa = ma[a[i]];
                aa=a[i];
            }
        }
        for(int i=0; i < b.size(); i++){
    
            if(b[i] != aa && mxb < mb[b[i]]){
    
                 mxb = mb[b[i]];
            }
        }
        ans = mxa + mxb;
        mxa =0, mxb = 0;
        for(int i=0; i < b.size(); i++){
    
            if(mxb < mb[b[i]]){
    
                 mxb = mb[b[i]];
                bb = b[i];
            }
        }
        for(int i=0; i < a.size(); i++){
    
            if(a[i] != bb && mxa < ma[a[i]]){
    
                mxa = ma[a[i]];
                aa=a[i];
            }
        }
        ans = max(ans, mxa + mxb);
        return nums.size()-ans;
    }
};

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/removing-minimum-number-of-magic-beans
analysis
First pair beans Sort , Then find the prefix sum , Suppose we finally get a length of beans[i] Then the number of beans taken out is the first i-1 Add the sum of beans in position i+1 Later ratio beans[i] More beans .
Code

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans = sorted(beans)
        summ = sum(beans) 
        ans = summ
        length = len(beans)
        for i in range(length):
            ans = min(ans, summ - (length-i) * beans[i])

        return ans

6007. The maximum sum of the array

Give you a length of n Array of integers for nums And an integer numSlots , Satisfy 2 * numSlots >= n . All in all numSlots Baskets , The number is 1 To numSlots .

You need to put all n Divide the whole number into these baskets , And each basket at most Yes 2 It's an integer . Of a distribution scheme With and Defined as the number of each number and its basket Bitwise and operation The sum of the results .

For example , The digital [1, 3] Put it in the basket 1 in ,[4, 6] Put it in the basket 2 in , The sum of this scheme is (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 .
Please return and will nums Put all numbers in numSlots The largest of the baskets and .

Example 1：

Input ：nums = [1,2,3,4,5,6], numSlots = 3
Output ：9
explain ： One possible solution is [1, 4] Put it in the basket 1 in ,[2, 6] Put it in the basket 2 in ,[3, 5] Put it in the basket 3 in . The maximum sum of and is (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9.

Example 2：

Input ：nums = [1,3,10,4,7,1], numSlots = 9
Output ：24
explain ： One possible solution is [1, 1] Put it in the basket 1 in ,[3] Put it in the basket 3 in ,[4] Put it in the basket 4 in ,[7] Put it in the basket 7 in ,[10] Put it in the basket 9 in . The maximum sum of and is (1 AND1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 +1 + 3 + 4 + 7 + 8 = 24 . Be careful , Basket 2 ,5 ,6 and 8 It's empty. , This is allowed .

Tips ：

n == nums.length
1 <= numSlots <= 9
1 <= n <= 2 * numSlots
1 <=nums[i] <= 15

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximum-and-sum-of-array
analysis
We can see numSlots The value is very small. , So we can use binary to represent basket , But this basket is quite special , He can hold two numbers , So we use two bits to represent a basket . Then dynamic planning
Code

class Solution {
    
public:
    int maximumANDSum(vector<int> &nums, int numSlots) {
    
        int ans = 0;
        vector<int> f(1 << (numSlots * 2));
        for (int i = 0; i < f.size(); ++i) {
    
            int c = __builtin_popcount(i); //i In binary 1 The position of is the position where the number is placed ,c For binary 1 The number of 
            if (c >= nums.size()) continue;
            for (int j = 0; j < numSlots * 2; ++j) {
    
                if ((i & (1 << j)) == 0) {
     //  Enumerate empty baskets  j
                    int s = i | (1 << j); // s It means that j The situation of putting numbers on the position 
                    f[s] = max(f[s], f[i] + ((j / 2 + 1) & nums[c]));
                    ans = max(ans, f[s]);
                }
            }
        }
        return ans;
    }
};