[数据结构与算法]leetcode每周.周赛第280场周赛 美团专场 还是有难度的 ~简单模拟 + 哈希奇偶计数 + 排序模拟遍历

📖本篇内容：leetcode每周.周赛第280场周赛 美团专场 还是有难度的 ~简单模拟 + 哈希奇偶计数 + 排序模拟遍历

📑 文章专栏：leetcode周赛打卡《周周打卡》

📆 最近更新：2022年1月 30日 leetcode每周.周赛第278场周赛 网易专场 果然题很难 但还是能刷 简单排序+遍历 双指针+前缀和

🙊个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）

🌇 点赞 👍 收藏 ?留言 📝 一键三连 _{关爱程序猿，从你我做起}

🙊写在前面

🙊小付来喽，今天接着有更新周赛栏目了哦，今天小付第五次打周赛

📆第280场周赛——2022-02-13

📝T1.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 <= 10^5

?思路 ?

一道简单的模拟题：

• 直接模拟即可
• 需要注意的是：只有在num1和num2都大于0的情况下才可以进行模拟

代码实现

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

执行结果

📝T2.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：

示例2：

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

示例3：

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

?思路 ?

本题思路以及考察点：

• 这道题的思路其实很简单主要是根据HashMap记录奇/偶数位上的数字个数，找出其中最大数量和次大数量的数字个数
• 如果当前奇数位与偶数位上的最大数量的数字不一致那么就直接 用 数位总长度 减去二者之和 就可以得出 需要修改的数字位个数
• 反之如果出现了两个数量最多的数字相同时 需要获得最小操作数 就要是比较当最大数和次大数的加和最大才能使得次数最小 所以需要计算出奇数位最大数量的数字位与偶数位次大数量的数字位 之和 与偶数位的最大数量的数字位与奇数位次大数量位之和 进行取最大值，那么我们现在的长度去减去最大值，那获得的就是最小的操作数了。

代码实现

class Solution {
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        HashMap<Integer,Integer> even = new HashMap<>();
        HashMap<Integer,Integer> odd = new HashMap<>();
        for(int i=0;i<n;i++) {
            if(i%2==0) {
                //记录偶数位上的每个数字个数
                even.put(nums[i],even.getOrDefault(nums[i],0)+1);
            } else {
                //记录奇数位上的每个数字个数
                odd.put(nums[i],odd.getOrDefault(nums[i],0)+1);
            }
        }
        //找出两个map中最多和次多的两个数字的key和val
        int[][] evenMaxAndSubMax = check(even);
        int[][] oddMaxAndSubMax = check(odd);
        //如果当前两个最多数量的key不相同 也就是 1 != 2 的情况下说明 当前长度 分别减去他们出现的频率 就是剩下的需要改变的正整数个数
        if(evenMaxAndSubMax[0][0] != oddMaxAndSubMax[0][0]) {
            n-= evenMaxAndSubMax[0][1];
            n-= oddMaxAndSubMax[0][1];
        } else { // 反之如果出现了两个数量最多的数字相同时 需要获得最小操作数 就要是比较当最大数和次大数的加和最大才能使得次数最小
            n-= Math.max(evenMaxAndSubMax[0][1]+oddMaxAndSubMax[1][1],oddMaxAndSubMax[0][1]+evenMaxAndSubMax[1][1]);   
        }
        return n;
    }
    
    int[][] check(HashMap<Integer,Integer> map) {
        int[][] maxAndSubMax = new int[2][2];
        //对于每个数字
        for(Integer key:map.keySet()) {
            //获取当前数字key的val
            int val = map.get(key);
            //找到个数数量前两个的数字进行数组存储 保存他们的 key 与 val || res[0][0] 是最多数量数字的key res[0][0] 是最多数量数字的val
            if(val>maxAndSubMax[0][1]) {
                maxAndSubMax[1][0] = maxAndSubMax[0][0];
                maxAndSubMax[1][1] = maxAndSubMax[0][1];
                maxAndSubMax[0][0] = key;
                maxAndSubMax[0][1] = val;
            } else if(val>maxAndSubMax[1][1]){//数量次多的key 与 val
                maxAndSubMax[1][0] = key;
                maxAndSubMax[1][1] = val;
            }
        }
        return maxAndSubMax;
    }
}

执行结果

📝T3.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 个魔法豆更少的方案。

提示

1 <= beans.length <= 10^5
1 <= beans[i] <= 10^5

?思路 ?

这道题的思路比较简单：

• 但是你会发现这道题虽然想的简单但是它给出的数量级太大，返回值都是一个long 那么肯定会有超时的可能。
• 这里先说思路:
• 利用(排序+前缀和) 的思路来进行求解
• 我们可以先将每个袋子全部拿空的话记录如果将所有袋子置零 那么这里所获得的值就是能拿出豆子的最大值，我们要求的最小值肯定是在其之下的。
• 设置滚动变量 通过枚举遍历 获得 每次 使得 每个袋子的魔法豆数量都为 beans[i] 个数时 所需要拿出的豆子个数

代码实现

class Solution {
    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans);
        int n = beans.length;
        long res = Long.MAX_VALUE;
        long sum = 0 ;
        //可以理解为可拿出魔法豆子的最大值 全部拿出 均置零
        for (int bean : beans){
            sum += bean;
        }

        //枚举遍历 获得 每次 使得 每个袋子的魔法豆数量都为 beans[i] 个数时 所需要拿出的豆子个数 
        for (int i = 0 ;i< n;i++){
            //滚动变量记录最小值 在于这个beans [i] * (n-i);
            res = Math.min(res,sum-(long)beans[i] * (n-i));
        }
        return res;
    }   
}

执行结果

🙊写在最后

小付打卡的第五场周赛 2022-02-13

尽可能把会做的题 都做好 就可以了

今天睡过头了 起来的时候就只有半个小时了=-=

本次周赛 对了两道题

第三题一直在超时 直接破防

所以还是很不错的周赛体验

最后

每天进步点 每天收获点

愿诸君 事业有成 学有所获

如果觉得不错 别忘啦一键三连哦~