目录编辑一、 HJ63 DNA序列滑动窗口题目描述算法思路滑动窗口Java 代码实现复杂度分析二、[编程题] 神奇数枚举与素数判断题目描述算法思路暴力枚举 判断Java 代码实现复杂度分析三、 REAL433 字符串替换字符串模拟题目描述算法思路单次遍历 尾插Java 代码实现复杂度分析一、 HJ63 DNA序列滑动窗口DNA序列_牛客题霸_牛客网题目描述给定一个 DNA 序列由 A/C/G/T 组成以及限定的子串长度 NN请找出 GC 比例最高且长度为 NN 的第一个子串。算法思路滑动窗口这道题是一道非常经典的定长滑动窗口问题。由于需要寻找长度为 NN 的连续子串我们可以维护一个长度为 NN 的窗口在字符串上从左向右滑动。使用left和right双指针right主动向右扩展。用cnt统计当前窗口内 C 和 G 的数量。当窗口大小达到 NN 时比较当前的cnt是否大于历史最大值count。由于要求“如果有多个则输出第一个”因此仅当cnt count时更新结果字符串。窗口右移将left指向的字符移出窗口若它是 C 或 G则cnt--。Java 代码实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); String s in.next(); int n in.nextInt(); int m s.length(); int left 0, right 0; int count 0, cnt 0; // count记录最大GC数cnt记录当前窗口GC数 String ret ; while (right m) { char ch s.charAt(right); if (ch C || ch G) cnt; // 窗口大小达到n if (right - left 1 n) { if (cnt count) { count cnt; ret s.substring(left, right 1); } // 左指针移除字符维护窗口大小 if (s.charAt(left) C || s.charAt(left) G) { cnt--; } left; } right; } System.out.println(ret); } }复杂度分析时间复杂度O(N)O(N)其中 NN 为字符串长度。左右指针分别最多遍历字符串一次。空间复杂度O(1)O(1)仅使用了常数个变量。二、[编程题] 神奇数枚举与素数判断神奇数_牛客笔试题_牛客网题目描述神奇数定义存在不同位置的两个数位组成一个两位数不含前导0且这个两位数是质数。例如 153可以组成 13、15、31、53 等其中 13、31、53 均为质数所以 153 是神奇数。给定区间 [a,b][a,b]1≤a≤b≤100001≤a≤b≤10000求区间内神奇数的个数。算法思路暴力枚举 判断由于题目数据范围非常小最大到 10000我们完全可以直接暴力枚举区间内每一个数并对每个数进行数位拆分和组合验证。核心逻辑拆解数位拆分将数字 xx 拆解到数组中。两两组合使用双重循环挑出两个不同位置的数位i ! j。去前导零如果十位数字num[i] 0组成的两位数会带有前导零如 05需跳过。素数判断判断num[i] * 10 num[j]是否为素数。Java 代码实现import java.util.Scanner; public class Main { // 判断素数试除法 public static boolean isPriem(int x) { if (x 2) return false; for (int i 2; i Math.sqrt(x); i) { if (x % i 0) return false; } return true; } // 检查是否为神奇数 public static int check(int x) { int[] num new int[10]; int n 0; // 拆解数位 while (x ! 0) { num[n] x % 10; x / 10; } // 枚举所有不同位置的两个数位 for (int i 0; i n; i) { for (int j 0; j n; j) { if (num[i] ! 0 i ! j) { // 不含前导0且位置不同 if (isPriem(num[i] * 10 num[j])) { return 1; } } } } return 0; } public static void main(String[] args) { Scanner in new Scanner(System.in); int a in.nextInt(), b in.nextInt(); int ret 0; for (int i a; i b; i) { ret check(i); } System.out.println(ret); } }复杂度分析时间复杂度O((b−a)×log10(x)×x)O((b−a)×log10(x)×x)。对于最大数据范围循环次数有限绝对能在 1 秒内跑完。空间复杂度O(1)O(1)数位数组大小固定为 10。三、 REAL433 字符串替换字符串模拟字符串替换_牛客题霸_牛客网题目描述实现一个字符串替换函数。将原串中的%s按顺序替换为参数列表arg中的字符。若参数列表的字符数大于占位符数则将剩下的参数添加到字符串的末尾。保证参数个数大于等于占位符个数。算法思路单次遍历 尾插这道题是典型的模拟题考察对字符串 API 的熟悉程度和边界处理。占位符识别通过遍历原字符串遇到%字符时说明遇到了占位符题目隐含占位符为%s代码中通过i跳过了s。此时从arg数组中取出下一个字符追加到结果中。尾部追加遍历完原字符串后检查arg数组是否还有剩余字符若有则全部追加到结果字符串末尾。Java 代码实现import java.util.*; public class StringFormat { public String formatString(String A, int n, char[] arg, int m) { int count 0; StringBuffer ret new StringBuffer(); int i 0; while (i n) { if (A.charAt(i) %) { ret.append(arg[count]); i; // 跳过占位符中的 s与循环末尾的 i 结合 } else { ret.append(A.charAt(i)); } i; } // 追加剩余的参数字符 while (count arg.length) { ret.append(arg[count]); } return String.valueOf(ret); } }复杂度分析时间复杂度O(NM)O(NM)其中 NN 为原字符串长度MM 为参数数组长度。空间复杂度O(NM)O(NM)用于构建结果字符串StringBuffer。
算法实战：滑动窗口、素数枚举与字符串模拟（三道经典题解）
目录编辑一、 HJ63 DNA序列滑动窗口题目描述算法思路滑动窗口Java 代码实现复杂度分析二、[编程题] 神奇数枚举与素数判断题目描述算法思路暴力枚举 判断Java 代码实现复杂度分析三、 REAL433 字符串替换字符串模拟题目描述算法思路单次遍历 尾插Java 代码实现复杂度分析一、 HJ63 DNA序列滑动窗口DNA序列_牛客题霸_牛客网题目描述给定一个 DNA 序列由 A/C/G/T 组成以及限定的子串长度 NN请找出 GC 比例最高且长度为 NN 的第一个子串。算法思路滑动窗口这道题是一道非常经典的定长滑动窗口问题。由于需要寻找长度为 NN 的连续子串我们可以维护一个长度为 NN 的窗口在字符串上从左向右滑动。使用left和right双指针right主动向右扩展。用cnt统计当前窗口内 C 和 G 的数量。当窗口大小达到 NN 时比较当前的cnt是否大于历史最大值count。由于要求“如果有多个则输出第一个”因此仅当cnt count时更新结果字符串。窗口右移将left指向的字符移出窗口若它是 C 或 G则cnt--。Java 代码实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); String s in.next(); int n in.nextInt(); int m s.length(); int left 0, right 0; int count 0, cnt 0; // count记录最大GC数cnt记录当前窗口GC数 String ret ; while (right m) { char ch s.charAt(right); if (ch C || ch G) cnt; // 窗口大小达到n if (right - left 1 n) { if (cnt count) { count cnt; ret s.substring(left, right 1); } // 左指针移除字符维护窗口大小 if (s.charAt(left) C || s.charAt(left) G) { cnt--; } left; } right; } System.out.println(ret); } }复杂度分析时间复杂度O(N)O(N)其中 NN 为字符串长度。左右指针分别最多遍历字符串一次。空间复杂度O(1)O(1)仅使用了常数个变量。二、[编程题] 神奇数枚举与素数判断神奇数_牛客笔试题_牛客网题目描述神奇数定义存在不同位置的两个数位组成一个两位数不含前导0且这个两位数是质数。例如 153可以组成 13、15、31、53 等其中 13、31、53 均为质数所以 153 是神奇数。给定区间 [a,b][a,b]1≤a≤b≤100001≤a≤b≤10000求区间内神奇数的个数。算法思路暴力枚举 判断由于题目数据范围非常小最大到 10000我们完全可以直接暴力枚举区间内每一个数并对每个数进行数位拆分和组合验证。核心逻辑拆解数位拆分将数字 xx 拆解到数组中。两两组合使用双重循环挑出两个不同位置的数位i ! j。去前导零如果十位数字num[i] 0组成的两位数会带有前导零如 05需跳过。素数判断判断num[i] * 10 num[j]是否为素数。Java 代码实现import java.util.Scanner; public class Main { // 判断素数试除法 public static boolean isPriem(int x) { if (x 2) return false; for (int i 2; i Math.sqrt(x); i) { if (x % i 0) return false; } return true; } // 检查是否为神奇数 public static int check(int x) { int[] num new int[10]; int n 0; // 拆解数位 while (x ! 0) { num[n] x % 10; x / 10; } // 枚举所有不同位置的两个数位 for (int i 0; i n; i) { for (int j 0; j n; j) { if (num[i] ! 0 i ! j) { // 不含前导0且位置不同 if (isPriem(num[i] * 10 num[j])) { return 1; } } } } return 0; } public static void main(String[] args) { Scanner in new Scanner(System.in); int a in.nextInt(), b in.nextInt(); int ret 0; for (int i a; i b; i) { ret check(i); } System.out.println(ret); } }复杂度分析时间复杂度O((b−a)×log10(x)×x)O((b−a)×log10(x)×x)。对于最大数据范围循环次数有限绝对能在 1 秒内跑完。空间复杂度O(1)O(1)数位数组大小固定为 10。三、 REAL433 字符串替换字符串模拟字符串替换_牛客题霸_牛客网题目描述实现一个字符串替换函数。将原串中的%s按顺序替换为参数列表arg中的字符。若参数列表的字符数大于占位符数则将剩下的参数添加到字符串的末尾。保证参数个数大于等于占位符个数。算法思路单次遍历 尾插这道题是典型的模拟题考察对字符串 API 的熟悉程度和边界处理。占位符识别通过遍历原字符串遇到%字符时说明遇到了占位符题目隐含占位符为%s代码中通过i跳过了s。此时从arg数组中取出下一个字符追加到结果中。尾部追加遍历完原字符串后检查arg数组是否还有剩余字符若有则全部追加到结果字符串末尾。Java 代码实现import java.util.*; public class StringFormat { public String formatString(String A, int n, char[] arg, int m) { int count 0; StringBuffer ret new StringBuffer(); int i 0; while (i n) { if (A.charAt(i) %) { ret.append(arg[count]); i; // 跳过占位符中的 s与循环末尾的 i 结合 } else { ret.append(A.charAt(i)); } i; } // 追加剩余的参数字符 while (count arg.length) { ret.append(arg[count]); } return String.valueOf(ret); } }复杂度分析时间复杂度O(NM)O(NM)其中 NN 为原字符串长度MM 为参数数组长度。空间复杂度O(NM)O(NM)用于构建结果字符串StringBuffer。
