-二分与双指针的结合 + 2024秦皇岛-Problem D)
文章目录
- 一. 力扣 [713. 乘积小于 K 的子数组](https://leetcode.cn/problems/subarray-product-less-than-k/description/)
- 1. 题目解析
- 2. 滑动窗口算法原理
- 3. 二分+对数+前缀和+双指针
- 3. 代码
- 二. 2024秦皇岛-Problem D
- 1. 题目解析
- 2. 算法原理
- 3. 代码
一. 力扣713. 乘积小于 K 的子数组
1. 题目解析
题意简单明了, 成绩小于指定的k, 子数组指的是连续的区间
2. 滑动窗口算法原理
3. 二分+对数+前缀和+双指针
3. 代码
滑动窗口代码👇
classSolution{publicintnumSubarrayProductLessThanK(int[]nums,intk){intl=0,r=0,mul=1,ret=0;// k为1, 可以直接返回0, 因为这里乘积最小值为1, 且numd[i]最小值也是1if(k<=1)return0;while(r<nums.length){mul*=nums[r];while(mul>=k){mul/=nums[l];l++;}ret+=r-l+1;r++;}returnret;}}二分+双指针代码👇
classSolution{publicintnumSubarrayProductLessThanK(int[]nums,intk){if(k<=1){return0;}intn=nums.length;double[]dp=newdouble[n+1];for(inti=1;i<=n;i++){dp[i]=dp[i-1]+Math.log(nums[i-1]);}doublelogk=Math.log(k);intret=0;for(intj=0;j<n;j++){intl=0;// l左端点可能为0intr=j;// r最大就是右端点inti=j+1;// 左端点的最坏情况,nums[j]本身也不满足doublet=dp[j+1]-logk+1e-10;while(l<=r){intmid=l+(r-l)/2;if(dp[mid]>t){i=mid;r=mid-1;}else{l=mid+1;}}ret+=j-i+1;}returnret;}}二. 2024秦皇岛-Problem D
小编总结了两天的超详细解析
1. 题目解析
- 题目很好理解, 重要的是对于示例的分析, 这道题的示例给的可以说很恶心
- 猫条可以类比为修改次数(交换次数)
2. 算法原理
这道题用到的算法思想还是较多的, 动态规划 + 正难则反 + 贡献计数
- 首先是步骤一: 贡献计数, 即如何给定字符串中的优美子序列
- 步骤二: 将问题转化, 反向思考, 在构建字符串过程中统计优美子序列
- 重头戏: 动态规划, 要理解其中 i , j, k 分别对应的含义
- 兄弟们可能有疑惑的地方, 为什么要从0遍历k
3. 代码
importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Arrays;importjava.util.StringTokenizer;publicclassMy_Main{// 封装从左面挑选两个的方法staticintselect2(intleft){return(left)*(left-1)/2;}publicstaticvoidmain(String[]args)throwsException{// 读取输入BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringTokenizerst=newStringTokenizer(br.readLine());char[]cc=st.nextToken().toCharArray();st=newStringTokenizer(br.readLine());intm=Integer.valueOf(st.nextToken());intn=cc.length;// 统计字符c的数量 和 记录c的下标intC=0;for(charch:cc)if(ch=='c')C++;intP=n-C;intidx=1;int[]pos=newint[C+1];//我们要填的是下一个数, 即i+1这个数, 因此i从0开始遍历,for(inti=0;i<n;i++){if(cc[i]=='c'){pos[idx++]=i+1;// 让index从1开始, 同时每个index绑定的下标也右移一位, 即原本cc[0]位置为c, 对应的就是pos[1] = 1}}// 建立dp表int[][][]dp=newint[n+1][C+1][m+1];// 初始化for(inti=0;i<=n;i++){for(intj=0;j<=C;j++){Arrays.fill(dp[i][j],-1);}}dp[0][0][0]=0;for(inti=0;i<n;i++){// j 表示的是c的个数,超过i或者C都没有意义, 因此选择较小的那一个for(intj=0;j<=Math.min(i,C);j++){for(intk=0;k<=m;k++){// 当前位置j和k不能满足,满足的话会被提前填写if(dp[i][j][k]<0)continue;// 放p,先判断是否有剩余if(i-j<P){intaddP=select2(j)*(C-j);dp[i+1][j][k]=Math.max(dp[i+1][j][k],dp[i][j][k]+addP);}// 放c, j<C才有意义, 才可以放cif(j<C){intaddC=select2(i-j)*(P-(i-j));// 求总代价intcost=k+Math.abs(i+1-pos[j+1]);if(cost<=m){dp[i+1][j+1][cost]=Math.max(dp[i+1][j+1][cost],dp[i][j][k]+addC);}}}}}intret=0;for(intk=m;k>=0;k-=2){ret=Math.max(dp[n][C][k],ret);}System.out.println(ret);}}
