7-4 1.1.4 破碎的项链（USACO）

这将是这里第一道用Java解的题目。
大概在两个月前，暑假实训的时候就已经用c++做过这题了。记得当时一点一点修改漏洞打补丁，搞得整个代码完全不可读；后来调整了思路，整体设计了解决方案，就好多了。

记得当时印象最深刻的一个问题是：（可以简化为）如何确保一段由01组成的数字串，全是0或者全是1？

有两种方案，第一种是在遍历过程中不断比较i和i-1位是不是一样的，另一种是只比较第i位和第0位是不是一样的。对于这一道题来说，第二种方案方便多了。

这道题大概是说拿到一个字串，在一个地方打开，向左最深可以走多远，向右最深可以走多远，返回它们加起来的值；对于不同的地方，比较最大的值。我在主函数部分进行遍历所有点，并且比较最大； 用一个函数求每个地方左右加起来的深度；而这个函数分别调用了左深度函数和右深度函数（它们只有微小的差异，大致是在移动方向和边界上）。

我把neckLace复制了一份，并且将它们头尾接起来，来处理循环的问题。

package brokenNecklace; //双倍的项链接起来 //从第二位开始经过到一条完整项链加一位 //left和right //延续性的判断//开头w： 从第一个有效的开始//开头rb： 记录下开头的情况//经过w： 移动到下一个 计数+1//经过rb 对比后再决定是否+1；import java.util.Scanner;public class Main {static int n;static String necklace;static String doubleNecklace;static int maxLen= 0;public static void main(String[] args) {Scanner console= new Scanner(System.in);n = console.nextInt();necklace = console.next();doubleNecklace = necklace + necklace;//System.out.println(doubleNecklace);if(n==1) {System.out.println(1);}for(int i=1; i< n; i++) {//条件表达式maxLen= length(i)>maxLen?length(i):maxLen; } if(maxLen>n)System.out.println((int)(maxLen*0.5));else System.out.println(maxLen);}public static int length(int loca) {int thisMax= 0;int leftLen= 0;int rightLen= 0;leftLen= findDeptL(loca-1);rightLen= findDeptR(loca);thisMax= leftLen+rightLen;return thisMax;}public static int findDeptL(int loca) {int dept= 0;char saveHead= 'A';boolean hasHead= false;//标记是否走到尽头boolean lenSign= true;//第一个白色；非白色 中间白色； 非白色； 记录下第一个非白色的；while(lenSign == true) {//System.out.println(loca + "LOCA");if(loca==-1) break;else if(doubleNecklace.charAt(loca) == 'w') {loca = loca -1;dept ++;}else if(hasHead== false) {saveHead= doubleNecklace.charAt(loca);loca= loca-1;dept++;hasHead= true;}else if(hasHead== true && doubleNecklace.charAt(loca)== saveHead ) {loca= loca-1;dept ++;}else if(doubleNecklace.charAt(loca)!= saveHead) {break;}else {System.out.println("ERROR");}} return dept;}public static int findDeptR(int loca) {int dept= 0;char saveHead= 'A';boolean hasHead= false;//标记是否走到尽头boolean lenSign= true;//第一个白色；非白色 中间白色； 非白色； 记录下第一个非白色的；while(lenSign == true) {//System.out.println(loca);if(loca==2*n) break;if(doubleNecklace.charAt(loca) == 'w') {if(loca==0) break;loca = loca +1;dept ++;}else if(hasHead== false) {saveHead= doubleNecklace.charAt(loca);loca= loca+1;dept++;hasHead= true;}else if(hasHead== true && doubleNecklace.charAt(loca)== saveHead ) {loca= loca+1;dept ++;}else if(doubleNecklace.charAt(loca)!= saveHead) {break;}else {System.out.println("ERROR");}} return dept;}}

对于求深度，我想最重要的是把不同的情况区分开；我打算这么分，按照开头还是中间分，按照白色还是br分；
所以最后得到这样的情况：开头是白；开头是br；中间是白，中间是br。我先写了个while循环，后来发现并没有发挥作用。（以下按照if elseif的顺序）

如果开头是白色那就深度+1，并且走到下一个吧（事实上中间的白色也这样处理）；注意我们需要记录下第一个不是白色的位置的颜色，因为这是我们判断是否连续的基础，所以我们需要一个变量来记录是不是已经得到了第一个不为白色的位置（hasHead?)；如果没有就记录颜色；如果有，那就是中间的普通位置了，颜色一致就继续前进；注意，出现颜色不一致必然已经有了初始颜色，所以一旦颜色不一样就之间退出；写得时候不太自信，用elseif完整隔开了所有情况，并且在随后写了else看看有没有啥没有考虑到的。

public static int findDeptL(int loca) {int dept= 0;char saveHead= 'A';boolean hasHead= false;//标记是否走到尽头boolean lenSign= true;//第一个白色；非白色 中间白色； 非白色； 记录下第一个非白色的；while(lenSign == true) {//System.out.println(loca + "LOCA");if(loca==-1) break;else if(doubleNecklace.charAt(loca) == 'w') {loca = loca -1;dept ++;}else if(hasHead== false) {saveHead= doubleNecklace.charAt(loca);loca= loca-1;dept++;hasHead= true;}else if(hasHead== true && doubleNecklace.charAt(loca)== saveHead ) {loca= loca-1;dept ++;}else if(doubleNecklace.charAt(loca)!= saveHead) {break;}else {System.out.println("ERROR");}} return dept;}

求深度的函数就这样完成了。另外有一点很有趣，因为项链是个圈，所以你还需要考虑循环的情况。我想直接在导入的necklace字串后面再接一个复制的necklace变成doublenNecklace就可以解决这个问题：比如说necklace是bbwwr那我就得到一个bbwwrbbwwr，在这个上面进行分析运算。 注意，这种情况下那种纯色项链，比如wwwww，bbbbb或者wwwbb，数出来的长度会变成n的两倍；我以为这会是个非常麻烦的事情，后来发现简单的

if(maxLen>n)System.out.println((int)(maxLen*0.5));else System.out.println(maxLen);

防止输出不合理值就行了。

总结

以上是生活随笔为你收集整理的7-4 1.1.4 破碎的项链（USACO）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。