文章目录
557. 反转字符串中的单词 III
题目概述:
给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例:
输入:"Let's take LeetCode contest"
输出:"s'teL ekat edoCteeL tsetnoc"
提示:
在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。
算法思路:
1. 双指针
算法补充:异或
-
java中异或用 ‘’^‘’ 表示,异或的规律是相同为零,不同为1。所以在字符交换的时候可以用异或来进行巧解
-
例如左边的数为11,右边的数为9,分别转换成二进制表示: 11 = 1011, 9 = 1001 1011****1001 1011 ^ 1001 = 0010(0010****1001) 1001 ^ 0010 = 1011(0010****1011) 0010 ^ 1011 = 1001(1001****1011)
算法步骤
- 根据题目要求,要每个单词反转,所以可以根据这个条件来做条件判断。
- 遍历字符串,设置快指针与慢指针,快指针在遇到空格时,利用异或算法,反转当前单词,同时反转之后,慢指针指向快指针的下一位。
代码实现:
public String reverseWords(String s) {
char[] chars = s.toCharArray();
int len = chars.length;
int left = 0;
int right = 0;
while(right <= len){
if(right == len || chars[right] == ' '){
int i = left;
int j = right - 1;
while(i < j){
chars[i] ^= chars[j];
chars[j] ^= chars[i];
chars[i] ^= chars[j];
i++;
j--;
}
left = right + 1;
}
right++;
}
return new String(chars);
}
复杂度分析:
- 时间复杂度:O(n),其中n为数组s的长度
- 空间复杂度:O(n),chars数组