编程珠玑

1.问题描述

你有一条项链，它由 N 个随机排列的红、白和蓝色的珠子组成（3<=N<=350）。下面的例子展示了两条 N=29 时的项链： 
               1 2                               1 2
           r b b r                           b r r b
          r         b                       b         b
         r           r                     b           r
        r             r                   w             r
       b               r                 w               w
      b                 b               r                 r
      b                 b               b                 b
      b                 b               r                 b
       r               r                 b               r
        b             r                   r             r
         b           r                     r           r
           r       r                         r       b
             r b r                            r r w
          Figure A                     Figure B
                        r red bead
                        b blue bead
                        w white bead
项链上的第一个和第二个珠子已经在图中标出了。
图 A 也可以用一个由 b 和 r 组成的字符串直接表示，b 代表蓝色而 r 代表红色，如下所示：brbrrrbbbrrrrrbrrbbrbbbbrrrrb。
假设你想从项链的某处将它截断拉直；接着从一端向另外一端数收集同颜色的珠子，直到碰到一个不同颜色的珠子为止；然后再从另外一端做同样的操作。(一端收集的珠子颜色可以不同于另一端的。)
请想办法找到一个截断项链的位置，能够让我们尽量多地收集到同色的珠子。

例子

如图 A 中的项链，从第 9 和第 10 个或者第 24 和 第 25 个珠子中间截断，则我们可以收集到 8 个珠子。
图 B 中的项链有白色的珠子，当遇到白色的珠子时，它既可以作为蓝色的珠子看待，也可以作为红色的珠子看待，由收集珠子时的需求决定。包含有白色珠子的项链则会由 r、b 和 w 字符组成的字符串来表示。
请编写一个程序计算从某条项链中能够收集到多少个珠子。

输入格式

第一行： N，项链上珠子的个数
第二行：一个字符串，长度为 N，由 r、b 和 w字符组成

输入样例

29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出格式

输出一行字符，它应该包含了计算出的结果。

输出样例

11

2.代码实现

import java.util.ArrayList;
import java.util.List;
/**
 * 关于一道珠玑算法的实现
 * @author guobo 2009-3-17
 * @version 1.0
 */
public class GemCode
{
 private static final String COLOR_B = "b";
 private static final String COLOR_R = "r";
 private static final String COLOR_W = "w";
 /**
  * @param String str 表示珠子颜色的字符串
  * @return int[] 返回对该字符串进行统计后的数据数组
  * 解析项链的字符串,2个颜色的
  * 例如:
  * 输入的字符串:brbrrrbbbrrrrrbrrbbrbbbbrrrrb
  * 初步转换的字符串:rbrrrbbbrrrrrbrrbbrbbbbrrrrbb
  * 最终的结果int[]中放的元素为:{1,1,3,3,5,1,2,2,1,4,4,2}
  */
 public int[] transStr(int len, String str)
 {
  /* 剔除字符串中的空白 */
  String tmp = str.replaceAll(" \\s", "");
  
  /* 判断输入的字符长度和字符串长度是否一致 */
  if(len != tmp.length())
  {
   System.out.println("the string length is error");
   return null;
  }
  
  /* 如果输入的字符串有问题,直接返回null */
  if (!validit(tmp))
  {
   System.out.println("intput the string ly user char 'b/r/w'!");
   return null;
  }
  List retList = new ArrayList();
  
  /* 从首个字符开始找起,查找字母发生变化的位置 */
  int loc = 0;
  if(COLOR_B.equals(tmp.substring(0, 1)))
  {
   loc = tmp.indexOf(COLOR_R);
  }
  else
  {
   loc = tmp.indexOf(COLOR_B);
  }
  /* 进行第一步转换 */
  tmp = tmp.substring(loc) + tmp.substring(0,loc);
  
  /* 获取需要返回的字符串 */
  while(tmp.length() > 0)
  {
   if(COLOR_B.equals(tmp.substring(0, 1)))
   {
    loc = tmp.indexOf(COLOR_R);
   }
   else
   {
    loc = tmp.indexOf(COLOR_B);
   }
   if(0 <= loc)
   {
    retList.add(String.valueOf(loc));
    tmp = tmp.substring(loc);
   }
   else
   {
    retList.add(String.valueOf(tmp.length()));
    tmp = "";
   }
  }
  return strToArray(retList);
 }
 
 /**
  * @param int[] 整型数组
  * @return int 返回相邻2个数相加的最大值
  * 从生成的数据数组中求相邻2个数相加最大的值
  */
 public int getLongNum(int[] data)
 {
  int len = data.length;
  
  int ret = data[0] + data[len-1];
  
  for (int i = 0; i < len-1; i++)
  {
   if(ret < data[i] + data[i+1])
   {
    ret = data[i] + data[i+1];
   }
  }
  return ret;
 }
 
 /**
  * @param List 输入的列表
  * @return int[] 转换后的×××数组
  * 将字符串List转换成int[]
  */
 public int[] strToArray(List dataList)
 {
  int len = dataList.size();
  int[] ret = new int[dataList.size()];
  String elem = "";
  for (int i = 0; i < len; i++)
  {
   elem = (String) dataList.get(i);
   try
   {
    ret[i] = Integer.parseInt(elem);
   }
   catch (NumberFormatException e)
   {
    e.printStackTrace();
   }
  }
  return ret;
 }
 
 /**
  * 字符串校验函数
  */
 public boolean validit(String str)
 {
  /* 确认字符串由字母b/r和空格组成 */
  return str.matches("(b|r)*");
 }
 
 /**
  * 主函数
  */
 public static void main(String[] args)
 {
  GemCode gc = new GemCode();
  int len = 29;
  String str = "brbrrrbbrrrrrbrrbbrbbbbrwwrrb";
  
  /* 对于有w字符的字符串进行处理 */
  if(0 <=str.indexOf(COLOR_W))
  {
   int a1 = 0;
   int a2 = 0;
   String str1 = str.replaceAll(COLOR_W, COLOR_R);
   if(null !=(gc.transStr(len, str1)))
   {
    a1 = gc.getLongNum(gc.transStr(len, str1));
   }
   else
   {
    return;
   }
   String str2 = str.replaceAll(COLOR_W, COLOR_B);
   if(null !=(gc.transStr(len, str2)))
   {
    a2 = gc.getLongNum(gc.transStr(len, str2));
   }
   else
   {
    return;
   }
   
   int ret = a1 > a2 ? a1:a2;
   System.out.println(ret);
  }
  else /* 没有w字符的字符串处理 */
  {
   if (null !=(gc.transStr(len, str)))
   {
    System.out.println(gc.getLongNum(gc.transStr(len, str)));
   }
  }
 }
}