不愧是EA的题，我最爱的模拟人生……好难，呜呜
目录
1、找出峰值 - 暴力枚举
2、需要添加的硬币的最小数量 - 思维 + 贪心
3、统计完全子字符串 - 滑窗 + 分组循环
1、找出峰值 - 暴力枚举
2951. 找出峰值
class Solution {
public List<Integer> findPeaks(int[] m) {
List<Integer> res=new ArrayList<>();
for(int i=1;i<m.length-1;i++)
if(m[i-1]<m[i]&&m[i]>m[i+1]) res.add(i);
return res;
}
}2、需要添加的硬币的最小数量 - 思维 + 贪心
真难啊……
2952. 需要添加的硬币的最小数量
思路：
- 题目只要求返回最少添加硬币数量，对硬币顺序没有关系，因此我们将数组顺序排序
- 假设数组中一个数都不用，能凑出来的数就是[0,1)，此时如果加入x，这个范围就会扩大，新得到的区间为[x,1+x)，此时若两个区间没有重合，则需要新增硬币
- 为了让新增硬币数最少，我们只能添加缺的硬币（只增加最紧缺的）
- 我们设定右边界为v，遍历数组中每一个值x，如果右边界覆盖不到x，则加硬币，更新右边界，直到可以覆盖x后再返回来根据x更新右边界，直到右边界v > target，说明满足条件
class Solution {
public int minimumAddedCoins(int[] a, int target) {
int v=1,res=0,i=0;
Arrays.sort(a);
while(v<=target)
{
if(i<a.length&&a[i]<=v)
{
v+=a[i]; //两区间重合，则更新右区间
i++;
}
else //假如遍历完整个数组仍然不满足target 则需要不断扩大右边界
{
v*=2; //右区间拓展
res++; //两区间不重合，新增硬币
}
}
return res;
}
}
3、统计完全子字符串 - 滑窗 + 分组循环
2953. 统计完全子字符串
分组循环
思路：
第一步：分组循环分割子串
根据【相邻字符在字母表中的顺序 至多 相差 2 】 的条件，我们可以将整个字符串分割成若干个子串，再逐个对子串进行处理
比如说：aabb | ffgg ccddef | zzz | aaa
第二步：逐个对子串进行滑窗统计
根据【
s中每个字符 恰好 出现k次】，我们知道若字符串中有m种字母，则满足条件的子串长度必然是k*m，所以我们维护k*m的滑动窗口，每次对窗口内的字母出现次数进行统计，满足条件的子串res++滑窗 —— 外层枚举右侧（一个一个走），内层根据情况移动左侧
class Solution {
public int countCompleteSubstrings(String s, int k) {
int n=s.length();
int res=0;
//首先划分若干子串，对每个子串再进行处理（分组循环）
for(int i=0;i<n;)
{
int st=i;
i++;
for(;i<n&&Math.abs(s.charAt(i)-s.charAt(i-1))<=2;i++);
//上面for循环结束后，i指向分割子串最末尾的下一个字符
res+=f(s.substring(st,i),k); //将分割好的子串逐一处理
}
return res;
}
public int f(String x,int k)
{
char[] s=x.toCharArray();
int res=0;
for(int m=1;m<=26&&k*m<=s.length;m++) //枚举有m种字符
{
int[] cnt=new int[26]; //哈希表统计字符出现次数
for(int r=0;r<s.length;r++)
{
cnt[s[r]-'a']++;
int l=r+1-k*m; //保证滑窗大小为k*m
if(l>=0)
{
boolean flag=true;
for(int t:cnt)
if(t!=k&&t>0)
{
flag=false;
break; //如果滑窗内每个字符不是恰好满足k个
}
if(flag) res++; //统计满足条件的子串
cnt[s[l]-'a']--;
}
}
}
return res;
}
}
