【C++】 —— 笔试刷题day_16
刷题_day16，继续加油啊
一、字符串替换
题目解析
这道题是一道简单的字符题目，题目给我们一个字符串A，和n表示A字符串的长度，再给出一个字符数组arg，m表示arg中是数据个数。
然我们在字符串A中找到%s然后替换成arg中的字符；
算法分析
这道题就非常简单简单了，我们直接在A中寻找%s，然后将arg中的字符替换即可。
当然这里没有必要在原字符串中进行操作，创建一个新的字符串ret即可。
这里需要注意：A字符串中的%s的个数可能会小于arg中的字符数量，
代码实现
classStringFormat{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>usingnamespace std;boolisprim(int x){if(x<2)returnfalse;for(int i =2;i<=sqrt(x);i++){if(x % i ==0)returnfalse;}returntrue;}intcheck(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]))return1;}}return0;}intmain(){int l,r; cin>>l>>r;int ret =0;for(int i =max(10,l);i<=r;i++){ ret+=check(i);} cout<<ret<<endl;return0;}三、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>usingnamespace std;intmain(){ 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;return0;}到这里本篇文章就结束了，继续加油
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
