[数据结构与算法]力扣周赛 第280场 Java题解

🏠：博客首页： 进击的波吉
📕：今日分享的文章： 力扣周赛 第280场 Java题解
💝：坚持刷力扣，分享前三题题解🎈
🌱：Boji 还在努力学算法 ，如有疑问、疏漏之处，请多多指点🙏
??：自学成长的路上，感谢大家相伴！No hurry ， No Pause ！💝

开篇分享

??本次参加周赛AC第一题，第二题有知识点卡顿，就跳过了。。第三题爆搜，评测只过了一半，继续努力吧🏃

6004. 得到 0 的操作数

主要思路：首先要特判 都为 0的情况， 其次就 一个while循环结束！

时间复杂度： O(n) ;

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

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

题解参考:https://leetcode-cn.com/problems/minimum-operations-to-make-the-array-alternating/solution/nickzhou-sai-xi-lie-jian-dan-4fen-ti-by-vo2cj/

class Solution {
    public int minimumOperations(int[] nums) {
        int length = nums.length ;
        if (length < 2) {
            return 0 ;
        }

        Map<Integer, Integer> map1 = new HashMap<>() ;
        Map<Integer, Integer> map2 = new HashMap<>() ;

        for (int i = 0 ; i< length; i++) {
            if ( (i+1) % 2 == 1) {
                map1.put(nums[i], map1.getOrDefault(nums[i], 0) +1 ) ;
            } else {
                map2.put(nums[i], map2.getOrDefault(nums[i], 0) +1 ) ;
            }
        }

        int max1 = 0, mmax1 = 0 ; //max1 记录max1Num 出现的次数， mmax1 记录 次最大出现的次数
        int max1Num = 0 ;// 记录 最大的数字
        int count1 = 0 ; // 记录 奇数的总次数
        for (Integer key : map1.keySet()) {
            count1 += map1.get(key) ;
            if (max1 < map1.get(key)) {
                mmax1 = max1 ;
                max1 = map1.get(key) ;
                max1Num = key ;
            }else if (mmax1 < map1.get(key)) {
                mmax1 = map1.get(key) ;
            }
        }

        int max2 =0, mmax2 =0  ;
        int max2Num = 0 ;
        int count2 = 0 ;
        for (Integer key : map2.keySet()) {
            count2 += map2.get(key) ;
            if (max2 < map2.get(key)) {
                mmax2 = max2 ;
                max2 = map2.get(key) ;
                max2Num = key ;
            } else if (mmax2 < map2.get(key)) {
                mmax2 = map2.get(key) ; 
            }
        }

        if (max1Num != max2Num) {
            return length - max1 - max2 ; //当两个数不相等时，总长度 - 奇数相同数出现的最大次数 - 偶数相同数出现的最大次数  
        } else {
            //若两个数形相等，要找出最简方案，分别讨论mmax1 与 max2 之和  以及 mmax2 与 max1 之和 的最小值
            return Math.min((count1 - mmax1 + count2 - max2), (count1 - max1 + count2 - mmax2) ) ;
        }
    }
}

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

第三题自己爆搜过不了，借鉴了歪果仁的解法，属实精妙

nums = a, b, c, d ( a < b < c < d )
if make nums [a, a, a, a] remove beans (b - a) + (c - a) + (d - a) == b + c + d - 3a
if make nums [0, b, b, b] remove beans a + (c - b) + (d - b) == a + c + d - 2b
if make nums [0, 0, c, c] remove beans a + b + (d - c) == a + b + d - c
if make nums [0, 0, 0, d] remove beans a + b + c
结论：
b + c + d - 3a == (a + b + c + d) - 4a
a + c + d - 2b == (a + b + c + d) - 3b
a + b + d -c == (a + b + c + d) - 2c
a + b + c == (a + b + c + d) - d
注意： 数值范围爆 int ，应该用long 存值

class Solution {
    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans) ;
        long sum= 0  ;
        for (int bean : beans) {
            sum+= bean ;
        }

        long res = Long.MAX_VALUE ;
        long m = beans.length ;
        for (int i = 0 ; i < beans.length; i++,m--) {
            res = Math.min(res , sum - m * beans[i]) ;
        }
       return res ;
    }
}