本文主要是介绍Python3编程练习-彩色宝石项链,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
有一条彩色宝石项链,是由很多种不同的宝石组成的,包括红宝石,蓝宝石,钻石,翡翠,珍珠等。有一天国王把项链赏赐给了一个学者,并跟他说,你可以带走这条项链,但是王后很喜欢红宝石,蓝宝石,紫水晶,翡翠和钻石这五种,我要你从项链中截取连续的一小段还给我,这一段中必须包含所有的这五种宝石,剩下的部分你可以带走。如果无法找到则一个也无法带走。请帮助学者找出如何切分项链才能够拿到最多的宝石。
输入描述:
我们用每种字符代表一种宝石,A表示红宝石,B表示蓝宝石,C代表紫水晶,D代表翡翠,E代表钻石,F代表玉石,G代表玻璃等等,我们用一个全部为大写字母的字符序列表示项链的宝石序列,注意项链是首尾相接的。每行代表一种情况。
输出描述:
输出学者能够拿到的最多的宝石数量。每行一个
思路:
右指针一直往后移动,直到左右指针之间包含了ABCDE 5个字母之后,更新长度,然后左指针一直往右移动,直到左右指针之间不完全包含ABCDE,之后右指针又开始像右移动,重复这个过程直到右指针到了字符串的右边界为止。
def minstr(s):s=s+sslist=[]for i in s:slist.append(i)left=0;right=5minc=float('inf')while right<=len(slist):if set('ABCDE').issubset(set(slist[left:right])):prec=right-leftminc=min(minc,prec)left+=1else:right+=1return int(len(slist)/2-minc)
import sys
L= sys.stdin.readlines()
for s in L:s=s.strip('\n')print(minstr(s))
这篇关于Python3编程练习-彩色宝石项链的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!