USACO考试题beads的两种解法

USACO试题beads的两种解法

package Karl.Water;

/*
LANG: JAVA
TASK: beads
*/


import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.LinkedList;

public class beads {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			BufferedReader br = new BufferedReader(new FileReader("beads.in"));
			PrintWriter pw = new PrintWriter (new FileWriter("beads.out"));
			
			int length = Integer.parseInt(br.readLine());
			String temp = br.readLine();
			LinkedList<Character> necklace = new LinkedList<Character>();
			for (int i=0;i<length;i++) {
				necklace.add(temp.charAt(i));
			}
			
			int max = 0;
			for (int i=0;i<length;i++) {
				char remove = necklace.removeFirst();
				char first = necklace.getFirst();
				int position = 0;
				necklace.addLast(remove);
				
				int result = 0;
				boolean allW = false;
				if (necklace.getFirst()=='w'){
					int end1 = find(necklace,0,length,0); 
					result = end1 + 1;
					if (end1<necklace.size()-1){
						int end2 = find (necklace,end1+1,length,0);
						first = necklace.get(end2);
						position = end2;
						result = result + end2 - end1;
					}else {
						allW = true;
					}
				} else {
					int end = find(necklace,0,length,0);
					position = end ;
					result = result + end + 1;
				}
				if (!allW){
					if (necklace.getLast()=='w') {
						int end1 = find(necklace, length-1,position,1);
						int end2 = find(necklace,end1-1,position,1);
						
						if (necklace.get(end2)==first){
							result = result ;
						}else {
							result = result + length - end1;
							result = result + end1 - end2 ;
						}
					}else {
						if (necklace.getLast()==first){
							result = result; 
						}else {
							int end = find(necklace,length-1,position,1);
							result = result + length - end ;	
						}
					}
				}
				if (result >=max){
					max = result;
				}
			}
			pw.println(max);
			pw.close();
			br.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static int find(LinkedList<Character> necklace,int startPoint ,int endPoint,int direction){
		if (direction ==0 ){
			int i=startPoint+1;
			for (;i<=endPoint-1;i++){
				if (necklace.get(i)!=necklace.get(startPoint)&&necklace.get(i)!='w'){
					break;
				}
			}
			return i-1;
		} else {
			int i=startPoint-1;
			for (;i>=endPoint+1;i--){
				if (necklace.get(i)!=necklace.get(startPoint)&&necklace.get(i)!='w'){
					break;
				}
			}
			return i+1;
		}
	}

}

package Karl.Water;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class beads1 {
	List<Integer> list = new ArrayList<Integer>();
	public int judge(String s){
		if(s.charAt(0)=='w'){
			return judgeE(s);
		}else{
			return judgeB(s);
		}
	}
	public int judgeE(String s){
		int result=0;
		int j=0;
		char c=s.charAt(s.length()-1);
		for(int k=s.length()-1;k>0;k--){
			j++;
			if(c!=s.charAt(k-1)&&s.charAt(k-1)!='w'){
				list.add(j);
				System.out.println(j);
				j=0;
				c=s.charAt(k-1);
			}
		}
		int h = 0;
		for(int k=0;k<s.length()-1;k++){
			if(s.charAt(k)==s.charAt(k+1)){
				h++;
			}
		}
	//	System.out.println(h+" "+s.length()/2);
		if(h==(s.length()-1)){
			list.add((s.length()/2));
		}
		list.add(0);
		int size = list.size();
		for(int p=0;p<size;p++){
			if(p==size-1){
				result = result>(list.get(p)+list.get(0))?result:(list.get(p)+list.get(0));
			}else{
				result = result>(list.get(p)+list.get(p+1))?result:(list.get(p)+list.get(p+1));
			}
		}
		return result;
	}
	public int judgeB(String s){
		int result=0,f=0;
		int j=0;
		char c=s.charAt(0);
		for(int k=0;k<s.length()-1;k++){
			j++;
			if(c!=s.charAt(k+1)&&s.charAt(k+1)!='w'){
				list.add(j);
				j=0;
				c=s.charAt(k+1);
			}
		}
		int h = 0;
		for(int k=0;k<s.length()-1;k++){
			if(s.charAt(k)==s.charAt(k+1)){
				h++;
			}
		}
	//	System.out.println(h+" "+s.length()/2);
		if(h==(s.length()-1)){
			list.add((s.length()/2));
		}
		list.add(0);
		int size = list.size();
		for(int p=0;p<size;p++){
			if(p==size-1){
				result = result>(list.get(p)+list.get(0))?result:(list.get(p)+list.get(0));
			}else{
				result = result>(list.get(p)+list.get(p+1))?result:(list.get(p)+list.get(p+1));
			}
		}
		return result;
	}
	public static void main(String[] args) throws IOException {
		beads1 b = new beads1();
		BufferedReader br = new BufferedReader(new FileReader("beads.in"));
		PrintWriter pw = new PrintWriter (new FileWriter("beads.out"));
		String s1 = br.readLine();
		String s2 = br.readLine();
		pw.println(b.judge(s2+s2));
		pw.close();
		br.close();
	}
}