原题链接:登录—专业IT笔试面试备考平台_牛客网
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述
2. 思路分析
前缀和。
开一个int类型的前缀和数组pre[30][N](pre[i][j]表示某字符转成的数字 i 在一段区间的前缀个数。因为字母表有‘a’~'z'共26个字母,所以数组的一维至少开26,一般会多开一些,这里我开了30)。
读入字符串s,遍历字符串s(因为是前缀和的题目,所以下标要从1开始),我们将字符串s(string默认下标是从0开始的,所以之后是s[i-1])中的字符转成数字('a'转成1,'b’转成2,...'z'转成26)。 之后从1~26遍历 j(其实就是在遍历字符‘a’~'z'共26个字符),如果当前字符和上一个字符相同(即j==tmp),我们就让前缀和+1,即pre[j][i]=pre[j][i-1]+1;否则pre[j][i]=pre[j][i-1]。
因为n最大是5000。O(N^2)的复杂度不会超时,所以我们可以通过跑两重循环(外层循环枚举左端点,内层循环枚举右端点)来枚举左右区间 l,r 。再从1~26遍历k(还是从'a'遍历到‘z’),开一个变量tmp记录此时的pre[k][r]-pre[k][l-1](也就是字符k对应的数字在 l~r区间的个数),再通过tmp*(tmp-1) 算相同字符对数,并累加到cnt。不断更新ans的值,取max(ans,1.0*cnt/(r-l+1))即可。
因为是多组测试数据,所以每次循环结束要将pre[i][j]这个二维数组置空。
3. 代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5010;
int pre[30][N]; void solve(){int n; cin>>n;string s; cin>>s;for(int i=1;i<=n;i++){ //前缀和处理出26个字母的前缀和的数量;int tmp=s[i-1]-'a'+1; //字符串下标从0开始for(int j=1;j<=26;j++){ //判断当前枚举的字母是否和上一个字母相同if(j==tmp) pre[j][i]=pre[j][i-1]+1;else pre[j][i]=pre[j][i-1];}}double ans=0;for(int i=1;i<=n;i++){ //枚举每个区间,然后枚举每个字母,计算贡献。for(int j=i+1;j<=n;j++){int l=i,r=j;int cnt=0;for(int k=1;k<=26;k++){int tmp=pre[k][r]-pre[k][l-1];cnt+=tmp*(tmp-1)/2;}ans=max(ans,1.0*cnt/(r-l+1));}}cout<<fixed<<setprecision(6)<<ans<<endl;for(int i=1;i<=26;i++) //多组测试数据,所以每次循环结束将二维数组置空for(int j=1;j<=n;j++)pre[i][j]=0;
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin>>T;while(T--){solve();} return 0;
}