C++ 笔试刷题 Day 16：字符串替换、神奇数及 DNA 序列

二、神奇数

题目描述

给定区间 [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;
}

以上三道题涵盖了常见的面试考点，建议动手敲几遍加深理解。