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=nfor(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;}
}