【蓝桥杯集训4】双指针专题（6 / 6）

目录

3768. 字符串删减 - 滑动窗口ac

799. 最长连续不重复子序列 - 滑动窗口

800. 数组元素的目标和 - 二分ac

2816. 判断子序列 - 双指针

1238. 日志统计 - 滑动窗口

1240. 完全二叉树的权值 - 双指针  

1、前缀和 - 通过了 5/12个数据 

2、双指针

---

3768. 字符串删减 - 滑动窗口ac

3768. 字符串删减 - AcWing题库

题目：

思路：

用双指针l和r，移动r指针

当已经统计了2个x，若下一个字符为x，则需要删除1个x，且滑窗左边界往后移一位

若下一个字符不为x，则统计x个数的cnt清零，缩小滑窗至该非x字符上

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();String s=sc.next();int res=0,cnt=0;for(int l=0,r=0;r<n;r++){char c=s.charAt(r);if(cnt==2&&c=='x'){res++;l++;}else if(c=='x') cnt++;else {cnt=0;l=r;}}System.out.print(res);}
}

799. 最长连续不重复子序列 - 滑动窗口

活动 - AcWing

题目：

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入样例：
5
1 2 2 3 5
输出样例：
3

思路：

用一个数组统计每个数字出现个数

滑动窗口中如果出现重复数字，则左边界增大缩小滑窗直至不出现重复数字

不断更新最大连续不重复子序列长度

import java.util.*;class Main
{static int N=100010;static int[] st=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] a=new int[n];for(int i=0;i<n;i++) a[i]=sc.nextInt();int res=0;for(int l=0,r=0;r<n;r++){st[a[r]]++;while(l<r&&st[a[r]]>1) st[a[l++]]--; //如果滑窗内仍存在重复数字 则缩小滑窗res=Math.max(res,r-l+1);}System.out.print(res);}
}

 

800. 数组元素的目标和 - 二分ac

活动 - AcWing

import java.util.*;class Main
{static int N=100010;static int[] a=new int[N],b=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt(),x=sc.nextInt();for(int i=0;i<n;i++) a[i]=sc.nextInt();for(int j=0;j<m;j++) b[j]=sc.nextInt();for(int i=0;i<n;i++){int t=x-a[i];int l=0,r=m-1;while(l<r){int mid=l+r>>1;if(b[mid]>=t) r=mid;else l=mid+1;}if(b[l]==t){System.out.print(i+" "+l);break;}}}
}

 

2816. 判断子序列 - 双指针

活动 - AcWing

题目：

思路：

用i指针指向a，j指针指向b

遍历b数组，如果a[i]==b[j]，则向后移动i指针

如果遍历完，i==n，说明a全部匹配成功，说明a是b的子序列

import java.util.*;class Main
{static int N=100010;static int[] a=new int[N],b=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();for(int i=0;i<n;i++) a[i]=sc.nextInt();for(int j=0;j<m;j++) b[j]=sc.nextInt();int i=0;for(int j=0;j<m;j++){if(i<n&&a[i]==b[j]) i++;}if(i==n) System.out.print("Yes");else System.out.print("No");}
}

 

1238. 日志统计 - 滑动窗口

活动 - AcWing

题目：

思路：

按时间从小到大顺序排序

枚举时间段，滑动窗口内为合法时间，记录该区间内帖子的赞数

如果在滑窗内且赞数≥k，则为热帖，标记上

import java.util.*;class Main
{static int N=100010;public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),d=sc.nextInt(),k=sc.nextInt();int[][] list=new int[n][2];int[] cnt=new int[N];int[] st=new int[N];for(int i=0;i<n;i++){list[i][0]=sc.nextInt();list[i][1]=sc.nextInt();}Arrays.sort(list,(o1,o2)->{return o1[0]-o2[0];});for(int l=0,r=0;r<n;r++) //滑动窗口是合法时间段 统计滑窗内是否有热帖存在{int id=list[r][1];cnt[id]++;while(list[r][0]-list[l][0]>=d) //超过最大时间段 缩小滑窗{cnt[list[l][1]]--;l++;}if(cnt[id]>=k) st[id]=1;}for(int i=0;i<=100000;i++) if(st[i]==1) System.out.println(i);}
}

 

1240. 完全二叉树的权值 - 双指针  

活动 - AcWing

题目：

1、前缀和 - 通过了 5/12个数据 

看错题了，概念问题，是完全二叉树，看成满完全二叉树了……

完全二叉树，共n层，其中n-1层是满二叉树结构，最后一层所有节点都在最左边

import java.util.*;class Main
{static int N=100010;public static int work(int n){int cnt=0;while(n>1){n/=2;cnt++;}return cnt;}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] a=new int[N];int[] s=new int[N];for(int i=1;i<=n;i++) {a[i]=sc.nextInt();s[i]=s[i-1]+a[i];}int t=work(n+1);t--;int cnt=1,pre=1;int maxx=s[1],res=1;while(t-->0){int r=(int)Math.pow(2,cnt);int sum=s[r]-s[pre];if(maxx<sum){maxx=sum;int tp=work(r+1);res=tp;}cnt++;pre=r;}System.out.print(res);}
}

2、双指针

思路：

枚举每一层的起点和层数

计算每一层的总和 取最大值

import java.util.*;class Main
{static int N=100010;public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] a=new int[N];for(int i=1;i<=n;i++) a[i]=sc.nextInt();long maxx=-0x3f3f3f3f;int res=0;for(int i=1,d=1;i<=n;i*=2,d++) //i为起点下标 d为层数{long sum=0;for(int j=i;j<i+(1<<d-1)&&j<=n;j++) sum+=a[j]; //1<<d指将1位二进制数向左移d位 即2^dif(sum>maxx){maxx=sum;res=d;}}System.out.print(res);}
}