题目描述
有一条彩色宝石项链，是由很多种不同的宝石组成的，包括红宝石，蓝宝石，钻石，翡翠，珍珠等。有一天国王把项链赏赐给了一个学者，并跟他说，你可以带走这条项链，但是王后很喜欢红宝石，蓝宝石，紫水晶，翡翠和钻石这五种，我要你从项链中截取连续的一小段还给我，这一段中必须包含所有的这五种宝石，剩下的部分你可以带走。如果无法找到则一个也无法带走。请帮助学者找出如何切分项链才能够拿到最多的宝石。
输入描述:
我们用每种字符代表一种宝石，A表示红宝石，B表示蓝宝石，C代表紫水晶，D代表翡翠，E代表钻石，F代表玉石，G代表玻璃等等，我们用一个全部为大写字母的字符序列表示项链的宝石序列，注意项链是首尾相接的。每行代表一种情况。
输出描述:
输出学者能够拿到的最多的宝石数量。每行一个
思路：
直接暴力求解。比如：ABFGHEDC宝石串，首先从字母A开始向后遍历，当他找到一个串包含ABCDE时,该串是‘ ABFGHEDC’。继续遍历下一个字母B，.... 当遍历到字母E并找到整个ABCDE时发现，该串是'EDCAB'，显然该串最短，可以获得的宝石最长。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Stone {private static HashSet<Character> set = new HashSet<Character>();static {set.add('A');set.add('B');set.add('C');set.add('D');set.add('E');}//A B C D E 是王后需要的public static void main(String[] args) {Scanner scn = new Scanner(System.in);while(scn.hasNext()) {String string = scn.nextLine();System.out.println(processString(string));}scn.close();}public static void Main() {System.out.println("Hello World");}@SuppressWarnings("unchecked")private static int processString(String string) {int[] length = new int[string.length()];int startIndex;int endIndex;for(int i= 0;i<string.length();i++) {//遍历字符串中的每一个字符//为每个字符新创建一个包含ABCDE的Set集合。然后从该字符开始向后遍历,每发现Set集合中的元素,就将其从集合中移除//当遍历结束后,若Set为空,说明可以满足条件,startIndex和endIndex分别记录起始位置,用于计算包含ABCDE片段的长度//每个字符都有可能会对应一个长度,将这个长度存储在lengt[]数组中,最终取得一个最大值 返回即可Set<Character> stoneSet = (Set<Character>) set.clone();startIndex = -1;endIndex = -1;if(stoneSet.contains(string.charAt(i))) {//如果当前字符串是ABCDE中的一个stoneSet.remove(string.charAt(i));startIndex = i;for(int j = i; j<i+string.length();j++) {//那么把这个字符串看做一个环形的,从当前位置遍历,直到当前位置的前一个字母if(stoneSet.contains(string.charAt(j%string.length()))) {stoneSet.remove(string.charAt(j%string.length()));if(stoneSet.size()==0) {endIndex = j;break;}}}if(endIndex!=-1){endIndex = endIndex>startIndex?endIndex:endIndex+string.length();length[i] = string.length()-(endIndex-startIndex+1);//计算可以获得宝石串的长度}}}int maxLen = length[0];for(int i=0;i<length.length;i++) {if(maxLen<length[i])maxLen = length[i];}return maxLen;}
}
