//翻转str从s到e的部分 void ReverseWord(string &str, int s, int e) { while(s < e) swap(str[s++], str[e--]); } string ReverseSentence(string str) { ReverseWord(str, 0, str.size() - 1); //先整体翻转 int s = 0, e = 0; int i = 0; while(i < str.size()) { while(i < str.size() && str[i] == ' ') //空格跳过 i++; e = s = i; //记录单词的第一个字符的位置 while(i < str.size() && str[i] != ' ') //不是空格 找单词最后一个字符的位置 { i++; e++; } ReverseWord(str, s, e - 1); //局部翻转 } return str; }
class Solution { public: string ReverseSentence(string str) { string res = "", tmp = ""; for(unsigned int i = 0; i < str.size(); ++i){ if(str[i] == ' ') res = " " + tmp + res, tmp = ""; else tmp += str[i]; } if(tmp.size()) res = tmp + res; return res; } };
class Solution: def ReverseSentence(self, s): return " ".join(s.split()[::-1]) if s.strip() != "" else s
/* 算法思想:先翻转整个句子,然后,依次翻转每个单词。 依据空格来确定单词的起始和终止位置 */ public class Solution { public String ReverseSentence(String str) { char[] chars = str.toCharArray(); reverse(chars,0,chars.length - 1); int blank = -1; for(int i = 0;i < chars.length;i++){ if(chars[i] == ' '){ int nextBlank = i; reverse(chars,blank + 1,nextBlank - 1); blank = nextBlank; } } reverse(chars,blank + 1,chars.length - 1);//最后一个单词单独进行反转 return new String(chars); } public void reverse(char[] chars,int low,int high){ while(low < high){ char temp = chars[low]; chars[low] = chars[high]; chars[high] = temp; low++; high--; } } }
使用栈操作更加清晰明了,例如“world! hello”:
首先每个字符串一次进栈:
栈顶 | hello |
栈底 | world! |
然后依次出栈:hello world!
public String ReverseSentence(String str) { if (str.trim().equals("") && str.length() > 0) { return str; } Stack reverse = new Stack(); String string = str.trim(); String[] strings = string.split(" "); for (int i = 0; i length; i++) { reverse.push(strings[i]); } string = reverse.pop(); while (!reverse.isEmpty()) { string = string + " " + reverse.pop(); } return string; }
class Solution { public: string ReverseSentence(string str) { if (str.empty()) return str; reverse(str.begin(), str.end()); size_t beg = 0; size_t end = 0; while (end != string::npos){ beg = str.find_first_not_of(' ', beg); end = str.find_first_of(' ', beg); if (beg == string::npos) return str; if (end == string::npos) reverse(str.begin()+beg, str.end()); else { reverse(str.begin()+beg, str.begin()+end); beg = end+1; } } return str; } };
解题思路:先翻转每个单词,再翻转整个句子 细节很重要,要特别考虑到“ ”等输入中包含多余空格的情形 方法一:使用split public String ReverseSentence(String str) { if(str==null||str.trim().equals(""))// trim掉多余空格 return str; String[] words = str.split(" ");// 以空格切分出各个单词 StringBuffer buffer = new StringBuffer(); for(int i=0;i<words.length;i++){ buffer.append(reverse1(words[i].toCharArray(), 0, words[i].length()-1)).append(" "); } if(buffer.length()>0) buffer.deleteCharAt(buffer.length()-1);// 删除最后一个空格 return reverse1(buffer.toString().toCharArray(), 0, buffer.length()-1); } private String reverse1(char[] str, int l, int r) { // TODO Auto-generated method stub if(l>r) return ""; char tmp; while(l<r){ tmp = str[l]; str[l] = str[r]; str[r] = tmp; l++; r--; } return String.valueOf(str); } 方法二:不使用split private void reverse(char[] str, int l, int r) { // TODO Auto-generated method stub if(l>r) return; char tmp; while(l<r){ tmp = str[l]; str[l] = str[r]; str[r] = tmp; l++; r--; } } public String ReverseSentence(String str) { if(str==null||str.equals("")) return str; char[] words = str.toCharArray(); int l=0,r,i=0; boolean isFirst1 = true; boolean isFirst2 = true; while(i<words.length){ if(words[i]!=' '&&isFirst1){ // 定位到第一个不为空的字符 l = i; isFirst1 = false; i++; }else if(words[i]==' '&&isFirst2){ r = i-1;// 定位到单词后的第一个空格 isFirst2 = false; // 翻转已经截取的单词 reverse(words, l, r); // 修改标志,定位下一个单词 isFirst1 = true; isFirst2 = true; i++; }else{ i++; } } if(words[words.length-1]!=' '){ reverse(words, l, words.length-1);// 翻转最后一个单词 } reverse(words, 0, words.length-1); return String.valueOf(words); }
/* * 剑指offer的思想:两次翻转 */ public class Solution { public String ReverseSentence(String str) { if(str==null||str.trim().getClass().equals("")) return str; char[] c=str.toCharArray(); reverse(c, 0, str.length()-1);//翻转整个句子 //翻转句子中的每个单词 int begin=0; int end=0; while(begin!=c.length){//若起始字符为空格,则begin和end都自加 if(c[begin]==' '){ begin++; end++; } else if(c[end]==' '){//遍历到终止字符为空格,就进行翻转 reverse(c, begin, --end); begin=++end; } else if(end==c.length-1){//若遍历结束,就进行翻转 reverse(c, begin,end); begin=++end; } else{//没有遍历到空格或者遍历结束,则单独对end自减 end++; } } return String.valueOf(c); } //完成翻转功能 private void reverse(char[] c,int begin,int end){ while(begin<end){ char temp=c[begin]; c[begin]=c[end]; c[end]=temp; begin++; end--; } } }
看哥简洁的代码,反转两次: #include<algorithm> class Solution { public: string ReverseSentence(string str) { std::reverse(str.begin(),str.end()); int front=0; int back=0; int size = str.size(); while(front<size){ while(front<size&&str[front]==' ')++front; back=front; while(back<size&&str[back]!=' ')++back; std::reverse(str.begin()+front, str.begin()+back); front=back; } return str; } };
//时间O(n),空间O(1)。 //两次翻转,第一次整体翻转,第二次每个单词再翻转。 class Solution { public: string ReverseSentence(string str) { reverse(str.begin(), str.end()); string::size_type s = 0, e; while((e=str.find(' ', s)) != string::npos){ reverse(str.begin()+s, str.begin()+e); s = e + 1; } reverse(str.begin()+s, str.end()); return str; } };
# -*- coding:utf-8 -*- class Solution: """ Problem: 牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。 同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。 例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了, 正确的句子应该是“I am a student.”。 Cat对一一的翻转这些单词顺序可不在行,你能帮助他么? ----------------------------------------- Think: 1、直接法,直接分割字符串,然后反序拼接 2、对所有的字符进行翻转,然后对整个字符串进行翻转。python不好实现。 3、堆栈思想,反转字符串,先进后出,就是反转了 ----------------------------------------- Idea: 1、直接分割字符串,然后反序拼接 2、使用堆栈先进后出的规则,反转字符串 ----------------------------------------- Code[1]: def ReverseSentence(self, s): alist = s.split(" ") alist.reverse() return " ".join([x for x in alist]) ----------------------- 运行时间:37ms 占用内存:5752k 量级:O(n) 空间:n 优点:很容易想到并实现 缺点:需要多余的额外空间 ----------------------------------------- Code[2]: def ReverseSentence(self, s): alist = s.split(" ") stacklist = [] for i in alist: stacklist.append(i) result = [] while len(stacklist) > 0: result.append(stacklist.pop()) return " ".join([x for x in result]) ----------------------- 运行时间:29ms 占用内存:5612k 量级:O(n) 空间:2n 优点:容易理解,而且比较巧妙 缺点:需要多余的额外空间 """ def ReverseSentence(self, s): alist = s.split(" ") stacklist = [] for i in alist: stacklist.append(i) result = [] while len(stacklist) > 0: result.append(stacklist.pop()) return " ".join([x for x in result])
class Solution { public: string ReverseSentence(string str) { int len = str.size(), i = str.size() - 1; while(i >= 0){ stack<char> tmp; while(i >= 0 && str[i] != ' '){ tmp.push(str[i]); --i; } while(!tmp.empty()){ str += tmp.top(); tmp.pop(); } str += str[i]; --i; } return str.substr(len, len); } };
public class Solution { public String ReverseSentence(String str) { if(str==null||str.length()==0||str.trim().length()==0) return str; StringBuffer sb = new StringBuffer(); String[] s = str.trim().split(" "); for(int i = s.length-1;i>=0;i--){ if(s[i]!="") sb.append(s[i]); if(i-1>=0) sb.append(" "); } return sb.toString(); } }
//不知不觉刷到42题了,这道题主要思想就是先翻转所有字符,再逐个单词翻转,逐个单词翻转的时候考虑三种不同情况即可。 class Solution { public: void Reverse(string& sent, int begin, int end) { if (begin<0 || end<0) return; while (begin<end) { char c; c = sent[begin]; sent[begin] = sent[end]; sent[end] = c; begin++; end--; } } string ReverseSentence( string &str) { int length = str.size(); if (length <= 1) return str; int pBegin = 0; int pEnd = 0; while (str[pEnd] != '\0') { pEnd++; } pEnd--; Reverse(str, pBegin, pEnd); pBegin = pEnd = 0; while (str[pBegin] != '\0') { if (str[pBegin] == ' ') { pBegin++; pEnd++; } else if (str[pEnd] == ' ' || str[pEnd] == '\0') { Reverse(str, pBegin, --pEnd); pBegin = ++pEnd; } else { pEnd++; } } return str; } };
string ReverseSentence(string str) { stack<string> Words; int currBlankPos = 0; int perBlankPos = 0; string subString; while (currBlankPos>=0) { currBlankPos = str.find_first_of(' ', perBlankPos); // 找到空格分隔字符串(找到word压如栈里头) subString = str.substr(perBlankPos, currBlankPos < 0 ? (str.length() - perBlankPos) : currBlankPos - perBlankPos); // 按长度截取单词 perBlankPos = currBlankPos + 1; Words.push(subString); //把单词压如栈 } subString.clear(); while (!Words.empty()) { subString += Words.top(); Words.pop(); if(!Words.empty()) subString += " "; // 需不需要加空格 } return subString; }
public static String ReverseSentence(String str) { StringBuffer sb = new StringBuffer(""); if(str.length() <= 0 || str.trim().equals("")){ //要trim(),可能输入多个空格组成的字符串 return str; } String[] strSet = str.split(" "); int length = strSet.length; for(int i = length-1; i > 0 ;i--){ sb.append(strSet[i]+" "); } sb.append(strSet[0]); return sb.toString(); }
public class Solution { public String ReverseSentence(String str) { if (str.split(" ").length < 1 || str == null || str == "") { return str; } String resString = ""; String[] arr = str.split(" "); int left = 0; int right = arr.length - 1; while (left < right) { String tmp = arr[left]; arr[left++] = arr[right]; arr[right--] = tmp; } for (int i = 0; i < arr.length; i++) { resString += arr[i]; if (i <= arr.length - 2) { resString += " "; } } return resString; } }
虽然蒙对了,有谁能解释一下只有空格的情况。 思路:先反转整个句子,再依次反转每个单词 class Solution { public: string ReverseSentence(string str) { int len=str.size(); if(str[0]==' ')return str;//我改成str==" "为啥不行? fun(str,0,len-1);//整体反转一次 for(int l=0,r=0;r<=len;){//l设为每个单词开头,r设为每个单词后的空格位置 if(r<len&&str[r]!=' ')r++;//没有到达末尾或者遇到空格 else{//遇到空格或者到末尾 fun(str,l,r-1); l=++r; } } return str; } void fun(string &str,int l,int r){//反转一个字符串 for(int i=l;i<=(l+r)/2;i++) swap(str[i],str[l+r-i]); } };
//有两种方法,第一种不改变原来的字符串,新建一个新的串,通过检验空格获取每个单词,然后放//到结果串中去;第二种两次翻转,先整体翻转,然后检测空格,将每个单词翻转 //方法一: class Solution { public: string ReverseSentence(string str) { reverse(str.begin(),str.end()); string:: iterator left=str.begin(),right=left; while(*right!='\0'){ while(*right!='\0'&&*right!=' ') ++right; reverse(left,right); if(*right!='\0'){ left=right+1; right=left; } } return str; } }; //方法二: class Solution { public: string ReverseSentence(string str) { reverse(str.begin(),str.end()); string::size_type left=0,right=0; while((right=str.find(' ',left))!=str.npos){ reverse(str.begin()+left,str.begin()+right); left=right+1; } reverse(str.begin()+left,str.end()); return str; } };