C. K-Dominant Character
题意:给你一个字符串,要求你找出最小的包含相同字母的字串,并输出它的长度k
分析:orz! 这个题从昨晚卡到了今天。。。WA了7发。。。
这个题是个模拟题目,思路大概就是:找出每一种字符之间的距离最大值,放到一个数组里,然后对数组排序,找出最大值们中的最小值,就是答案。
注意:
1、如果每个字符都不同且为1个,就直接输出中间字符
2、除了要求字符之间最大值,还要求每种字符到第一个位置长度以及每种字符到末尾的长度
代码如下:
#include<iostream>
#include<string>
#include<string.h>
#include<cstring>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 2000;
string s;
int vis[maxn];
bool flag[maxn];
bool cmp(int x, int y) {
return x > y;
}
int main()
{
ios::sync_with_stdio(false);
cin >> s;
memset(vis, 0, sizeof(vis));
memset(flag, 0, sizeof(flag));
int n = s.size();
for (int i = 0; i < n; i++) {
vis[s[i] - 'a']++;//记录每种字符个数
}
bool Flag = 0;
for (int i = 0; i < n; i++) {
if (vis[s[i]-'a'] > 1) {
Flag = 1;
break;
}
}
if (Flag == 0) {//如果每个字符都不一样,找最中间的字符
cout << n / 2 + 1 << endl;
return 0;
}
int dis[100];
memset(dis, 0, sizeof(dis));
int len = 0;
for (int i = 0; i < n; i++) {
if (flag[s[i]-'a'])continue;
len = -1; //每次让初始位置为0
flag[s[i]-'a'] = 1; //如果能往下走,给这种字符赋值为1
for (int j = 0; j < n; j++) {
if (s[i] == s[j]) {
dis[s[i]-'a'] = max(dis[s[i]-'a'], j - len);
len = j;
}
}
dis[s[i]-'a'] = max(dis[s[i]-'a'], n - len);//最后一个位置
}
sort(dis, dis + 100,cmp);
for (int i = 0; i < 100; i++) {
if (dis[i] && dis[i + 1] == 0) {
cout << dis[i] << endl;
return 0;
}
}
return 0;
}