1.字符串替换
代码：
#define _CRT_SECURE_NO_WARNINGS 1 class Solution { public: string formatString(string str, vector<char>& arg) { string ans = ""; int pos = 0; for (int i = 0; i < str.size(); i++) { if (i != str.size() - 1 && str[i] == '%' && str[i + 1] == 's') { ans += arg[pos++]; i++; } else { ans += str[i]; } } // cout<<ans<<endl; while (pos < arg.size()) { ans += arg[pos++]; } return ans; } };
2.神奇数
思路：
暴力呗。枚举区间的每一个数字，并枚举这个数字的每俩个数位的组合，并判断是不是质数就OK了。时间复杂度为1e5*25*log(100)，大概就是在1e7的级别。也可以用一个质数筛提前把100以内的质数筛出来，时间复杂度就在1e6的级别。都差不多。
代码：
#include <iostream> #include<vector> using namespace std; const int N = 110; int prim[N]; int st[N]; int cnt = 0; void getprim() { st[1] = true; for (int i = 2; i < N; i++) { if (!st[i])prim[cnt++] = i; for (int j = 0; i < N / prim[j]; j++) { st[prim[j] * i] = true; if (i % prim[j] == 0)break; } } } int main() { int a, b; cin >> a >> b; int ans = 0; getprim(); for (int i = a; i <= b; i++) { vector<int> res; int k = i; while (k) { res.push_back(k % 10); k /= 10; } int f = 0; for (int j = 0; j < res.size(); j++) { if (f == 1)break; for (int k = 0; k < res.size(); k++) { if (j == k || res[j] == 0)continue; if (!st[res[j] * 10 + res[k]]) { f = 1; break; } } } if (f == 1) { // cout<<i<<endl; ans++; } } cout << ans << endl; }
3.DNA序列
又是一个题意都说不明白的题。最小子序列长度，到底是子串还是子序列啊。既然是定值为啥还要说最小啊，服了。
这题就不用算比例，因为长度是固定的，直接比较cg数量就好了.
#include <iostream> #include<string> #include<algorithm> using namespace std; const int N = 1100; int c[N]; int g[N]; int main() { string str; int ll; cin >> str >> ll; str.insert(str.begin(), '0'); int n = str.size(); for (int i = 1; i <= n; i++) { c[i] = c[i - 1] + (str[i] == 'C' ? 1 : 0); g[i] = g[i - 1] + (str[i] == 'G' ? 1 : 0); } string ans = ""; int res = 0; int len = ll; for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; int s = c[r] - c[l - 1] + g[r] - g[l - 1]; if (res < s) { ans = str.substr(l, len); res = s; } } cout << ans << endl; return 0; }
