反转字符串【LC344】
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路[双指针法]
//2021/11/9 class Solution { public void reverseString(char[] s) { int len = s.length; for (int l=0;l<len/2;l++){ char temp = s[l]; s[l] = s[len-l-1]; s[len-1-l] = temp; } } }
- 复杂度分析
- 时间复杂度：O(N)，其中 N为字符数组的长度。一共执行了 N/2次的交换。
- 空间复杂度：O(1)。只使用了常数空间来存放若干变量
- 通过位运算实现swap
class Solution { public void reverseString(char[] s) { int l = 0; int r = s.length - 1; while (l < r) { s[l] ^= s[r]; //构造 a ^ b 的结果，并放在 a 中 s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b s[l] ^= s[r]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换 l++; r--; } } }
