首页 > 试题广场 >

宝石手串

[编程题]宝石手串
  • 热度指数：8509 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}小红有一个 n 颗宝石构成的环形宝石手串，即第一颗和最后一颗宝石相连，其中第 i 个宝石的属性为 s_i ；若两个宝石的属性相同，那么这两个宝石会相互排斥，导致断开。
\hspace{15pt}小红可以从手串中摘掉一些宝石，每次摘掉后，这个宝石左右的两个宝石会相接，手串依旧是环形。
\hspace{15pt}小红想要破坏这个手串。她想要知道，最少还需要摘掉多少个宝石才会导致手串断开。特别的，当手串上剩余的宝石数量恰好为 2 而依旧没能断开时，视为破坏失败，直接输出 -1 。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 100\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n \left( 2 \leqq n \leqq 10^5 \right) 代表手串初始的宝石数量。
\hspace{15pt}第二行输入一个长度为 n 、仅由小写字母构成的字符串，代表手串上每个宝石的属性。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 10^5 。


输出描述:
\hspace{15pt}对于每一组测试数据，如果手环无法破坏，直接输出 -1 ；否则，在一行上输出一个整数，代表手串断开需要的最少操作次数。
示例1

输入

2
2
ac
3
aac

输出

-1
0
算法知识视频讲解
添加回答
C
人生有三乐头像 人生有三乐
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    //思路：创建一个哈希表用来记录这个字符到下一个相同字符的最短距离就行了。可以
    //如果找到最后位置没有找到相同，则从字符串首尾相连的情况开始找。ok肯定能实现，看看大佬们又没更好的算法。

    int hash_count[26];  //-1表示这个字母没有出现或者没有另一个相同属性的宝石给他断
    //memset(hash_count, -1, sizeof(hash_count));
    int n;
    scanf("%d\n",&n);

    for(int i=1;i<=n;i++)
    {
        memset(hash_count, -1, sizeof(hash_count)); //每次使用都初始化
        int l;
        scanf("%d\n",&l);
        char* string=malloc(sizeof(char)*(l+1));
        scanf("%s",string);
       
        for(int j=0;string[j]!='\0';j++)
        {
            bool isfind=false;//如果找到末尾都没找到可能存在环形的路径
            for(int k=j+1;string[k]!='\0';k++)
            {
                if(string[j]==string[k]) //找到两个相同字符的距离
                {
                    isfind=true;  //找到了
                    if(hash_count[string[j]-'a']==-1) //没有出现过记录
                    {
                        hash_count[string[j]-'a']=k-j-1; //记录数据

                    }else {
                        if(k-j-1<hash_count[string[j]-'a'])  //当前的距离是否比旧的记录少
                        {
                            hash_count[string[j]-'a']=k-j-1; //记录更少数据
                        }
                    }
                    break;  //找到了就可以不用继续找了，应该是这个原因导致超时
                }
               
            }

            //没找到看看有没有环形路径
            if(isfind==false)
            {
                int mowei_l=l-1-j;//记录末尾的长度
                for(int s=0;s<j-1;s++)
                {
                    if(string[j]==string[s]) //找到从末尾开始的路径
                    {
                        if(hash_count[string[j]-'a']==-1) //没有出现过记录
                        {
                            hash_count[string[j]-'a']=mowei_l+s; //记录数据
                        }else {
                            if(mowei_l+s<hash_count[string[j]-'a'])  //当前的距离是否比旧的记录少
                            {
                                hash_count[string[j]-'a']=mowei_l+s; //记录更少数据
                            }
                        }
                        break;  //找到了就可以不用继续找了，应该是这个原因导致超时
                    }
                   
                }
            }
        }
        //输出结果找最小
        int min=l;  //默认最长就是l
        bool cunzai=false;//是否存在最小的路径
        for(int i=0; i<26;i++)
        {
            //printf("%c=%d\n",i+'a',hash_count[i]);
            if(hash_count[i]!=-1&&hash_count[i]<min)
            {
                cunzai=true;
                min=hash_count[i];
            }
        }

        if(cunzai==true)
        {
            printf("%d\n",min);
        }else {
            printf("%d\n",-1);
        }
    }
   
    return 0;
} 
 

                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2025-10-02 16:45:53
                                                    
                                                                                            
                                                回复(0)
                                                                                                                                            

                                        

                                


                                                            
                        

                        
                                        

                            

        


                    

                                    

                        

                            

                            

                                提交观点
                            

                        

                    

                            

            

    

          

            
问题信息

            

              

                                      哈希
                                

                                  

                
                                                            

                                        难度：

                                

                                        1条回答
                      
                      695浏览
                                

            

          


                        

  

    

      
      
      
    

    
热门推荐

  

  

    

      
    

  



            

                

            

          
            
                          

                
相关试题

                

                  
                

              

            
                            

                        宝石手串
                

                





                
        

                                                                

        

    
    
    

    


            
    
    

        

            

                
            

            
扫一扫，把题目装进口袋

        

        

            
求职之前，先上牛客

            

                
                    

                        

                        

                            
                            
扫描二维码，进入QQ群

                        

                    

                
                
                    

                        

                        

                            
                            
扫描二维码，关注牛客公众号