代码随想录刷题day24|（字符串篇）151.反转字符串中的单词

一、题目思路

1.快慢指针移除字符串首尾以及单词中的多余空格

类似前面数组篇--移除元素代码随想录刷题day02|（数组篇）27.移除元素、26.删除有序数组中的重复项_代码随想录网站-CSDN博客

快指针fast遍历整个字符串，慢指针slow指向新字符串中的元素，去除时，只看fast的值，不看slow；fast为空(*)，slow=空，说明是开头，slow不移动，移动fast 直到fast指向不为空；fast为空，slow≠空，说明到了某个单词末尾，slow=空，这个操作只执行一次，确保实现每个单词之间有一个空格，同时slow+1，如果fast仍未空，说明单词之间有多个空格，移动fast直到不再为空，此时同时移动slow和fast，并将fast指向元素赋值给slow，直到fast为空，回到 * 位置，重新循环判断；最后slow指向新数组的末尾+1 = 长度;

注：回到for循环后，fast先加1，重复加1，会不会有问题？

当fast没有到末尾，但为空时，最后的while循环结束，重新开始for循环，此时fast指向为空，如果fast++，相当于去除掉指向空格，所以不会出错；

2.将字符串整体反转

类似反转字符串：代码随想录刷题day22|（字符串篇）344.反转字符串、541.反转字符串 II-CSDN博客

3.将每个单词反转

同上，只是需要判断是否到单词末尾，即指向为空时，进行反转；

注：1.for(int end = 0;end <= chars.length;end++)

 //这里<= 是为了 让end指向字符串末尾时和 指向单词间空格时 可以有同样的处理操作，否则end = length - 1 是最后一次循环，但是 reverse中第3个参数是end-1，那么end指向的最后一个单词就不会进行反转，就会出错；如果让第3个参数=end，那么指向单词间空格时就不符合要求，因为此时end 指向空格，空格不参与反转，但判断单词间只能通过判断空格，所以只能让end指向末尾元素的后一位，从而保证两者操作逻辑相同，不用单独处理；

2.if(end == chars.length || chars[end] == ' ') 判断条件的顺序

if(end == chars.length || chars[end] == ' ')  ✅

if(chars[end] == ' ' || end == chars.length) ❌

错误原因：

在if(chars[end] == ' ' || end == chars.length) 中：

1.chars[end]的访问可能越界：当end = chars.length时，数组索引范围时0到chars.length -1，访问chars[chars.length] 会导致ArrayIndexOutOfBoundsException；

2.短路求值：逻辑运算符 || 是短路求值，即如果第一个条件是true，则不会计算第二个条件；那么如果将end == chars,length放在前面，当end = chars.length时，为true，程序不会执行chars[end] == ' '，从而避免越界访问。

二、相关算法题目

151.反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）

class Solution {public String reverseWords(String s) {char[] chars = s.toCharArray();//1.去除首尾以及单词之间多余空格 快慢指针chars = removeExtraSpaces(chars);//2.反转整个字符串reverse(chars, 0, chars.length - 1);//3.反转单词reverseEachWord(chars);return new String(chars);   }//1.去除首尾以及单词之间多余空格 快慢指针public char[] removeExtraSpaces(char[] chars){int slow = 0;for(int fast = 0;fast < chars.length;fast++){if(chars[fast] != ' '){//此时不为空 说明指向下一个单词开头 但是slow要留出单词空  特殊情况 开头多个空格 slow不赋值 直接while if(slow != 0){chars[slow++] = ' ';}while(fast < chars.length && chars[fast] != ' '){chars[slow++] = chars[fast++];}//长度范围内退出while说明fast=空 到了单词末尾 最后slow指向新数组的末尾+1 = 长度}}char[] newChars = new char[slow];System.arraycopy(chars, 0, newChars, 0, slow);return newChars;}// //2.反转整个字符串public void reverse(char[] chars, int left, int right){if (right >= chars.length) {System.out.println("set a wrong right");return;}while(left < right){char c = chars[left];chars[left] = chars[right];chars[right] = c;left++;right--;}}//3.反转单词public void reverseEachWord(char[] chars){int start = 0;for(int end = 0;end <= chars.length;end++){if (end == chars.length || chars[end] == ' '){//每次到单词间空格 或者字符串末尾 就反转 (字符串末尾没有空格reverse(chars, start, end - 1);start = end + 1;}}}
}

三、总结

1.难点：不会处理单词之间的空格，因为只保留一个，其余去除；

2.java中另外三种解法不是很明白；

3.去除空格的代码思路好难想。。