LeetCode 344. Reverse String [Easy]

发表于 2019-04-26 更新于 2024-08-05 分类于 LeetCode ， Easy 阅读次数：

翻转字符串。

题目来源：https://leetcode.com/problems/reverse-string

题目难度：Easy

解答1[Java]：

核心思想

双指针，保存数组索引，一个指向头，一个指向尾，两者向中间靠拢。当第一个指针的值小于第二个指针的值时交换两个指针指向的值。

代码

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while(left < right){
            swap(s, left, right);
            ++left;
            --right;
        }
    }

    private void swap(char[] arr, int a, int b) {
        if (a == b) {
            return;
        }
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

解答2[Java]：

核心思想

要交换的两个元素的数组下标值之和为 s.length-1。

只需要遍历前一半的元素即可，也就是 s.length/2。如果数组长度为偶数，正好是前一半；如果数组长度为奇数，那么正好是前一半但不包括最中间的元素，最中间的元素不需要交换。

代码

class Solution {
    public void reverseString(char[] s) {
        int len = s.length;
        for (int i = 0; i < len / 2; ++i) {
            swap(s, i, (len - 1) - i);
        }
    }

    private void swap(char[] arr, int a, int b) {
        if (a == b) {
            return;
        }
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

须注意的地方

边界条件写成 i < len / 2，这样可以省去空数组检查，如果写成 i <= len / 2，当数组为空时，访问 s[0] 就会发生数组越界异常。

补充：是否可以用异或的方式交换两个值？

是否可以用异或的方式交换两个值？答案是可以，但是有例外情况。

是否建议使用异或的方式？答案是不建议。

交换两个元素的值，网上有些文章会说可以采用异或的方式来交换。这种方式可以，但是当交换的两个值相同的时候就会都变成零。从效率角度来讲，使用异或的方式，因为是位运算，我们可能以为效率更高，但实际上并不比使用临时变量效率更高。

使用异或交换变量的方式如下：

1
2
3

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

可以使用一个表格来解释一下：

	a	b
初始值	a	b
a = a ^ b 之后	a ^ b	b
b = a ^ b 之后	a ^ b	a ^ b ^ b = a
a = a ^ b 之后	a ^ b ^ a = b	a
结果	b	a

为什么使用临时变量效率更高？

简单来讲：

编译器会对使用临时变量这种方式进行优化；使用异或的方式，编译器无法进行优化。
可以很好地利用现代计算机的指令并行计算体系

如果要讲的详细，要讲很多内容，推荐参考别的文章：

用异或来交换两个变量是错误的 - 陈硕这篇文章讲的很细，推荐阅读。

维基百科中也有讲到：

Most modern compilers can optimize away the temporary variable in the three-way swap, in which case it will use the same amount of memory and the same number of registers as the XOR swap and is at least as fast, and often faster. In addition to that, the XOR swap is completely opaque to anyone unfamiliar with the technique.

解答1[Java]：

核心思想

代码

解答2[Java]：

核心思想

代码

须注意的地方

补充：是否可以用异或的方式交换两个值？

为什么使用临时变量效率更高？

参考资料