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

刷题_day16，继续加油啊

一、字符串替换

题目解析

这道题是一道简单的字符题目，题目给我们一个字符串 A，和 n 表示 A 字符串的长度，再给出一个字符数组 arg，m 表示 arg 中是数据个数。

然我们在字符串 A 中找到 %s 然后替换成 arg 中的字符；

算法分析

这道题就非常简单简单了，我们直接在 A 中寻找 %s，然后将 arg 中的字符替换即可。

当然这里没有必要在原字符串中进行操作，创建一个新的字符串 ret 即可。

这里需要注意：

A 字符串中的 %s 的个数可能会小于 arg 中的字符数量，

代码实现

class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        // write code here
        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++;
            }
        }
        if (A[sz - 2] != '%') ret += A[sz - 1];
        while (k < arg.size()) ret += arg[k++];
        return ret;
    }
};

二、神奇数

题目解析

这道题，给定我们一个区间 [l , r]，让我们找出来其中神奇数的个数；

**神奇数：**对于一个数 x，使用它的某两位组成的一个两位数是一个质数，那这个数就是神奇数。

算法分析

对于这道题，思路就简单明了了，你就是暴力枚；枚举出来所有可能的两位数，判断是否是质数即可。

遍历区间 [l , r]，判断是否是神奇数，是就计数加一；

判断是否是神奇数：先将数的每一位存到一个数组中，然后枚举所有可能的两位数，判断这两位数是否是质数；如果是，这个数就是神奇数；如果不是，那就继续枚举，直到枚举完所有的。（枚举完所有的就表示这个数不是神奇数）

判断是否是质数：（首先进行一下判断，如果 x<2，这个数就不是质数）从 2 开始判断 x 是否能被整除，如果能那就不是质数，如果不能就继续遍历；遍历到 sqrt(x) 时遍历结束；（遍历到 sqrt(x) 就表示这个数是质数）。

代码实现

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool isprim(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) {
    // 将 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 (isprim(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 序列

题目解析

这里题目给我们应该字符串 str，其中有 A/C/G/T 组成；还给了一个 n；

让我们在 str 中找到一个子串，这个子串长度为 n，要求我们这个子串中有尽可能多的 C/G。

最后要我们输出这个子串（子串中 C/G 尽可能多）。

算法分析

这道题，相信对题目比较敏感的朋友已经想到了做法，那就是 滑动窗口。

这里就不过多叙述了，直接来看思路：

这里呢，我们要找尽可能多数量的 C/G，我们就需要一个 count 来记录区间 [left , right] 在 C/G 的个数；然后用 maxcount；来记录当前最多的 C/G 的数量，用于比较；

题目要求我们最后输出子串，所以我们记录一下最后子串的起始位置 begin 和长度 len。进窗口：如果 A[right] == 'C' || A[right] == G，count++；判断：如果 right - left - 1 > n，就表示当前区间长度大于 n 了，就要出窗口操作；出窗口：如果 A[left] == 'C' || A[right] == 'G'，就 count--；更新结果：出窗口操作之后，如果区间长度等于 n，并且当前区间内 count 小于 maxcount，那就更新结果。

代码实现

#include <iostream>
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;
        }
    }
    cout << str.substr(begin, n) << endl;
    return 0;
}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws