Day 42最大差值解题思路股票问题 1 的思路代码实现importjava.util.*;publicclassSolution{publicintgetDis(int[]A,intn){intret0;intpreMinA[0];for(inti0;in;i){preMinMath.min(preMin,A[i]);retMath.max(ret,A[i]-preMin);}returnret;}}兑换零钱解题思路完全背包问题不需要关心选的钱的下标代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt(),aimin.nextInt();int[]arrnewint[n];for(inti0;in;i)arr[i]in.nextInt();int[]dpnewint[5010];Arrays.fill(dp,0x3f3f3f3f);dp[0]0;for(inti0;in;i){for(intj0;j5010;j){if(jarr[i])dp[j]Math.min(dp[j-arr[i]]1,dp[j]);}}System.out.println(dp[aim]0x3f3f3f3f?-1:dp[aim]);}}小红的子串解题思路前缀和思想 滑动窗口滑动窗口统计字符种类不超过k的子串数量。子串总数可能达到n(n1)/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(n1)/2必须使用 longprivatestaticlongfind(intk){int[]hashnewint[26];intkind0;longcnt0;for(intleft0,right0;rightn;right){intinputs[right]-a;if(hash[input]0)kind;hash[input];while(kindk){intoutputs[left]-a;hash[output]--;if(hash[output]0)kind--;left;}// 对于每个 right窗口收缩到合法后所有起点位于 [left, right] 的子串都合法因此应增加// 关键固定 right只统计“以 right 位置结尾”的子串这种情况应该增加 right - left 1cnt(right-left1);}returncnt;}publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);nin.nextInt();intlin.nextInt(),rin.nextInt();sin.next().toCharArray();// 关键: 前缀和思路, 找 [l, r] - 找 [0, r] - [0, l - 1]System.out.println(find(r)-find(l-1));}}