這將是這里第一道用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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。