南沙网站建设,嵌入式软件开发工程师做什么,做网站公司选智投未来,加强网站网络安全建设目录
3768. 字符串删减 - 滑动窗口ac
799. 最长连续不重复子序列 - 滑动窗口
800. 数组元素的目标和 - 二分ac
2816. 判断子序列 - 双指针
1238. 日志统计 - 滑动窗口
1240. 完全二叉树的权值 - 双指针
1、前缀和 - 通过了 5/12个数据
2、双指针 3768. 字符串删减 -…目录
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 scnew Scanner(System.in);int nsc.nextInt();String ssc.next();int res0,cnt0;for(int l0,r0;rn;r){char cs.charAt(r);if(cnt2cx){res;l;}else if(cx) cnt;else {cnt0;lr;}}System.out.print(res);}
} 799. 最长连续不重复子序列 - 滑动窗口
活动 - AcWing 题目 给定一个长度为 n 的整数序列请找出最长的不包含重复的数的连续区间输出它的长度。 输入样例 5 1 2 2 3 5 输出样例 3 思路 用一个数组统计每个数字出现个数 滑动窗口中如果出现重复数字则左边界增大缩小滑窗直至不出现重复数字 不断更新最大连续不重复子序列长度 import java.util.*;class Main
{static int N100010;static int[] stnew int[N];public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt();int[] anew int[n];for(int i0;in;i) a[i]sc.nextInt();int res0;for(int l0,r0;rn;r){st[a[r]];while(lrst[a[r]]1) st[a[l]]--; //如果滑窗内仍存在重复数字 则缩小滑窗resMath.max(res,r-l1);}System.out.print(res);}
} 800. 数组元素的目标和 - 二分ac
活动 - AcWing
import java.util.*;class Main
{static int N100010;static int[] anew int[N],bnew int[N];public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt(),msc.nextInt(),xsc.nextInt();for(int i0;in;i) a[i]sc.nextInt();for(int j0;jm;j) b[j]sc.nextInt();for(int i0;in;i){int tx-a[i];int l0,rm-1;while(lr){int midlr1;if(b[mid]t) rmid;else lmid1;}if(b[l]t){System.out.print(i l);break;}}}
} 2816. 判断子序列 - 双指针
活动 - AcWing 题目 思路 用i指针指向aj指针指向b 遍历b数组如果a[i]b[j]则向后移动i指针 如果遍历完in说明a全部匹配成功说明a是b的子序列 import java.util.*;class Main
{static int N100010;static int[] anew int[N],bnew int[N];public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt(),msc.nextInt();for(int i0;in;i) a[i]sc.nextInt();for(int j0;jm;j) b[j]sc.nextInt();int i0;for(int j0;jm;j){if(ina[i]b[j]) i;}if(in) System.out.print(Yes);else System.out.print(No);}
} 1238. 日志统计 - 滑动窗口
活动 - AcWing 题目 思路 按时间从小到大顺序排序 枚举时间段滑动窗口内为合法时间记录该区间内帖子的赞数 如果在滑窗内且赞数≥k则为热帖标记上 import java.util.*;class Main
{static int N100010;public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt(),dsc.nextInt(),ksc.nextInt();int[][] listnew int[n][2];int[] cntnew int[N];int[] stnew int[N];for(int i0;in;i){list[i][0]sc.nextInt();list[i][1]sc.nextInt();}Arrays.sort(list,(o1,o2)-{return o1[0]-o2[0];});for(int l0,r0;rn;r) //滑动窗口是合法时间段 统计滑窗内是否有热帖存在{int idlist[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 i0;i100000;i) if(st[i]1) System.out.println(i);}
} 1240. 完全二叉树的权值 - 双指针
活动 - AcWing 题目 1、前缀和 - 通过了 5/12个数据
看错题了概念问题是完全二叉树看成满完全二叉树了…… 完全二叉树共n层其中n-1层是满二叉树结构最后一层所有节点都在最左边 import java.util.*;class Main
{static int N100010;public static int work(int n){int cnt0;while(n1){n/2;cnt;}return cnt;}public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt();int[] anew int[N];int[] snew int[N];for(int i1;in;i) {a[i]sc.nextInt();s[i]s[i-1]a[i];}int twork(n1);t--;int cnt1,pre1;int maxxs[1],res1;while(t--0){int r(int)Math.pow(2,cnt);int sums[r]-s[pre];if(maxxsum){maxxsum;int tpwork(r1);restp;}cnt;prer;}System.out.print(res);}
}
2、双指针 思路 枚举每一层的起点和层数 计算每一层的总和 取最大值 import java.util.*;class Main
{static int N100010;public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nextInt();int[] anew int[N];for(int i1;in;i) a[i]sc.nextInt();long maxx-0x3f3f3f3f;int res0;for(int i1,d1;in;i*2,d) //i为起点下标 d为层数{long sum0;for(int ji;ji(1d-1)jn;j) suma[j]; //1d指将1位二进制数向左移d位 即2^dif(summaxx){maxxsum;resd;}}System.out.print(res);}
}
