557. 反转字符串中的单词 III-Java

文章目录

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数组
上一篇:demo02


下一篇:【1011】甲流疫情死亡率