“生活就像海洋，只有意志堅強的人，才能到達彼岸。”—— 馬克思

題目

n?張多米諾骨牌排成一行，將每張多米諾骨牌垂直豎立。在開始時，同時把一些多米諾骨牌向左或向右推。

每過一秒，倒向左邊的多米諾骨牌會推動其左側相鄰的多米諾骨牌。同樣地，倒向右邊的多米諾骨牌也會推動豎立在其右側的相鄰多米諾骨牌。

如果一張垂直豎立的多米諾骨牌的兩側同時有多米諾骨牌倒下時，由于受力平衡， 該骨牌仍然保持不變。

就這個問題而言，我們會認為一張正在倒下的多米諾骨牌不會對其它正在倒下或已經倒下的多米諾骨牌施加額外的力。

給你一個字符串?dominoes?表示這一行多米諾骨牌的初始狀態，其中：

• dominoes[i] = 'L'，表示第?i?張多米諾骨牌被推向左側，
• dominoes[i] = 'R'，表示第?i?張多米諾骨牌被推向右側，
• dominoes[i] = '.'，表示沒有推動第?i?張多米諾骨牌。

返回表示最終狀態的字符串。

難度：中等

分析

我們遍歷字符串，根據當前位置上的值進行分類討論：

當前值為'.'：跳過；

當前值為'L'：把之前的'.'置為'L'直到遇到非'.'的位置；

當前值為'R'：尋找下一個非'.'的位置，如果沒有或者下一個位置為'R'，將之間的'.'置為'R'，跳到下一個非'.'的位置；如果下一個位置為'L'，則將之間的'.'左邊的置為'R'，右邊的置為'L'，中間的不變，跳到'L'的下一位。

注意到我們沒有判斷當前值為'L'并且上一個非'.'位置為'R'的情況是因為該情況已被跳過（在當前值為'R'并且下一個非'.'值為'L'的情況中處理）以避免重復操作。

解答

class Solution {public String pushDominoes(String dominoes) {char[] arr=dominoes.toCharArray();int n=arr.length;int index=0;while (index<n){if (arr[index]=='.'){index++;}else if (arr[index]=='L'){for (int i=index-1;i>=0;i--){if (arr[i]!='.'){break;}arr[i]='L';}index++;}else{int nextIndex;for (nextIndex=index+1;nextIndex<n;nextIndex++){if (arr[nextIndex]!='.'){break;}}if (nextIndex==n||arr[nextIndex]=='R'){for (int i=index+1;i<nextIndex;i++){arr[i]='R';}index=nextIndex;}else{  //index R  nextIndex Lfor (int i=1;index+i<nextIndex-i;i++){arr[index+i]='R';arr[nextIndex-i]='L';}index=nextIndex+1;}}}return new String(arr);}
}

“治于神者，眾人不知其功；爭于明者，眾人知之。”——《墨子》