資訊專欄INFORMATION COLUMN
摘要：代碼先反轉(zhuǎn)整個數(shù)組反轉(zhuǎn)每個單詞雙指針交換法復(fù)雜度時間空間思路這題就是版的做法了，先反轉(zhuǎn)整個數(shù)組，再對每個詞反轉(zhuǎn)。
Reverse Words in a String
使用API 復(fù)雜度Given an input string, reverse the string word by word.
For example, Given s = "the sky is blue", return "blue is sky the".
Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space
時間 O(N) 空間 O(N)
思路將單詞根據(jù)空格split開來存入一個字符串?dāng)?shù)組，然后將該數(shù)組反轉(zhuǎn)即可。
注意先用trim()將前后無用的空格去掉
用正則表達(dá)式" +"來匹配一個或多個空格
代碼public class Solution {
public String reverseWords(String s) {
String[] words = s.trim().split(" +");
int len = words.length;
StringBuilder result = new StringBuilder();
for(int i = len -1; i>=0;i--){
result.append(words[i]);
if(i!=0) result.append(" ");
}
return result.toString();
}
}
雙指針交換法
復(fù)雜度
時間 O(N) 空間 O(N) 如果輸入時char數(shù)組則是O(1)
思路先將字符串轉(zhuǎn)換成char的數(shù)組，然后將整個數(shù)組反轉(zhuǎn)。然后我們再對每一個單詞多帶帶的反轉(zhuǎn)一次，方法是用兩個指針記錄當(dāng)前單詞的起始位置和終止位置，遇到空格就進(jìn)入下一個單詞。
代碼public class Solution {
public String reverseWords(String s) {
s = s.trim();
char[] str = s.toCharArray();
// 先反轉(zhuǎn)整個數(shù)組
reverse(str, 0, str.length - 1);
int start = 0, end = 0;
for(int i = 0; i < s.length(); i++){
if(str[i]!=" "){
end++;
} else {
// 反轉(zhuǎn)每個單詞
reverse(str, start, end - 1);
end++;
start = end;
}
}
return String.valueOf(str);
}
public void reverse(char[] str, int start, int end){
while(start < end){
char tmp = str[start];
str[start] = str[end];
str[end] = tmp;
start++;
end--;
}
}
}
Reverse Words in a String II
雙指針交換法 復(fù)雜度Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example, Given s = "the sky is blue", return "blue is sky the".
Could you do it in-place without allocating extra space?
時間 O(N) 空間 O(1)
思路這題就是Java版的Inplace做法了，先反轉(zhuǎn)整個數(shù)組，再對每個詞反轉(zhuǎn)。
代碼public class Solution {
public void reverseWords(char[] s) {
reverse(s, 0, s.length - 1);
int start = 0;
for(int i = 0; i < s.length; i++){
if(s[i] == " "){
reverse(s, start, i - 1);
start = i + 1;
}
}
reverse(s, start, s.length - 1);
}
public void reverse(char[] s, int start, int end){
while(start < end){
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64538.html
摘要：公眾號愛寫給定一個字符串，你需要反轉(zhuǎn)字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。示例輸入輸出注意在字符串中，每個單詞由單個空格分隔，并且字符串中不會有任何額外的空格。 公眾號：愛寫bug（ID：icodebugs） 給定一個字符串，你需要反轉(zhuǎn)字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。 Given a string, you need to revers...
摘要：公眾號愛寫給定一個字符串，你需要反轉(zhuǎn)字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。示例輸入輸出注意在字符串中，每個單詞由單個空格分隔，并且字符串中不會有任何額外的空格。 公眾號：愛寫bug（ID：icodebugs） 給定一個字符串，你需要反轉(zhuǎn)字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。 Given a string, you need to revers...
摘要：小鹿題目翻轉(zhuǎn)字符串里的單詞給定一個字符串，逐個翻轉(zhuǎn)字符串中的每個單詞。說明無空格字符構(gòu)成一個單詞。遇到空格之后，將單詞進(jìn)行倒序拼接。消除尾部的空格。測試用例空字符串。中間空格大于的字符串。 Time：2019/4/20Title: Reverse Words In a StringDifficulty: MidumnAuthor: 小鹿 題目：Reverse Words In a ...
摘要：說明無空格字符構(gòu)成一個單詞。輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。我們將字符串轉(zhuǎn)為字符型數(shù)組并用兩個指針來解這道題。指針作為原字符串轉(zhuǎn)為字符數(shù)組的索引，從右向左移。 公眾號：愛寫bug（ID：icodebugs） 翻轉(zhuǎn)字符串里的單詞 Given an input string, reverse the string word by word. 示例 1：...
摘要：說明無空格字符構(gòu)成一個單詞。輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。我們將字符串轉(zhuǎn)為字符型數(shù)組并用兩個指針來解這道題。指針作為原字符串轉(zhuǎn)為字符數(shù)組的索引，從右向左移。 公眾號：愛寫bug（ID：icodebugs） 翻轉(zhuǎn)字符串里的單詞 Given an input string, reverse the string word by word. 示例 1：...
閱讀 3821·2021-09-30 09:59
閱讀 2474·2021-09-13 10:34
閱讀 614·2019-08-30 12:58
閱讀 1543·2019-08-29 18:42
閱讀 2237·2019-08-26 13:44
閱讀 2964·2019-08-23 18:12
閱讀 3355·2019-08-23 15:10
閱讀 1657·2019-08-23 14:37
