一,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;}
}