5292. 划分数组为连续数字的集合
给你一个整数数组 nums
和一个正整数 k,请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
如果可以,请返回 True;否则,返回 False。
示例 1:
输入:nums = [1,2,3,3,4,4,5,6], k = 4
输出:true
解释:数组可以分成 [1,2,3,4] 和 [3,4,5,6]。
**题目表述为集合,不是数组。 =__=**
输入:nums = [3,3,2,2,1,1], k = 3
输出:true
分析:
需要将数组按照k个一组划分。所以一共有len / k
个集合。如果不能整除说明不符合条件。
因为考虑到是集合,所以先将数组进行排序。
- 首先用map统计每个数字才出现的次数。
- 然后遍历数组的每个元素。
- 从map中取出每个元素的出现次数。如果数量为0,说明该元素已经被包含到其他的集合啦,可以跳过了。
- 每取出一个元素,就可以将保存的个数-1。
- 然后就开始查询符合条件的集合。
- 从map中分别取出
num+i
的元素剩余次数,i
从1到len / k
。 - 如果次数为0,说明当前的这一个集合不符合条件。返回false
- 从map中分别取出
- 写到这里已经可以得到结果。但是在后序的查询过程中可能存在很多已经将数量减少到0的元素。
- 为了减少后序操作,定义一个变量m。维护已经出现的符合条件的集合的次数。如果m等于
len/k
,说明已经找到了全部符合条件的集合返回true;
- 为了减少后序操作,定义一个变量m。维护已经出现的符合条件的集合的次数。如果m等于
- 从map中取出每个元素的出现次数。如果数量为0,说明该元素已经被包含到其他的集合啦,可以跳过了。
public boolean isPossibleDivide(int[] nums, int k) {
int len = nums.length;
if(len%k!=0){
return false;
}
Arrays.sort(nums);
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
int count = len/k;
int m = 0;
for(int num:nums){
int start = map.get(num);
if(start==0){
//已经没有了
continue;
}
map.put(num,start-1);
for(int i =1;i<k;i++){
int temp = map.getOrDefault(num+i,0);
if(temp==0){
//当前序列不合法。
return false;
}
map.put(num+i,temp-1);
}
m++;
if(m==count){
return true;
}
}
return true;
}
5293. 子串的最大出现次数
给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:
子串中不同字母的数目必须小于等于 maxLetters
。
子串的长度必须大于等于 minSize
且小于等于 maxSize
。
输入:s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出:2
解释:子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求:2 个不同的字母,长度为 3 (在 minSize 和 maxSize 范围内)。
这道题需要寻找的是满足条件的出现次数最大的任意子串的次数。
- 虽然给定了最大和最小长度,实际上只需要使用最小的长度就能计算处出现的最大次数。
- 在计算出现次数的基础上,题目需要保证子串字母数量小于等于
maxLetter
,当然使用Set结合计算数量。如果不符合条件就舍弃当前子串。 - 为了保证在串s长度极长的情况下不会超时。可以使用Map保存每个串出现的次数。
- 在遍历结束后,统计集合中出现的最大次数,即为结果。
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
char[] arr= s.toCharArray();
Map<String,Integer> map = new HashMap<>();
for(int i =0;i<=s.length()-minSize;i++){
if(checkOut(arr,i,i+minSize-1)<=maxLetters){
String key = String.valueOf(arr,i,minSize);
map.put(key,map.getOrDefault(key,0)+1);
}
}
int count = 0;
for(Integer num : map.values()){
count = count<num ?num:count;
}
return count;
}
public int checkOut(char[] arr,int start,int end){
Set<Character> set = new HashSet<>();
for(int i =start;i<=end;i++){
set.add(arr[i]);
}
return set.size();
}