📒博客首页：崇尚学技术的科班人
🍣今天给大家带来的文章是《LeetCode第280场周赛》🍣
🍣希望各位小伙伴们能够耐心的读完这篇文章🍣
🙏博主也在学习阶段，如若发现问题，请告知，非常感谢🙏
💗同时也非常感谢各位小伙伴们的支持💗

<1> 第一题

题目

得到 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 <= 10^5

⭐思路⭐

• 思路

这道题是签到题，我的做法就是模拟这个过程，当num1 > num2时，就进行num1 = num1 - num2且计数；当num1 < num2时，我们就进行num2 = num2 - num1且计数；如果两个数相等就计数并退出循环。

代码实现

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

运行结果

<2> 第二题

题目

使数组变成交替数组的最少操作数
给你一个下标从 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

⭐思路⭐

• 思路

因为这里我们的主要目的就是我们对奇偶下标的数进行计数，然后对奇偶下标的数中最多的数选用作为我们要修改为的数。所以我们需要对其出现次数的各个数按照出现次数从大到小的排序。如果使用一个哈希表的话，那么就不能按照出现次数进行排序。排序之后，然后如果出现次数最多的数不相等的话，我们直接使用这两个数；否则我们需要选用出现次数次大的数进行求最小值进行返回。

代码实现

class Solution {
    public int minimumOperations(int[] nums) {
        int[][] cnt1 = new int[100010][2];
        int[][] cnt2 = new int[100010][2];

        for(int i = 0; i < cnt1.length; i ++){
            cnt1[i][0] = i;
            cnt2[i][0] = i;
        }

        for(int i = 0; i < nums.length; i ++){
            if(i % 2 == 0){
                cnt1[nums[i]][1] ++;
            }else if(i % 2 == 1){
                cnt2[nums[i]][1] ++;
            }
        }

        Arrays.sort(cnt1,(a1,b1) -> b1[1] - a1[1]);
        Arrays.sort(cnt2,(a1,b1) -> b1[1] - a1[1]);

        if(cnt1[0][0] != cnt2[0][0]) return nums.length - (cnt1[0][1] + cnt2[0][1]);
        return nums.length - Math.max(cnt1[0][1] + cnt2[1][1], cnt1[1][1] + cnt2[0][1]);
    }
}

运行结果

<3> 第三题

题目

拿出最少数目的魔法豆
给你一个 正 整数数组 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

⭐思路⭐

• 思路

而我们这里的就是 枚举 beans 数组中的所有可能的值，然后将小于 beans[i] 的数进行设置为 0,将大于 beans[i]的数下降到 beans[i]。这里我们就是预处理出来一个前缀和数组进行辅助，然后就是求最小值。

代码实现

class Solution {
    public long minimumRemoval(int[] beans) {
        /**
            这道题类似于 acwing 中的周赛中的重置数列的一道题。它的那道题就是将所有的数变为相同的数需要的操作次数，但是他这里就是我们可以操作一个区间内的数，它那里的做法就是对所有范围的数进行枚举    
         */
        long ans = Long.MAX_VALUE;
        int len = beans.length;
        long[] s = new long[len + 1];
        Arrays.sort(beans);
        for(int i = 1; i <= len; i ++) s[i] = s[i - 1] + beans[i - 1];
        for(int i = 0; i < len; i ++){
            ans = Math.min(ans,s[i + 1] + (s[len] - s[i + 1]) - (long)beans[i] * (len - i));
        }
        return ans;
    }
}

运行结果