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;
}