第280场周赛解答

第280场周赛

链接↓

第280场周赛

6004.得到 0 的操作数

给你两个 非负 整数 num1 和 num2 。

每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。

• 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。

返回使 num1 = 0 或 num2 = 0 的 操作数 。

示例 1：

输入：num1 = 2, num2 = 3
输出：3
解释：
- 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。
- 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。
- 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。
此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 3 。

示例 2：

输入：num1 = 10, num2 = 10
输出：1
解释：
- 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 1 。

提示：

• 0 <= num1, num2 <= 105

分析：

直接按照题目意思来就行了，注意特判开始就为0的情况

class Solution {
public:
    int countOperations(int num1, int num2) {
    int ans=0;
    if(num1==0||num2==0){
        return 0;
    }
    while(num1!=0||num2!=0){
    if(num1>num2){
        num1=num1-num2;
        ans++;
    }
    else if(num2>num1){
        num2=num2-num1;
        ans++;   
    }
    if(num1==num2){
        ans++;
        break;
    }
    }
        return ans;
    
    }
};

---

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

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。

如果满足下述条件，则数组 nums 是一个 交替数组 ：

• nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
• nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。

在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。

返回使数组变成交替数组的 最少操作数 。

示例 1：

输入：nums = [3,1,3,2,4,3]
输出：3
解释：
使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。
在这种情况下，操作数为 3 。
可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。

示例 2：

输入：nums = [1,2,2,2,2]
输出：2
解释：
使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1].
在这种情况下，操作数为 2 。
注意，数组不能转换成 [2,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

分析：

由题知：

若距离为1且value相等时，必须要修改；

若距离为2且value不同时，必须要修改；

且需要求修改的最少操作数

那么我们可以使用哈希表去对数组的值进行统计，得出什么数字出现的频次最高及次高。

最后我们通过总的去减去两次统计过的，即为需要修改的

特别地，在最高频的值相等时，我们需要从中取出一个最小值。

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
    int n=nums.size();
    unordered_map<int,int> mp1,mp2;
    for(int i=0;i<n;i++){
        if(i&1){
            mp1[nums[i]]++;
        }
        else{
            mp2[nums[i]]++;
        }
    }
    int ka=-1,kb=-1,va=0,vb=0;
        for(auto[k,v]:mp1){
            if(v>va){
                va=v;
                ka=k;
            }
        }
        for(auto[k,v]:mp1){
            if(k==ka) continue;
            if(v>vb){
                vb=v;
                kb=k;
            }
        }
    
    int k1=-1,k2=-1,v1=0,v2=0;
        for(auto[k,v]:mp2){
            if(v>v1){
                v1=v;
                k1=k;
            }
        }
        for(auto[k,v]:mp2){
            if(k==k1) continue;
            if(v>v2){
                v2=v;
                k2=k;
            }
        }
        if(ka!=k1) return n-va-v1;
        else{
            return min(n-va-v2,n-v1-vb);
        }
    }
};

---

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

给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。

请你返回你需要拿出魔法豆的 最少数目。

示例 1：

输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2：

输入：beans = [2,10,3,2]
输出：7
解释：
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示：

• 1 <= beans.length <= 105
• 1 <= beans[i] <= 105

分析：

对于本题只需要比cur小的，全部拿走，比cur大的，减去多余部分

对数组进行一次排序

其中拿出来的数量，等于当前下标左右之和

通过计算前后缀之和

最后扫一次数组即可获得最小值

特别注意：因本题的数据范围，故在最后取cnt的时候会卡一次类型，如下:

Line 9: Char 67: runtime error: signed integer overflow: 40570 * 52936 cannot be represented in type ‘int’ (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:18:67

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        int n=beans.size();
        sort(beans.begin(),beans.end());
        vector<long long> pre(n+1),post(n+1);
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]+beans[i-1];
        }
        for(int i=n-1;i>=0;i--){
            post[i]=post[i+1]+beans[i];
        }
        long long cnt=1e12;
        for(int i=1;i<=n;i++){
            cnt=min(cnt,pre[i-1]+post[i]-(n-i)*(long long)beans[i-1]);
        }
        return cnt;
    }
};

---

6007.数组的最大与和

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。

你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。

• 比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2中，这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。

请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。
最大与和为 (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 。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

提示：

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

---

分析：

见代码及其注释

int dp[10][1<<19];
class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n=nums.size();
        memset(dp,-1,sizeof(dp));
        dp[0][0]=0;
        int lim=1<<n;
        for(int i=1;i<=numSlots;i++){
            for(int s=0;s<lim;s++){
                if(dp[i-1][s]==-1) continue;
                //不放数字
                dp[i][s]=max(dp[i][s],dp[i-1][s]);
                //放一个数字
                for(int k=0;k<n;k++){
                    if((s>>k)&1) continue;
                    dp[i][s|(1<<k)]=max(dp[i][s|(1<<k)],dp[i-1][s]+(nums[k]&i));
                }
            }
            //第i个篮子放一个数字，等同于01背包问题
            for(int s=lim-1;s>=0;s--){
                if(dp[i][s]==-1) continue;
                for(int k=0;k<n;k++){
                    if((s>>k)&1) continue;
                    dp[i][s|(1<<k)]=max(dp[i][s|(1<<k)],dp[i][s]+(nums[k]&i));
                }
            }
        }
        return dp[numSlots][lim-1];
    }
};