翻转单词序列【Java版】
翻转单词序列
http://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3
方法一:一轮扫描法
//从后向前扫描,将单词转移到另一个O(n)空间String //两重循环,外面i一直向左探测,探测到一个单词开始处,用j向右遍历,进行复制 public class Solution { public String ReverseSentence(String str) { String res = "";//【String不要用null初始化, 要用空字符串""】 //如果写成 String str = null; ==>系统会得到str = "null" if(str == null || str.length()==0)return res; char[] ch = str.toCharArray(); for(int i=ch.length-1; i>=0; --i){ if(i==0 || ch[i-1]==' '){//i==0写在前面,防止i-1溢出 for(int j=i; j!=ch.length && ch[j]!=' '; ++j){ res += ch[j];//【String直接加char】 } if(i!=0) res += ' ';//加空格,最后不加 } } return res; } }//时间O(n) 空间O(n)
方法二:两轮翻转法
//首先完全翻转,然后逐个单词翻转 public class Solution { public String ReverseSentence(String str) { char[] ch = str.toCharArray(); char temp = 0; for(int i=0; i<ch.length/2; ++i){ temp = ch[i]; ch[i] = ch[ch.length-1-i]; ch[ch.length-1-i] = temp; } int left = 0; String res =""; for(int right=0; right<=ch.length-1; ++right){ if(right == ch.length-1 || ch[right+1]==' '){ for(int i=right; i>=left; --i){ res += ch[i]; } if(right != ch.length-1)res += ' '; left = right+2; } } return res; } }//时间O(n) 空间O(n) //此方法(对于Java语言)并无优势,两轮而且都调整、耗时多 //C语言,可以做到空间O(1) //C语言对String操作的自由度更高
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》