leetcode280周赛

竞赛链接

T1: 6004. 得到 0 的操作数

---

思路

模拟

Code

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

复杂度分析

时间复杂度：O(logmax(N,M))
空间复杂度：O(1)

T2: 6005. 使数组变成交替数组的最少操作数

---

思路

理解题意：我们要让奇数位置都相同，偶数位置都相同，且这两个数字不能相同。

要想操作最少，我们应该尽可能利用已有的数字，因此我们对奇数和偶数位置分别计数。但这里直接采用最大频率的数字是不对的，因为二者的最大频率数字可能相同。因此我们枚举前二大频率进行搭配。

Code

struct Node
{
    int first, second;
};

bool operator<(Node aa,Node bb)  //第一个从大到小排,第二个从小到大 
{
    return aa.first==bb.first?bb.second<aa.second:aa.first<bb.first;
}

class Solution {
public:
    vector<int>a,b;
    unordered_map<int,int>ma,mb;
    priority_queue<Node>pq,pp;
    int minimumOperations(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;++i){
            if(i%2==0)
                a.emplace_back(nums[i]),ma[nums[i]]++;
            else
                b.emplace_back(nums[i]),mb[nums[i]]++;
        }
        int a1=0,a2=0,sa1=0,sa2=0;
        for(auto& i:ma){
            pq.push({i.second,i.first});
        }
        if(!pq.empty()){
            a1=pq.top().first,sa1=pq.top().second;
            pq.pop();
        }
        if(!pq.empty()){
            a2=pq.top().first,sa2=pq.top().second;
            pq.pop();
        }

        int b1=0,b2=0,sb1=0,sb2=0;
        for(auto& i:mb){
            pp.push({i.second,i.first});
        }
        if(!pp.empty()){
            b1=pp.top().first,sb1=pp.top().second;
            pp.pop();
        }
        if(!pp.empty()){
            b2=pp.top().first,sb2=pp.top().second;
            pp.pop();
        }

        int ans=INT_MAX;
        /*
        cout<<a1<<" "<<sa1<<endl;
        cout<<a2<<" "<<sa2<<endl;
        cout<<b1<<" "<<sb1<<endl;
        cout<<b2<<" "<<sb2<<endl;*/
        if(sa1==sb1){
            if(sb2!=0){
                int cnt=a.size()-a1+b.size()-b2;
                ans=min(ans,cnt);
            }
            if(sa2!=0){
                int cnt=a.size()-a2+b.size()-b1;
                ans=min(ans,cnt);
            }
            if(sa2==0&&sb2==0){
                ans=min(a1,ans);
                ans=min(b1,ans);
            }
        }
        if(sa1!=sb1){
            int cnt=a.size()-a1+b.size()-b1;
            ans=min(ans,cnt);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

T3: 6006. 拿出最少数目的魔法豆

---

思路

排序+前缀和预处理+枚举
按照数目从小到大排序后，对于每个位置，我们可以选择将这个位置左边的袋子清空，并将右边的袋子中魔法豆的数目都减少到与当前位置相同。从这些位置中找出代价最小的一个即可。

Code

typedef long long ll;
const int N=100005;
class Solution {
public:
    ll pre[N],hou[N];
    long long minimumRemoval(vector<int>& beans) {
        sort(beans.begin(),beans.end());
        int n=beans.size();
        ll ans=9223372036854775807;
        for(int i=0;i<n;++i){
            pre[i+1]=pre[i]+beans[i];
        }
        for(int i=n-1;i>=0;--i){
            hou[i]=hou[i+1]+beans[i];
        }
        for(int i=0;i<n;++i){
            ll sum=pre[i]+hou[i+1]-(ll)(n-i-1)*beans[i];
            ans=min(sum,ans);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

T4: 6007. 数组的最大与和

---

思路

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);
            if (c >= nums.size()) continue;
            for (int j = 0; j < numSlots * 2; ++j) {
                if ((i & (1 << j)) == 0) { // 枚举空篮子 j
                    int s = i | (1 << j);
                    //因为这里相当于往篮子新加了一个数，所以当前值等于上一个只有i-1数加上现在的值增益取max
                    f[s] = max(f[s], f[i] + ((j / 2 + 1) & nums[c]));  
                    ans = max(ans, f[s]);   //因为篮子没有必要放满,所以在每次新加完一个数后，都要更新最大值
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(N^2⋅S⋅2^N)
• 空间复杂度：O(2^N)

相似题目

1879. 两个数组最小的异或值之和

个人总结

---

本次周赛，t2有点费事，自己想了个差不多的解法，然后在debug两发后才过掉；t3刚开始想二分，但又因为没办法确定单调性，于是转用排序+前缀和+枚举才ac，t4因为不会状压，于是只能罚坐。。