本文主要是介绍Leetcode周赛374补题（3 / 3） - EA专场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
不愧是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*mif(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;}
}
这篇关于Leetcode周赛374补题（3 / 3） - EA专场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
