LEETCODE 344. Reverse String 解题思路分析

题目大意：

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

---

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=344

解题思路分析：

这是一道简单题目，不过题目要求使用原地算法，这也就意味着我们不能使用额外的存储空间来辅助解题。对于本题，翻转字符串，实际上就是将数组中相对称的两位上的字符进行交换。解题时，我们定义左右两个指针，初始时，左指针指向0，右指针指向数组最后一位，当左指针小于右指针时保持循环，我们交换左右指针指向的两个字符，然后左指针加一，右指针减一，重复上述步骤直到循环结束。

另外，为了更加节省空间，我们在交换两个字符时可以使用位运算，这样可以省去创建额外变量的空间，之前的文章我们多次介绍过，交换两个字符的值可以通过以下异或运算的代码来实现：

a^=b;
b^=a;
a^=b;

// 普通写法：
int temp = a;
a = b;
b = temp;

实现代码：

public void reverseString(char[] s) {
    // 定义左右两个指针
    int left=0,right=s.length-1;
    while(left<right){
        // 交换两个指针指向的字符
        s[left]^=s[right];
        s[right]^=s[left];
        s[left]^=s[right];
        left++; // 左指针加一
        right--; // 右指针减一
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 96.80% of Java online submissions for Reverse String.

Memory Usage: 43.3 MB, less than 99.41% of Java online submissions for Reverse String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-344-reverse-string-解题思路分析/