首页 > 试题广场 >

宝石手串

[编程题]宝石手串

热度指数：8509 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小红有一个 $n$ 颗宝石构成的环形宝石手串，即第一颗和最后一颗宝石相连，其中第 $i$ 个宝石的属性为 $s_i$ ；若两个宝石的属性相同，那么这两个宝石会相互排斥，导致断开。
$\hspace{15pt}$ 小红可以从手串中摘掉一些宝石，每次摘掉后，这个宝石左右的两个宝石会相接，手串依旧是环形。

$\hspace{15pt}$ 小红想要破坏这个手串。她想要知道，最少还需要摘掉多少个宝石才会导致手串断开。特别的，当手串上剩余的宝石数量恰好为 $2$ 而依旧没能断开时，视为破坏失败，直接输出 $-1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  代表手串初始的宝石数量。
第二行输入一个长度为  、仅由小写字母构成的字符串，代表手串上每个宝石的属性。

除此之外，保证单个测试文件的  之和不超过  。

输出描述:

对于每一组测试数据，如果手环无法破坏，直接输出  ；否则，在一行上输出一个整数，代表手串断开需要的最少操作次数。

示例1

输入

2
2
ac
3
aac

输出

-1
0

算法知识视频讲解

Python3

不想泡池子的马后炮炮手在看机会

N = int(input())
while 1:
    try:
        n = int(input())
        ls = list(input())
        count = n
        code = {}
        for i in range(n):
            if ls[i] in code:
                code[ls[i]].append(i)
            else:
                code[ls[i]] = []
                code[ls[i]].append(i)
        psbls = []
        for x in code.items():
            if len(x[1])>1:
                psbls.append(x[0])
        if len(psbls) == 0:
            print(-1)
        else:
            for x in psbls:
                for i in range(len(code[x])-1):
                    if (code[x][i+1] - code[x][i]-1)<count:
                        count = code[x][i+1] - code[x][i]-1
                if (n - code[x][-1] + code[x][0] - 1)<count:
                    count = n - code[x][-1] + code[x][0] - 1
            print(count)

    except:
        break

发表于 2025-10-09 13:06:40 回复(0)

Python3

牛客744375192号

m=int(input())
for _ in range(m):
    n=int(input())
    m=input()
    if n==2 and m[0]!=m[1]:
        print(-1)
    else:
        last={}
        for j,k in enumerate(m):#abcdajlc
            if k not in last:
                last[k]=j
            else:
                print(j-last[k]-1)

发表于 2025-09-08 13:22:48 回复(0)

Python3

笨笨向前冲

def compute(n,s):
    my_dict = {}
    # value是三元组 首位置 上一个位置 最小距离
    for i in range(n):
        a = s[i]
        if a in my_dict:        
            my_dict[a][2] = min(my_dict[a][2],min(i-my_dict[a][1]-1,my_dict[a][0]+n-1-i))
            my_dict[a][1] = i
        else:
            my_dict[a] = [i,i,n+1]

    ans = min([value[-1] for value in my_dict.values()])
    return ans if ans<n else -1


T = int(input())
for i in range(T):
    n = int(input())
    s = str(input())
    print(compute(n,s))

发表于 2025-07-09 20:52:19 回复(0)

Python3

忧伤的双曲线

T = int(input())

for i in range(T):

n = int(input())

s = input()

ss = s+s

if len(s)==len(set(s)):

print(-1)

else:

flag = False

for j in range(1,len(s)+1):

for k in range(len(s)):

if ss[k]==ss[k+j]:

print(j-1)

flag = True

break

if flag:

break

发表于 2025-03-19 23:35:44 回复(0)

Python3

牛客388550911号

求相同字符的最短间隔, 可以遍历, 维护一个字典, 键是字符, 值分别记录当前字符的下标和最短距离的最小值

发表于 2025-03-06 23:40:52 回复(0)

Python3

在拧螺丝的他很有趣

T = int(input())

i = 0

# 判断最少需要断开多少次

def get_num(lst, n):

dic = []

for i in range(len(lst)):

if i < len(lst)-1:

dic.append(lst[i+1] - lst[i] -1)

else:

dic.append(n-lst[i]-1+lst[0])

return min(dic)

# 判断断开需要多少次操作

def num(s):

my_dict = {}

for i in s:

if i not in my_dict.keys():

my_dict[i] = 1

else:

my_dict[i] += 1

if len(my_dict.keys()) == len(s):

return -1

else:

p = len(s)+1

for i in my_dict.keys():

if my_dict[i] > 1:

l = [] # 记录坐标

for j in range(len(s)):

if s[j] == i:

l.append(j)

q = get_num(l, len(s))

if p > q:

p = q

return p

while i<T:

i += 1

n = int(input())

s = input()

print(num(s))

发表于 2025-03-05 11:52:23 回复(0)

提交观点

问题信息

哈希

难度：

7条回答 181收藏 694浏览

宝石手串

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题