生活随笔
收集整理的這篇文章主要介紹了
9.10 中国电信it研发中心 笔试编程题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
A
題意: 假設字符串中出現次數最少的字母是x, 出現次數為y, 刪除所有出現次數為y的字符
思路: 統計一下字符的出現次數, 然后照著做就行
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <cstdio>
#include <sstream>
#include <cctype>#define LL long long
#define mst(a, b) memset(a, b, sizeof(a))
#define pill pait<int, int>
#define ft first
#define sd secondusing namespace std;
const int qq =
3e5 +
10;
const int MOD =
1e9 +
7;
const int INF =
1e9 +
10;
int vis[
300];
char s[qq];
int main() {
string x;
cin >> x;
int minx = INF;
for (
int i =
0; i < x.size(); ++i) {vis[x[i]]++;}
string ans =
"";
for (
int i =
0; i < x.size(); ++i) {
if (vis[x[i]] >
0) minx = min(minx, vis[x[i]]);}
for (
int i =
0; i < x.size(); ++i) {
if (minx == vis[x[i]])
continue;ans += x[i];}
cout << ans << endl;
return 0;
}
B
題意: 求第n個丑數
思路: leetcode原題, 可以去leetcode找一找
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <cstdio>
#include <sstream>
#include <cctype>#define LL long long
#define mst(a, b) memset(a, b, sizeof(a))
#define pill pait<int, int>
#define ft first
#define sd secondusing namespace std;
const int qq =
3e5 +
10;
const int MOD =
1e9 +
7;
const int INF =
1e9 +
10;
int n;
int num[qq];
void init() {num[
0] =
1;
int a, b, c;a = b = c =
0;
int top =
0;
for (
int i =
1; top <=
1500; ++i) {
int x = num[a] *
2;
int y = num[b] *
3;
int z = num[c] *
5;
if (x <= y && x <= z) {num[++top] = x, a++;}
else if (y <= x && y <= z) {num[++top] = y, b++;}
else {num[++top] = z, c++;}
while (num[a] *
2 <= num[top]) a++;
while (num[b] *
3 <= num[top]) b++;
while (num[c] *
5 <= num[top]) c++;}
}
int main() {init();
scanf(
"%d", &n);
printf(
"%d\n", num[n -
1]);
return 0;
}
C
題意: 求兩個串前后重疊部分的最大長度
思路: 最初我是采用這種暴力計算的方法, 可以ac
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <cstdio>
#include <sstream>
#include <cctype>#define LL long long
#define mst(a, b) memset(a, b, sizeof(a))
#define pill pait<int, int>
#define ft first
#define sd secondusing namespace std;
const int qq =
3e5 +
10;
const int MOD =
1e9 +
7;
const int INF =
1e9 +
10;
string x, y;
int main() {
std::ios::sync_with_stdio(
false);
cin >> x >> y;
int maxn =
0;
for (
int i = x.size() -
1; i >=
0; --i) {
int start = i, len =
0;
for (
int j =
0; j < y.size() && start < x.size(); ++j) {
if (x[start] == y[j]) {start++, len++;}
else {
break;}}maxn = max(maxn, len);}
for (
int i = y.size() -
1; i >=
0; --i) {
int start = i, len =
0;
for (
int j =
0; j < x.size() && start < y.size(); ++j) {
if (y[start] == x[j]) {start++, len++;}
else {
break;}}maxn = max(maxn, len);}
cout << maxn << endl;
return 0;
}
之后想了想發現其實就是個kmp問題, 跑兩次kmp即可 時間復雜度O(n)
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <cstdio>
#include <sstream>
#include <cctype>#define LL long long
#define mst(a, b) memset(a, b, sizeof(a))
#define pill pait<int, int>
#define ft first
#define sd secondusing namespace std;
const int qq =
3e5 +
10;
const int MOD =
1e9 +
7;
const int INF =
1e9 +
10;
string x, y;
int nt[qq];
void getNext(
string f) {
int i =
0, j = -
1;nt[
0] = -
1;
int len = f.size();
while (i < len) {
if (j == -
1 || f[i] == f[j]) {nt[++i] = ++j;}
else {j = nt[j];}}
}
int getMaxn(
string x,
string y) {
int i =
0, j =
0;
int len = x.size();
while (i < len) {
if (j == -
1 || x[i] == y[j]) {i++, j++;}
else {j = nt[j];}}
return j;
}
int main() {
std::ios::sync_with_stdio(
false);
cin >> x >> y;getNext(x);
int maxn = getMaxn(y, x);getNext(y);maxn = max(maxn, getMaxn(x, y));
cout << maxn << endl;
return 0;
}
總結
以上是生活随笔為你收集整理的9.10 中国电信it研发中心 笔试编程题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
