劍指 Offer 58 - I. 翻轉單詞順序
劍指 Offer 58 - I. 翻轉單詞順序
輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字元的順序不變。為簡單起見，標點符號和普通字母一樣處理。例如輸入字元串"I am a student. "，則輸出"student. a am I"。
示例 1：
輸入: "the sky is blue"
輸出: "blue is sky the"
示例 2：
輸入: " hello world! "
輸出: "world! hello"
解釋: 輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。
示例 3：
輸入: "a good example"
輸出: "example good a"
解釋: 如果兩個單詞間有多餘的空格，將反轉後單詞間的空格減少到只含一個。
說明：
- 無空格字元構成一個單詞。
- 輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。
- 如果兩個單詞間有多餘的空格，將反轉後單詞間的空格減少到只含一個。
一、套路化or模板化
首先可以看一下這個核心模板程式碼：
char[] str = s.trim().toCharArray();
Stack<String> res = new Stack<>();//存放字元串的棧
StringBuilder tmp = new StringBuilder();//臨時字元串
for(char c : str) {//遍歷字元句子
// 遇到' '就入棧，否則就接在tmp後
if(c == ' ') {
if(tmp.length()!=0){
res.push(tmp.toString());
// 清空StringBuilder的三種方法
// tmp = new StringBuilder(); 性能最差
// tmp.setLength( 0 ); 可以使用
tmp.delete( 0, tmp.length() ); // 推薦使用
}
}else{
tmp.append(c) ;
}
}
然後這道題的程式碼如下：
class Solution {
public String reverseWords(String s) {
char[] str = s.trim().toCharArray();
Stack<String> res = new Stack<>();//存放字元串的棧
StringBuilder tmp = new StringBuilder();//臨時字元串
for(char c : str) {//遍歷字元句子
// 遇到' '就入棧，否則就接在tmp後
if(c == ' ') {
if(tmp.length()!=0){
res.push(tmp.toString());
// 清空StringBuilder的三種方法
// tmp = new StringBuilder(); 性能最差
// tmp.setLength( 0 ); 可以使用
tmp.delete( 0, tmp.length() ); // 推薦使用
}
}else{
tmp.append(c) ;
}
}
// 此時tmp為s的最後一個單詞
while(!res.isEmpty()){
tmp.append(" ").append(res.pop());
}
return tmp.toString();
}
}
二、雙指針
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 刪除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首個空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加單詞
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳過單詞間空格
j = i; // j 指向下個單詞的尾字元
}
return res.toString().trim(); // 轉化為字元串並返回
}
}
三、分隔+倒序
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); // 刪除首尾空格，分割字元串
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍歷單詞列表
if(strs[i].equals("")) continue; // 遇到空單詞則跳過
res.append(strs[i] + " "); // 將單詞拼接至 StringBuilder
}
return res.toString().trim(); // 轉化為字元串，刪除尾部空格，並返回
}
}
