思路及解答Java内置函数分割反转Java ⾥⾯有切割字符串的⽅法直接⽤空格进⾏分隔分隔成为多个单词然后从字符串数组的后⾯开始每⼀个字符拼接上⼀个空格但是值得注意的⼀点是当只剩下⼀个字符串的时候也就是索引为 0 的时候不需要再拼接空格。代码实现如下javapublic class Solution { public String ReverseSentence(String str) { if (str null || str.length() 0 || str.equals( )) { return ; } //去除首尾空格后按照空格分隔 String[] strs str.trim().split( ); StringBuilder stringBuilder new StringBuilder(); for (int i strs.length - 1; i 0; i--) { stringBuilder.append(strs[i]); stringBuilder.append(i 0 ? : ); } return stringBuilder.toString(); } }时间复杂度O(n)分割和拼接各需线性时间空间复杂度O(n)存储单词数组和结果字符串借助栈借助栈栈是先进后出也就是我们切割完字符串之后全部放到栈中再全部取出来拼接就可以完成逆序的操作。有⼀个值得注意的点就是空格的问题我们压栈的时候跟随着拼接上空格即可最后⼀个字符不压⼊空格。javapublic String ReverseSentence(String str) { if (str null || str.length() 0) return str; StringBuilder stringBuilder new StringBuilder(); String[] strs str.split( ); if (strs.length 0) return str; Stack String stack new Stack (); for (int i 0; i strs.length - 1; i) { stack.push(strs[i]); stack.push( ); } stack.push(strs[strs.length - 1]); while (!stack.isEmpty()) { stringBuilder.append(stack.pop()); } return stringBuilder.toString(); }双指针法(推荐)⾸先判断字符串 str 是否为空或者为空字符如果 str 不为空则初始化 start 和 end 指针指向字符串的尾部 start 从尾部向头部遍历针对每⼀个字符如果字符为空字符如果 start 和 end 不是出于同⼀个位置说明已经遍历完⼀个单词那么将 start1 ~ end 之间的字符拼接到结果后并且添加上⼀个空格。将 start-1 并且 end 指向 start 的位置否则说明是多余的空格直接跳过 start-1 endstart如果字符不是空字符可以把 start 索引前移也就是 start--最后剩下最后⼀个单词的时候需要特殊处理最后⼀个单词拼接到字符串后⾯就可以了。javapublic class Solution { public static void main(String[] args) { Solution solution new Solution(); System.out.println(solution.ReverseSentence(nowcoder. a am I)); } public String ReverseSentence(String str) { if (str ! null str.length() ! 0 !str.equals( )) { int start str.length() - 1, end start; StringBuffer stringBuffer new StringBuffer(); for (; start 0;) { // 如果为空格 if (str.charAt(start) ) { // 且开始索引和结束索引不⼀致的情况 if (start ! end) { // 遍历start1~end的字符加到 for (int i start 1; i end; i) { stringBuffer.append(str.charAt(i)); } // 每⼀个单词的后⾯加上⼀个空格 stringBuffer.append( ); } start--; end start; } else { start--; } } // 处理最后⼀个单词 for (int i 0; i end; i) { stringBuffer.append(str.charAt(i)); } return stringBuffer.toString(); } return str; } }时间复杂度O(n)每个字符被访问常数次空间复杂度O(n)StringBuilder存储结果三次反转法空间最优通过字符级操作实现O(1)空间复杂度假设字符数组可修改。先反转整个字符串再逐个反转每个单词三次反转的数学原理对于句子 A B CA、B、C为单词整体反转 C B A单词反转 C反转→ C, B反转→ B, A反转→ A结果 C B A → 正是期望的顺序javapublic class Solution { public String reverseWords(String s) { if (s null || s.length() 0) return ; char[] chars s.toCharArray(); int n chars.length; // 步骤1反转整个字符串 reverse(chars, 0, n - 1); // 步骤2反转每个单词 reverseWords(chars, n); // 步骤3清理多余空格 return cleanSpaces(chars, n); } /** * 反转字符数组的指定区间 */ private void reverse(char[] chars, int left, int right) { while (left right) { char temp chars[left]; chars[left] chars[right]; chars[right--] temp; } } /** * 反转每个单词 */ private void reverseWords(char[] chars, int n) { int i 0, j 0; while (i n) { // 跳过前导空格 while (i j || (i n chars[i] )) i; // 找到单词结尾 while (j i || (j n chars[j] ! )) j; // 反转单词 reverse(chars, i, j - 1); } } /** * 清理多余空格返回最终字符串 */ private String cleanSpaces(char[] chars, int n) { int i 0, j 0; while (j n) { // 跳过前导空格 while (j n chars[j] ) j; // 保留单词间的一个空格 while (j n chars[j] ! ) { chars[i] chars[j]; } // 添加单词间空格 while (j n chars[j] ) j; if (j n) { chars[i] ; } } return new String(chars, 0, i); } }