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.
click to show clarification.
Clarification: What constitutes a word? A sequence of non-space characters constitutes a word. Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces. How about multiple spaces between two words? Reduce them to a single space in the reversed string.
s思路: 1. 這道題見過多次了。先全部reverse,然后對(duì)每個(gè)單詞reverse。 2. 重點(diǎn)反而不是reverse,可以把reverse寫成一個(gè)函數(shù);重點(diǎn)是找到每個(gè)單詞的開始結(jié)尾??赡苡腥我舛鄠€(gè)空格,導(dǎo)致不規(guī)則的情況,不規(guī)則的情況,我們一般用while來handle。
3.這道題還是比較復(fù)雜的,要求去掉所有冗余空格?,F(xiàn)在這個(gè)方法比自己想到的方法簡(jiǎn)單得多,而且好實(shí)現(xiàn)!自己原先想的方法是:對(duì)空格計(jì)數(shù),數(shù)完然后一起刪;而別人家的代碼,看空格的坐標(biāo),如果i=0或i=n-1,以及看這個(gè)坐標(biāo)左右位置是否有單詞決定是否刪除這個(gè)空格,即:一個(gè)一個(gè)的判斷,一個(gè)一個(gè)的刪除。就不用計(jì)數(shù)了,簡(jiǎn)單! 4.這里面的邏輯是這樣的:如果對(duì)空格計(jì)數(shù),尤其是在頭部和尾部的空格,不能用坐標(biāo)判斷,那對(duì)句中的空格和句首尾的空格就要分開處理,增加復(fù)雜性。這種情況下,就可以嘗試不計(jì)數(shù),而改用發(fā)現(xiàn)一個(gè)刪除一個(gè)。以后做題的時(shí)候,定制化,比如統(tǒng)計(jì)空格的個(gè)數(shù),雖然道理上沒錯(cuò),但是代碼很繁復(fù),還不如不去管這些信息,直接判斷一個(gè)空格是否合法反而簡(jiǎn)單!也就是說,好的方法是實(shí)現(xiàn)起來容易,道理講得明白即可,沒有非那一種不可。思考的時(shí)候,不可以潛意識(shí)覺得那一種就絕對(duì)好或絕對(duì)差,更不能給某一種方法打標(biāo)簽,這樣只會(huì)讓自己執(zhí)著一種方法,反而不利于獨(dú)立自由之思考!
class Solution {public: void reverse(string&s,int begin,int end){ while(begin<end){ swap(s[begin],s[end]); begin++; end--; } } void reverseWords(string &s) { // int n=s.size(); reverse(s,0,n-1); int i=0,l=0,r=0; while(i<n){ if(s[i]==' '){ if(i>0&&i<n-1&&s[i-1]!=' '&&s[i+1]!=' '){ i++; l=i; r=i; }else{ s.erase(i,1);n--;//長(zhǎng)度減一 } }else{ while(r<n&&s[r]!=' ') r++; reverse(s,l,r-1); i=r; } } }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注