企业官网建设流程全解析

目录

​编辑

一、 HJ63 DNA序列（滑动窗口）

题目描述

算法思路：滑动窗口

Java 代码实现

复杂度分析

二、[编程题] 神奇数（枚举与素数判断）

题目描述

算法思路：暴力枚举 + 判断

Java 代码实现

复杂度分析

三、 REAL433 字符串替换（字符串模拟）

题目描述

算法思路：单次遍历 + 尾插

Java 代码实现

复杂度分析

一、 HJ63 DNA序列（滑动窗口）

DNA序列_牛客题霸_牛客网

题目描述

给定一个 DNA 序列（由 A/C/G/T 组成），以及限定的子串长度 NN，请找出 GC 比例最高且长度为 NN 的第一个子串。

算法思路：滑动窗口

这道题是一道非常经典的定长滑动窗口问题。由于需要寻找长度为 NN 的连续子串，我们可以维护一个长度为 NN 的窗口，在字符串上从左向右滑动。

1. 使用left和right双指针，right主动向右扩展。

2. 用cnt统计当前窗口内 'C' 和 'G' 的数量。

3. 当窗口大小达到 NN 时，比较当前的cnt是否大于历史最大值count。由于要求“如果有多个则输出第一个”，因此仅当cnt > count时更新结果字符串。

4. 窗口右移：将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），我们完全可以直接暴力枚举区间内每一个数，并对每个数进行数位拆分和组合验证。

核心逻辑拆解：

1. 数位拆分：将数字 xx 拆解到数组中。

2. 两两组合：使用双重循环，挑出两个不同位置的数位（i != j）。

3. 去前导零：如果十位数字num[i] == 0，组成的两位数会带有前导零（如 05），需跳过。

4. 素数判断：判断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)×log⁡10(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(N+M)O(N+M)，其中 NN 为原字符串长度，MM 为参数数组长度。

• 空间复杂度：O(N+M)O(N+M)，用于构建结果字符串StringBuffer。