【字符串】【双指针翻转字符串+快慢指针】Leetcode 151 反转字符串中单词【好】

---------------🎈🎈题目链接🎈🎈-------------------
---------------🎈🎈解答链接🎈🎈-------------------

解法1 双指针翻转字符串+快慢指针+更新数组大小

1.翻转全部
2.删除空格(快慢指针) 这部分蛮难思考的

• 当slow不是0（为了排除最前面的一个（一堆）空格）时
  且ch[fast]不是空格，ch[fast-1]是空格的时候————表示一个单词结束，另一个单词开始，此时给slow加空格再进行赋值
• ch[fast]不是空格——不断遍历单词的时候，只需要把fast的值赋给slow即可
• 剩下的就是ch[fast]是空格的时候，那就不操作直接fast++

3.翻转单词

更新数组：char[] newch = Arrays.copyOf(ch, 4);

时间复杂度O(N)

• 翻转全部字符的操作需要遍历整个字符串，时间复杂度为O(n)，其中n是字符串的长度。
• 删除空格的操作也需要遍历整个字符串，时间复杂度为O(n)。
• 翻转单词的操作需要遍历整个字符串，时间复杂度为O(n)。

空间复杂度O(N)

• 使用了一个字符数组ch来存储字符串的字符，空间复杂度为O(n)，其中n是字符串的长度。
• 使用了一个新的字符数组newch来存储删除空格后的字符，空间复杂度为O(n)。
• 没有使用额外的空间，所以除了字符数组外，空间复杂度为O(1)。

class Solution {public String reverseWords(String s) {
class Solution {public String reverseWords(String s) {// 1.翻转全部// 2.删除空格// 3.翻转单词char[] ch = s.toCharArray();// 1.翻转全部int left = 0;int right = ch.length-1;while(left < right){ch[left] ^= ch[right];ch[right] ^= ch[left];ch[left] ^= ch[right];left++;right--;}// 2.删除空格(快慢指针) 更新数组// 慢指针不为0，快指针指向空格 直至遇到下一个字母后 ch[slow++] =' 'int slow = 0;int fast = 0;for(; fast < ch.length; fast++){// 当slow不是0（为了排除最前面的一个（一堆）空格）时，// 且ch[fast]不是空格，ch[fast-1]是空格的时候————表示一个单词结束，另一个单词开始，此时给slow加空格再进行赋值if(slow != 0 && ch[fast] != ' ' && ch[fast-1] == ' '){ ch[slow++] = ' ';ch[slow++] = ch[fast];} // ch[fast]不是空格——不断遍历单词的时候，只需要把fast的值赋给slow即可else if(ch[fast] != ' '){ch[slow++] = ch[fast];}// 剩下的就是ch[fast]是空格的时候，那就不操作直接fast++}char[] newch = Arrays.copyOf(ch, slow); // 更新数组// 3.翻转单词int left2 = 0;for(int i = 0; i <= newch.length; i++){if(i == newch.length || newch[i] == ' ' ){int right2 = i-1;while(left2 < right2){newch[left2] ^= newch[right2];newch[right2] ^= newch[left2];newch[left2] ^= newch[right2];left2++;right2--;}left2 = i+1;}}return new String(newch);}
}