章丘营销型网站建设,创客贴网页设计网站,优化关键词排名,wordpress性能差文章目录反转字符串习题双指针swap 的两种方式反转字符串
本节对应代码随想录中#xff1a;代码随想录#xff0c;讲解视频#xff1a;字符串基础操作#xff01; | LeetCode#xff1a;344.反转字符串_哔哩哔哩_bilibili
习题
题目链接#xff1a;344. 反转字符串 - …
文章目录反转字符串习题双指针swap 的两种方式反转字符串
本节对应代码随想录中代码随想录讲解视频字符串基础操作 | LeetCode344.反转字符串_哔哩哔哩_bilibili
习题
题目链接344. 反转字符串 - 力扣LeetCode
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1
输入s [h,e,l,l,o]
输出[o,l,l,e,h]双指针
作为数组的第一题这题还是比较简单的。反转字符串其实就是原来第一个字符变成最后一个字符原来第二个字符变成倒数第二个字符以此类推。那其实就是将第一个与最后一个字符交换将第二个与倒数第二个字符交换以此类推。并且我们只需要遍历字符串一半的长度就行交换即可。
class Solution {public:void reverseString(vectorchar s) {int size s.size();for (int i 0, j size - 1; i size / 2; i, j--) {swap(s[i], s[j]);}}
};时间复杂度O(nnn)。有一个 for 循环它的迭代次数是数组大小的一半即 O(n/2)swap 函数交换了两个元素的值其时间复杂度为 O(1)。因此这个函数的时间复杂度为 O(n/2 * 1)也就是 O(n)空间复杂度O(111)。只使用了常量级别的额外空间存储变量 i、j 和 size因此空间复杂度为 O(1)
对于本题其实使用库函数 reverse 就能解题但显然本题并不是考察库函数的使用面试的时候更不会如此。但是必须要了解可以使用什么库函数来实现代码如下
class Solution {public:void reverseString(vectorchar s) {reverse(s.begin(),s.end());}
};时间复杂度O(nnn)。只调用了一次 C 标准库中的 reverse 函数其时间复杂度为 O(n)其中 n 是数组的大小空间复杂度O(111)。没有使用任何额外的内存来存储变量所以空间复杂度是 O(1)
swap 的两种方式
第一种是比较常见的方式
int tmp s[i];
s[i] s[j];
s[j] tmp;第二种是通过位运算
int a 5; // 101
int b 7; // 111
a ^ b; // 此时 a 的值为 2101^111010
b ^ a; // 此时 b 的值为 5010^111即(101^111)^111101)
a ^ b; // 此时 a 的值为 7010^101即(101^111)^101111解释利用异或运算符的特性一个数异或同一个数两次会得到原始的值这个交换操作不需要临时变量比第一种方法更快尤其是在处理大型数据集时。但要注意的是这种方式只适用于整型数据类型对于其他类型例如浮点数、字符或自定义对象等则需要采用其他方法进行交换。
解题的时候一般的交换元素可以直接用 swap 函数即 swap(a,b)
