[daily problem insight] Li Kou - the 280th weekly match (I really didn't know it could be so simple to solve other people's problems)

️ Winter vacation xinkeng —— Code Fox's daily notes
The winter vacation is about to expire

6007. The maximum sum of the array -Hard- The first 280 Weekly competition questions 4

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 .

// The solution comes from ——https://leetcode-cn.com/u/endlesscheng/
class Solution {
    
    public int maximumANDSum(int[] nums, int numSlots) {
    
        var ans = 0;
        var f = new int[1 << (numSlots * 2)];
        for (var i = 0; i < f.length; i++) {
    
            var c = Integer.bitCount(i);
            if (c >= nums.length) continue;
            for (var j = 0; j < numSlots * 2; ++j) {
    
                if ((i & (1 << j)) == 0) {
     //  Enumerate empty baskets  j
                    var s = i | (1 << j);
                    f[s] = Math.max(f[s], f[i] + ((j / 2 + 1) & nums[c]));
                    ans = Math.max(ans, f[s]);
                }
            }
        }
        return ans;
    }
}

6006. Take out the smallest number of magic beans -Mid- The first 280 Weekly competition questions 3

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 .

class Solution {
    
    public long minimumRemoval(int[] beans) {
    
        Arrays.sort(beans);
        long sum=0;
        for(int i:beans){
    
            sum+=i;
        }
        int n=beans.length;
        if(n==1){
    
            return 0;
        }
        long dp=0;
        long sumF=0;
        
        long min=Long.MAX_VALUE;
        
        for(int i=n-1;i>=0;i--){
    
            if(i!=n-1){
    
                dp=(sum+sumF-(long)beans[i+1]*(long)(n-1-i));
            }
            else{
    
                dp=sum;
            }
            sum-=beans[i];
            sumF+=beans[i];
            if(min>dp){
    
                min=dp;
            }
        }
        dp=sumF-(long)beans[0]*(long)(n);
        if(min>dp){
    
            min=dp;
        }
        return min;
    }
}

6005. The minimum number of operands to make an array an alternating array -Mid- The first 280 Weekly competition questions 3

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 .

class Solution {
    
    public int minimumOperations(int[] nums) {
    
        int n=nums.length;
        if(n==1){
    
            return 0;
        }
        int[][] same=new int[2][2];
        int[][] same2=new int[2][2];
        int count=0;
        int cur=0;
        same=get(nums,n,2);
        same2=get(nums,n,1);
        int m=0;
        if(same[0][1]!=same2[0][1]){
    
            m=same[0][0]+same2[0][0];
        }
        m=Math.max(same2[1][0]+same[0][0],m);
        m=Math.max(same2[0][0]+same[1][0],m);
        return n-m;
    }
    
    int[][] get(int[] nums,int n,int k){
    
        int count=0;
        int cur=0;
        Map<Integer,Integer> map=new HashMap<>();
        int[][] same=new int[2][2];
        for(int i=k%2;i<n;i+=2){
    
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        
        for(Map.Entry<Integer,Integer> e:map.entrySet()){
    
            if(e.getValue()>same[0][0]){
    
                same[1][0]=same[0][0];
                same[1][1]=same[0][1];
                same[0][0]=e.getValue();
                same[0][1]=e.getKey();
            }
            else if(e.getValue()>same[1][0]){
    
                same[1][0]=e.getValue();
                same[1][1]=e.getKey();
            }
        }
        return same;
    }
}

6004. obtain 0 The number of operations - The first 280 Weekly competition questions 1

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 .

class Solution {
    
    public int countOperations(int num1, int num2) {
    
        int a=0;
        while(num1!=0&&num2!=0){
    
            if(num1>=num2){
    
                a+=(num1/num2);
                num1%=num2;
            }
            else{
    
                a+=(num2/num1);
                num2%=num1;
            }
        }
        return a;
    }
}

ending

Title source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems

️ Focus on the author , Take you to brush the questions , Learn the most commonly used algorithm skills from simple algorithm problems （ Winter vacation every day ）
️ Pay attention to the author's questions —— Simple to advanced , Let you unknowingly become a ruthless problem brushing machine , If you have any questions, please send a private letter