leetcode - 双周赛114

一，2869.收集元素的最小操作次数

// 解法：哈希表 + 从右往左遍历
class Solution {
    public int minOperations(List<Integer> nums, int k) {
        Set<Integer> set = new HashSet<>();
        for(int i=1; i<=k; i++){
            set.add(i);
        }
        for(int i=nums.size()-1; i>=0; i--){
            if(set.contains(nums.get(i))){
                set.remove(nums.get(i));
            }
            if(set.size() == 0)
                return nums.size()-i;
        }
        return -1;
    }
}

二，2870.使数组为空的最小操作次数 

首先明确一个点：2 和 3 可以组成除了 1 以外的所有的正整数。

证明：设一个正整数 X ，X > 1

           1)   X % 3 = 0，肯定可以

           2） X % 3 = 1，可以把最后一个3拿出来和剩下的1组成4，而4可以被2整除

           3） X % 3 = 2，剩余的2可以被2整除

再看题目，我们先统计每个相同元素出现的次数，然后根据上方的结论得出答案。 

class Solution {
    public int minOperations(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int ans = 0;
        for(int x : nums)
            map.put(x,map.getOrDefault(x,0)+1);
        for(Map.Entry<Integer,Integer> x : map.entrySet()){
            int val = x.getValue();
            if(val == 1) return -1;
            if(val % 3 == 0) ans += val/3;
            if(val % 3 == 1) ans += (val-3)/3+2;
            if(val % 3 == 2) ans += val/3+1;
        }
        return ans;
    }
}

 三，2871.将数组分割成最多数目的子数组

我们先来讲一下 & 的性质，0&0=0，0&1=0，1&1=1

推出：1）当两个数进行按位与操作，得到的数字 >= 两个数字的最小值。

           2）参与&运算的数越多，得到的数就越小。(AND最小值是将数组nums的全部元素进行&操作)

题目要我们在保证按位与AND值最小的情况下，尽可能多的分割数组，求最多子数组个数。

假设AND最小值为 a，将数组分成n个子数组时，分割后得到的AND值肯定大于等于 n*a。

推出：要想分割子数组，即 a >= n*a，我们的 a 即 AND最小值一定要为0，否则不能分割。

要想得到做多的子数组，遍历数组，进行&运算，一旦遇到 a = 0，ans += 1

class Solution {
    public int maxSubarrays(int[] nums) {
        int ans = 0;
        int a = -1;//-1的补码是全1，-1&n=n
        for(int i=0; i<nums.length; i++){
            a &= nums[i];
            if(a == 0){
                a = -1;
                ans++;
            }
        }
        return ans==0?1:ans;
    }
}

 四，2872.可以被 k 整除连通块的最大数目

class Solution {
    int ans = 0;
    int[] values;
    List<List<Integer>> g = new ArrayList<>();//得到每个点的相邻节点
    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        this.values = values;
        for(int i=0; i<n; i++){
            g.add(new ArrayList<Integer>());
        }
        for(int[] x : edges){
            g.get(x[0]).add(x[1]);
            g.get(x[1]).add(x[0]);
        }
        dfs(0,-1,k);
        return ans;
    }
    
    long dfs(int x, int father, int k){
        long s = values[x];
        for(int y : g.get(x)){
            if(y != father){
                s += dfs(y,x,k);
            }  
        }
        if(s%k == 0){
            s = 0;
            ans++;
        }
        return s;
    }
}