厦门百度整站优化服务,软件工程师月薪,做网站的动态图片,英德市城乡建设局网站题目描述:
有一条彩色宝石项链#xff0c;是由很多种不同的宝石组成的#xff0c;包括红宝石#xff0c;蓝宝石#xff0c;钻石#xff0c;翡翠#xff0c;珍珠等。有一天国王把项链赏赐给了一个学者#xff0c;并跟他说#xff0c;你可以带走这条项链#xff0c;但是…题目描述:
有一条彩色宝石项链是由很多种不同的宝石组成的包括红宝石蓝宝石钻石翡翠珍珠等。有一天国王把项链赏赐给了一个学者并跟他说你可以带走这条项链但是王后很喜欢红宝石蓝宝石紫水晶翡翠和钻石这五种我要你从项链中截取连续的一小段还给我这一段中必须包含所有的这五种宝石剩下的部分你可以带走。如果无法找到则一个也无法带走。请帮助学者找出如何切分项链才能够拿到最多的宝石。
输入描述:
我们用每种字符代表一种宝石A表示红宝石B表示蓝宝石C代表紫水晶D代表翡翠E代表钻石F代表玉石G代表玻璃等等我们用一个全部为大写字母的字符序列表示项链的宝石序列注意项链是首尾相接的。每行代表一种情况。
输出描述:
输出学者能够拿到的最多的宝石数量。每行一个
示例1:
输入
ABCYDYE
ATTMBQECPD
输出
1
3
解题思路
相当于构造一个动态的滑动窗口窗口的大小依次递增最小为5最大为输入字符串的长度。然后用这个窗口依次从左向右框选字符每框选依次便进行依次判断如果符合题意就输出length-n退出程序。
#includeiostream
#includestring.h
using namespace std;bool In(string str,int n){int i,j;int count0;string sABCDE;for(i0;i5;i){for(j0;jn;j){if(s[i]str[j]){count;break;}}}if(count5)return true;elsereturn false;
}int main(){string str;string temp;int length;int n;int i;int k;cinstr;lengthstr.length();for(n5;nlength;n){for(i0;ilength;i){temp.clear();for(k0;kn;k){temp.append(1,str[(ik1)%length]);}if(In(temp,n)){coutlength-nendl;return 0;}}}
}
欢迎留言交流。。。
