题解 | 宝石手串

宝石手串

https://www.nowcoder.com/practice/9648c918da794be28575dd121efa1c50

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <climits>

using namespace std;

int main() {
    int T;
    cin >> T;
    cin.ignore(100, '\n'); // 清空输入缓冲区
    // cout << "T==" << T << endl;
    while (T--) {
        int n; cin>>n;
        cin.ignore(100, '\n'); // 清空输入缓冲区
        // cout << "n==" << n << endl;
        string s; cin>>s;
        cin.ignore(100, '\n'); // 清空输入缓冲区
        // cout << "string==" << s <<endl;
        int ans=-1;
        if (n==2 && s[0]!=s[1]) {
            cout << ans << endl;
            continue;
        }
        for (int i=0; i<n-1; i++) {
            if (i==0 && s[i]==s[n-1])   {ans=0; break;}
            if (s[i]==s[i+1])   {ans=0; break;}
        }
        if (ans==0)   {cout<<0<<endl; continue;}
        // 记录每个属性都有在哪些位置上
        unordered_map<char, vector<int>> positions;
        for (int i=0; i<n; i++) {
            positions[s[i]].emplace_back(i);
        }
        // 计算每个属性不同位置之间的间距
        int min_val = INT_MAX;
        // cout << "position的size=="<<positions.size()<<endl;
        for (auto it=positions.begin(); it!=positions.end(); it++) {
            // cout << "当前position.vector的size=="<<it->second.size()<<endl;
            if ((it->second).size()==1)     {continue;}
            vector<int> temp=it->second, dis;
            for (int i=0; i<it->second.size(); i++) {
                int dis_i;
                if (i==it->second.size()-1) {
                    // cout << "n==" << n << ", temp[0]==" << temp[0] << ", temp[" << i << "]==" << temp[i] << endl;
                    dis_i = (n + temp[0]) - temp[i] - 1;
                }
                else  dis_i = temp[i+1] - temp[i] - 1;
                // cout << "dis_i==" <<dis_i<<endl;
                min_val = min(min_val, dis_i);
                dis.emplace_back(dis_i);
            }
        }
        if (min_val == INT_MAX)  {
            cout << -1 << endl; continue;
        } else {
            // cout<<"min_val==";
            cout<<min_val<<endl; continue;
        }
    }
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务