同系列文章导读:【数据结构与算法】导读
所有文章均在本博客首发,其他平台同步更新
如果有更好的方法,欢迎指点,共同进步~~
有其他语言代码也可在留言区留言,谢谢
发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】
- 时间:2022-05-27
- 题目序号:344
- 难度:简单
问题描述
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
来源:力扣(LeetCode)
示例1
输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]
示例2
输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
提示
1 <= s.length <= 105
s[i]
都是 ASCII 码表中的可打印字符
解题思路
题解部分参考自代码随想录。如有侵权,请联系进行删除~~
- 本题采用双指针进行字符串的反转,字符串也可以看作是数组
- 比较容易想得到,一个指针指向0,一个指向length - 1
- 每次交换两指针指向的字符,前指针后移,后指针前移
- 在进行交换时,可以采用两种方式
- 一种是常见的temp中间变量法,一种是通过位运算
中间变量法
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
位运算法
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
两种方法比较来说,位运算法虽然不易理解,但是不需要开辟新的空间,更推荐使用
代码实现
class Solution {
public void reverseString(char[] s) {
int j = s.length - 1;
for(int i = 0; i < j; i++){
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
j--;
}
}
}
总结
- 在进行两数交换时,都可以采用中间变量或者位运算来实现
- 位运算不需要开辟新的空间,所以更推荐使用位运算实现两数交换