「漫步計算機系統」之資料結構與演算法（9）：陣列2
問題一：
將字串 S 從第 K 位置分隔成兩個子字串，並交換這兩個子字串的位置。
Input：
S=“abcXYZdef”
K=3
Output：
“XYZdefabc”
演算法描述：
將字串從0至k-1反轉；
將字串從k至串尾反轉；
將字串從頭至尾反轉，即完成。
程式碼如下：
public String LeftRotateString（String str， int n） {
if （n >= str。length（））
return str；
char［］ chars = str。toCharArray（）；
reverse（chars， 0， n - 1）；
reverse（chars， n， chars。length - 1）；
reverse（chars， 0， chars。length - 1）；
return new String（chars）；
}
private void reverse（char［］ chars， int i， int j） {
while （i < j）
swap（chars， i++， j——）；
}
private void swap（char［］ chars， int i， int j） {
char t = chars［i］；
chars［i］ = chars［j］；
chars［j］ = t；
}
問題二：
翻轉單詞順序列
Input：
“I am a student。”
Output：
“student。 a am I”
演算法描述：
從頭至尾掃描字串，用空格將字串分割為子字串；
將每個子字串反轉，子字串和空格的相對位置不變；
最後將整個字串反轉，即完成。
public String ReverseSentence（String str） {
int n = str。length（）；
char［］ chars = str。toCharArray（）；
int i = 0， j = 0；
while （j <= n） {
if （j == n || chars［j］ == ‘ ’） {
reverse（chars， i， j - 1）；
i = j + 1；
}
j++；
}
reverse（chars， 0， n - 1）；
return new String（chars）；
}
private void reverse（char［］ c， int i， int j） {
while （i < j）
swap（c， i++， j——）；
}
private void swap（char［］ c， int i， int j） {
char t = c［i］；
c［i］ = c［j］；
c［j］ = t；
}
問題三：
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序。例如和為 100 的連續序列有：
［9， 10， 11， 12， 13， 14， 15， 16］
［18， 19， 20， 21， 22］
演算法描述：
從3開始，累加；若和小於目標值，遊標end加1，數字串加遊標end，迭代；
若小於目標值，數字串減遊標start，遊標start加1；
若等於目標值，則新增這個數字串，並將左右遊標start和end加1，數字串減去原start加上end，即將整個數字串向前移動一位；
最後迭代至遊標end大於等於目標值，執行完畢！
public ArrayList
ArrayList
int start = 1， end = 2；
int curSum = 3；
while （end < sum） {
if （curSum > sum） {
curSum -= start；
start++；
} else if （curSum < sum） {
end++；
curSum += end；
} else {
ArrayList
for （int i = start； i <= end； i++）
list。add（i）；
ret。add（list）；
curSum -= start；
start++；
end++；
curSum += end；
}
}
return ret；
}
注：凡屬於本公眾號內容，未經允許不得私自轉載，否則將依法追究侵權責任。