笔试强训 Day 42：最大差值、兑换零钱、小红的子串
Day 42
最大差值
解题思路：
- 股票问题 1 的思路；
代码实现：
importjava.util.*;publicclassSolution{publicintgetDis(int[]A,intn){intret=0;intpreMin=A[0];for(inti=0;i<n;i++){preMin=Math.min(preMin,A[i]);ret=Math.max(ret,A[i]-preMin);}returnret;}}兑换零钱
解题思路：
- 完全背包问题，不需要关心选的钱的下标；
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt(),aim=in.nextInt();int[]arr=newint[n];for(inti=0;i<n;i++)arr[i]=in.nextInt();int[]dp=newint[5010];Arrays.fill(dp,0x3f3f3f3f);dp[0]=0;for(inti=0;i<n;i++){for(intj=0;j<5010;j++){if(j>=arr[i])dp[j]=Math.min(dp[j-arr[i]]+1,dp[j]);}}System.out.println(dp[aim]==0x3f3f3f3f?-1:dp[aim]);}}小红的子串
解题思路：前缀和思想 + 滑动窗口
- 滑动窗口统计字符种类不超过
k的子串数量。 - 子串总数可能达到
n(n+1)/2，计数需使用long。 - 固定
right后，合法子串的起点范围为[left, right]，收集以 right 为结尾的子串个数。 - 字符种类在
[l,r]内的子串数为find(r) - find(l-1)。
代码实现：
importjava.util.*;publicclassMain{privatestaticchar[]s;privatestaticintn;// 滑动窗口统计种类不超过 k 的个数// 关键：滑动窗口不方便同时统计 [r,l], 只能先算 [0, r] 和 [0, l - 1], 否则会遗漏很多情况// 关键点：计数可能达到约 n(n+1)/2，必须使用 longprivatestaticlongfind(intk){int[]hash=newint[26];intkind=0;longcnt=0;for(intleft=0,right=0;right<n;right++){intinput=s[right]-'a';if(hash[input]==0)kind++;hash[input]++;while(kind>k){intoutput=s[left]-'a';hash[output]--;if(hash[output]==0)kind--;left++;}// 对于每个 right，窗口收缩到合法后，所有起点位于 [left, right] 的子串都合法，因此应增加// 关键：固定 right，只统计“以 right 位置结尾”的子串，这种情况应该增加 right - left + 1cnt+=(right-left+1);}returncnt;}publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);n=in.nextInt();intl=in.nextInt(),r=in.nextInt();s=in.next().toCharArray();// 关键: 前缀和思路, 找 [l, r] -> 找 [0, r] - [0, l - 1]System.out.println(find(r)-find(l-1));}}