【C++】刷题强训(day16)--字符串替换、神奇数、DNA序列
目录
1、字符串替换
1.1 题目
1.2 思路
1.3 代码实现
编辑
2、神奇数
2.1 题目
2.2 思路
2.3 代码实现
3、 DNA序列
3.1 题目
3.2 思路
刷题汇总：传送门！
1、字符串替换
1.1 题目
1.2 思路
读完题，知道让实现将字符数组中的字符元素将对字符串中占位符的进行替换，其中如果数组有剩余就尾插到最后返回替换后的字符串即可。
那么，根据示例和题目要求分析，既然占位符是固定格式，就看成整体，直接遍历字符串，遇见’%'先不做处理，遇见’s’再执行替换处理，占位符替换完后，再看字符数组是否为空，不为空就直接尾插到需要返回的字符串即可。那么，接下来就是代码实现。
1.3 代码实现
class StringFormat {
public:
string formatString(string A, int n, vector<char> arg, int m)
{
string str;
int j = 0;
for(int i=0;i < n;i++)
{
if( i+1 < n && A[i] == '%' && A[i+1]=='s')
{
str+= arg[j++];
m--;i++;
}
else
str += A[i];
}
while(m--)
str += arg[j++];
return str;
}
};
2、神奇数
2.1 题目
2.2 思路
读完题，知道给出一个区间[a, b]，计算区间内“神奇数”的个数。其中，神奇数表示该数只要存在任意不同位置的两个数位，组成一个两位数是质数，那么满足神奇数。
注意题目中说明不能计入前导0的情况，即103，取十位和个位出现03则不能计入这样的情况。那么，基本思路就是遍历区间，判断是否满足神奇书，其中要对遍历的数字进行位数转换再组合以及判断前导0的处理和判断是否是质数。
2.3 代码实现
#include <iostream>
#include<vector>
#include<math.h>
using namespace std;
bool isspmir(int x)
{
if(x < 2) return false;
for(int i = 2;i <= sqrt(x);i++)
{
if( x % i == 0)
return false;
}
return true;
}
bool check(int x)
{
vector<int> nums;
while(x)
{
nums.push_back(x % 10);
x /= 10;
}
for(int i = 0;i < nums.size();i++)
{
for(int j = 0;j < nums.size();j++)
{
if(i != j && nums[i]!=0)
if(isspmir(nums[i]*10 + nums[j]))
return true;
}
}
return false;
}
int main()
{
int a, b;
cin >> a >> b;
int ret = 0;
for(int i = max(a,10);i <=b;i++)
{
if(check(i))
ret++;
}
cout << ret << endl;
return 0;
}
3、 DNA序列
3.1 题目
3.2 思路
读完题，知道需要处理一个由A/C/G/T组成的DNA序列，然后求其GC比例最高且长度为N的第一个子串并输出。这里比例最高就是出现的次数最多，也就是输出子串C和G次数最多的连续的子串即可。那么，可以蛮力法利用双指针left和right遍历，统计C和G的个数count，每一次遍历的长度到输入的长度n时，就比较依次count的最大值，然后将lef指针向后移动一位，right指针也返回left,count也清0重新计数，以此循环遍历所有结果得到的最大值count的子串就是需要输出的子串。
不难发现，这样会导致很多重复的无用功，也发现两个指针的移动方向一致，且保持着固定的长度n，进行更新指针位置，那么就想到了滑动窗口的思路。所以这里相较之下使用滑动窗口优化。
那么滑动窗口的基本步骤：
(1)、进窗口：这里遇见C或G就进窗口；
(2)、判断窗口：当窗口大于输入的长度n时就移动窗口；
(3)、出窗口：移动窗口时，如果左指针是C或G就出窗口；
(4)、更新结果：更新记录的数量count表示每一组窗口中最大或最高比例的C/G;
接下来就是代码程序实现。
3.3 代码实现
#include <iostream>
using namespace std;
int main()
{
string s;
int n;
cin >>s >> n;
int begin = -1;//标记结果的其实位置
int count = 0;//统计 c 和 g个数
int maxcount = 0;//存储之前窗口中C+G 的个数
int left = 0,right = 0, l = s.size();
while(right < l)
{
if(s[right] == 'C' || s[right] == 'G')
count++;
while(right - left + 1 > n)
{
if(s[left] == 'C' || s[left] == 'G' )
count--;
left++;
}
if(right - left + 1 == n)
{
if(count > maxcount)
{
maxcount = count;
begin = left;
}
}
right++;
}
cout << s.substr(begin,n) << endl;
return 0;
}
本篇完，下篇见 ！
