LeetCode 344 反转字符串[三] | Java 刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]输入：address = "1.1.1.1"
输出："1[.]1[.]1[.]1"
复制代码

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
复制代码

思路分析

很多人可能会使用reverse，也就是将本道题的核心使用 Java API 一步解决，这肯定不是面试官想看到的答案，在判断能否使用 Api 来求解算法题的时候有个标准，就是这个 API 有没有简单粗暴的将核心逻辑代替。第一种解法是使用双指针解法，分别将头指针和尾指针的值进行调换，该解法的时间复杂度是 ${O(n)}$ ，空间复杂度也是 ${O(1)}$ 。

还有一种解法也是使用双指针解法，题目中提到，数组中的所有字符都是 ASCII 码表中的可打印字符。也就是说可以使用异或运算，运算速度更快。我们需要先了解异或：

异或运算（⊕）有以下三个性质：

任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
任何数和其自身做异或运算，结果是 0，即 a ⊕ a = 0。
异或运算满足交换律和结合律，即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a)= b ⊕ 0 = b。

该解法的时间复杂度是 ${O(n)}$ ，空间复杂度也是 ${O(1)}$ 。

代码展示

解法一：使用双指针，不断交换头尾指针的值，时间复杂度是 ${O(n)}$ ，空间复杂度也是 ${O(1)}$ 。

 public void reverseString(char[] s) {
     if(s == null){
         return;
     }
     int length = s.length;
     int right = length - 1;
     int left = 0;
     while(left < right){
         char temp = s[left];
         s[left] = s[right];
         s[right] = temp;
         left++;
         right--;
     }
 }
复制代码

解法二：也是使用双指针，不断交换头尾指针的值，但是这里使用的是异或运算，加快计算速度。时间复杂度是 ${O(n)}$ ，空间复杂度也是 ${O(1)}$ 。

    public void reverseString(char[] s) {
        if(s == null){
            return;
        }
        int length = s.length;
        int right = length - 1;
        int left = 0;
        while(left < right){
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];

            left++;
            right--;
        }
    }
复制代码