C++ 笔试刷题 Day 16
今天整理了三道经典的 C++ 算法题，涵盖字符串处理、数字逻辑和滑动窗口。咱们直接过一遍思路和代码。
一、字符串替换
题目描述
给定一个字符串 A 及其长度 n，以及一个字符数组 arg 和元素个数 m。要求在 A 中找到所有的 %s 占位符，并依次用 arg 中的字符进行替换。
思路分析
这题其实不难，核心逻辑很直观：遍历原字符串，遇到 %s 就取下一个可用字符填入结果串。没必要原地修改，新建一个结果串 ret 更稳妥。
注意点：
%s的数量可能少于arg中的字符数量，多余的字符也要追加到结果末尾。- 循环边界要处理好，避免越界。
代码实现
class StringFormat {
public:
string formatString(string A, int n, vector<char> arg, int m) {
string ret;
int sz = A.size();
int k = 0;
for (int i = 0, j = 1; j < sz; i++, j++) {
if (A[i] != '%' || A[j] != 's') {
ret += A[i];
} else {
ret += arg[k++];
i++;
j++; // 跳过已匹配的 s
}
}
// 处理最后一个字符，防止漏掉非 %s 结尾的情况
if (sz > 1 && A[sz - 2] != '%') {
ret += A[sz - 1];
}
while (k < arg.size()) {
ret += arg[k++];
}
return ret;
}
};
二、神奇数
题目描述
给定区间 [l, r]，统计其中'神奇数'的个数。如果一个数的任意两位组成的两位数（如 12, 21）是质数，则该数为神奇数。
思路分析
暴力枚举即可。遍历区间内每个数，提取每一位数字，两两组合成两位数，判断是否为质数。
判断质数优化：
- 小于 2 不是质数。
- 只需遍历到
sqrt(x)即可。
代码实现
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0) return false;
}
return true;
}
int check(int n) {
vector<int> num;
while (n) {
num.push_back(n % 10);
n /= 10;
}
for (int i = 0; i < num.size(); i++) {
for (int j = 0; j < num.size(); j++) {
if (i != j && num[i] != 0) {
if (isPrime(num[i] * 10 + num[j])) return 1;
}
}
}
return 0;
}
int main() {
int l, r;
cin >> l >> r;
int ret = 0;
for (int i = max(10, l); i <= r; i++) {
ret += check(i);
}
cout << ret << endl;
return 0;
}
三、DNA 序列
题目描述
给定由 A/C/G/T 组成的字符串 str 和整数 n。找出长度为 n 的子串，使得该子串中 C 和 G 的数量尽可能多，输出该子串。
思路分析
典型的滑动窗口问题。维护一个长度为 n 的窗口，统计窗口内 C/G 的个数，记录最大值对应的起始位置。
关键点：
- 使用
count记录当前窗口内目标字符数量。 - 当窗口大小超过
n时，左指针右移并更新count。 - 每次移动后比较
maxcount，更新最优解。
代码实现
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
int n;
cin >> str >> n;
int begin = -1, count = 0, maxcount = 0;
for (int left = 0, right = 0; right < str.size(); right++) {
if (str[right] == 'C' || str[right] == 'G') {
count++;
}
while (right - left + 1 > n) {
if (str[left] == 'C' || str[left] == 'G') {
count--;
}
left++;
}
if (count > maxcount) {
begin = left;
maxcount = count;
}
}
if (begin != -1)
cout << str.substr(begin, n) << endl;
return 0;
}
以上三道题涵盖了常见的面试考点，建议动手敲几遍加深理解。