题目
题目来源leetcode
leetcode地址：151. 翻转字符串里的单词，难度：中等。
题目描述(摘自leetcode)：
给你一个字符串 s ，逐个翻转字符串中的所有 单词 。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。 说明： 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。 翻转后单词间应当仅用一个空格分隔。 翻转后的字符串中不应包含额外的空格。 示例 1： 输入：s = "the sky is blue" 输出："blue is sky the" 示例 2： 输入：s = " hello world " 输出："world hello" 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。 示例 3： 输入：s = "a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。 示例 4： 输入：s = " Bob Loves Alice " 输出："Alice Loves Bob" 示例 5： 输入：s = "Alice does not even like bob" 输出："bob like even not does Alice" 提示： 1 <= s.length <= 104 s 包含英文大小写字母、数字和空格 ' ' s 中 至少存在一个 单词
本地调试代码：
class Solution { public int search(int[] nums, int target) { .... } public static void main(String[] args) { Solution solution = new Solution(); int[] arr = new int[]{-1,0,3,5,9,12};//这里修改数组内容 System.out.println(solution.search(arr, 2));//数组、目标值 } }
题解
NO1：拼接法
优化前(Stringbuilder拼接)
思路：从前往后进行遍历，遇到空格往后移动一步，遇到非空格先记录下当前索引，接着一直遍历到该单词的后一个位置，取出该单词最终进行拼接返回。
代码：
//"the sky is blue" => "blue is sky the" public String reverseWords(String s) { StringBuilder str = new StringBuilder(); int i = 0; //遍历字符串结束 while(i<s.length()){ //过滤空字符串 while(i<s.length() && s.charAt(i) == ' '){i++;} if( i == s.length()){ break; } int temp = i; while(i<s.length() && s.charAt(i) != ' '){i++;} String word = s.substring(temp,i); str = new StringBuilder(word).append(" ").append(str); } if(str.length()>0){ return str.substring(0,str.length() - 1); } return ""; }
这里直接使用了String的api来进行截取字符串操作，并且来进行合并多个单词时频繁创建StringBuilder，不仅仅影响时间还有空间复杂度。
优化后(char[]，时间复杂度最优解)
思路：这里是从后往前进行遍历，首先遇到!=空格的先记录索引left，紧接着继续向前移动直到为邻接点或者=空格停止，此时我们就能够拿到对应单词的范围索引，将该单词取出依次存储到新字符数组中。
代码：时间复杂度O(n)、空间复杂度O(n)
这里是没有任何API进行调用的，纯对字符数组进行操作，所以比优化前的效果好很多 public String reverseWords(String s) { //源字符数组 char[] initialArr = s.toCharArray(); //新字符数组 char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回 int newArrPos = 0; //i来进行整体对源字符数组从后往前遍历 int i = initialArr.length-1; while(i>=0){ while(i>=0 && initialArr[i] == ' '){i--;} //跳过空格 //此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置 int right = i; while(i>=0 && initialArr[i] != ' '){i--;} //指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格 for (int j = i+1; j <= right; j++) { newArr[newArrPos++] = initialArr[j]; if(j == right){ newArr[newArrPos++] = ' ';//空格 } } } //若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回) if(newArrPos == 0){ return ""; }else{ return new String(newArr,0,newArrPos-1); } }
No2：双反转+移位
思路：并没有开辟新的数组或字符串来进行拼接，而是在原始字符数组上来进行操作。
①反转字符串 "the sky is blue "=> " eulb si yks eht"
②遍历" eulb si yks eht"，过程中先对某个单词进行反转再移位
对第一个单词进行操作举例：" eulb si yks eht" =反转> " blue si yks eht" =移位> "blue si yks eht"
代码：时间复杂度O(n)、空间复杂度O(1)
/** * 空间复杂度O(1)解法 */ public String reverseWords(String s) { //步骤1：字符串整体反转（此时其中的单词也都反转了） char[] initialArr = s.toCharArray(); reverse(initialArr, 0, s.length() - 1); //步骤2：遍历循环字符串 int k = 0; for (int i = 0; i < initialArr.length; i++) { if (initialArr[i] == ' ') { continue; } int tempCur = i; while (i < initialArr.length && initialArr[i] != ' ') { i++; } for (int j = tempCur; j < i; j++) { if (j == tempCur) { //遍历开始前 reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题 } initialArr[k++] = initialArr[j]; if (j == i - 1) { //遍历结束 //避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界 if (k < initialArr.length) { initialArr[k++] = ' '; } } } } if (k == 0) { return ""; } else { //参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况 return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1); } } public void reverse(char[] chars, int begin, int end) { for (int i = begin, j = end; i < j; i++, j--) { chars[i] ^= chars[j]; chars[j] ^= chars[i]; chars[i] ^= chars[j]; } }
