【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 代码实现

1. class StringFormat {
2. public:
3.     string formatString(string A, int n, vector<char> arg, int m)
4.     {
5.         string str;
6.         int j = 0;
7.         for(int i=0;i < n;i++)
8.         {
9.             if( i+1 < n && A[i] == '%' && A[i+1]=='s')
10.             {
11.                 str+= arg[j++];
12.                 m--;i++;
13.             }
14.             else
15.                 str += A[i];
16.         }
17.         while(m--)
18.             str += arg[j++];
19.         return str;
20.     }
21. };

复制代码

2、神奇数

2.1 标题

2.2 思路

读完题，知道给出一个区间[a, b]，计算区间内“神奇数”的个数。其中，神奇数体现该数只要存在恣意不同位置的两个数位，组成一个两位数是质数，那么满意神奇数。
注意标题中阐明不能计入前导0的环境，即103，取十位和个位出现03则不能计入这样的环境。那么，根本思路就是遍历区间，判断是否满意神奇书，其中要对遍历的数字举行位数转换再组合以及判断前导0的处置惩罚和判断是否是质数。
2.3 代码实现

1. #include <iostream>
2. #include<vector>
3. #include<math.h>
4. using namespace std;
6. bool isspmir(int x)
7. {
8.     if(x < 2) return false;
9.     for(int i = 2;i <= sqrt(x);i++)
10.     {
11.         if( x % i == 0)
12.             return false;
13.     }
14.     return true;
15. }
17. bool check(int x)
18. {
19.     vector<int> nums;
20.     while(x)
21.     {
22.         nums.push_back(x % 10);
23.         x /= 10;
24.     }
26.     for(int i = 0;i < nums.size();i++)
27.     {
28.         for(int j = 0;j < nums.size();j++)
29.         {
30.             if(i != j && nums[i]!=0)
31.                 if(isspmir(nums[i]*10 + nums[j]))
32.                     return true;
33.         }
34.     }
35.     return false;
36. }
38. int main()
39. {
40.     int a, b;
41.     cin >> a >> b;
42.     int ret = 0;
43.     for(int i = max(a,10);i <=b;i++)
44.     {
45.         if(check(i))
46.             ret++;
47.     }   
48.     cout << ret << endl;
49.     return 0;
50. }

复制代码

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 代码实现

1. #include <iostream>
2. using namespace std;
4. int main()
5. {
6.     string s;
7.     int n;
8.     cin >>s >> n;
10.     int begin  = -1;//标记结果的其实位置
11.     int count = 0;//统计 c 和 g个数
12.     int maxcount = 0;//存储之前窗口中C+G 的个数
13.     int left = 0,right = 0, l  = s.size();
14.     while(right < l)
15.     {
16.         if(s[right] == 'C' || s[right] == 'G')
17.             count++;
18.         while(right - left + 1 > n)
19.         {
20.             if(s[left] == 'C' || s[left] == 'G' )
21.                 count--;
22.              left++;
23.         }
24.         if(right - left + 1 == n)
25.         {
26.             if(count > maxcount)
27.             {
28.                 maxcount = count;
29.                 begin = left;
30.             }
31.         }
32.         right++;
33.     }
34.     cout << s.substr(begin,n) << endl;
35.     return 0;
36. }

复制代码

---

本篇完，下篇见 ！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。