文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析:本题自己写了一个swap函数,用来反转字符串,也可以用库函数reverse。然后是用index遍历字符串,步长为2k,if判断剩余的字符数量。(这道题的解法写的不太好,太冗杂了,有待改进,大家仅做参考)。后面还有一个优化版本,看优化版本即可。
程序如下:
class Solution {
public:
string swap(string s) {
for (int i = 0, j = s.size() - 1; i < s.size() / 2; ++i, --j) {
s[i] ^= s[j]; // ^位运算当中的异或算子
s[j] ^= s[i];
s[i] ^= s[j];
}
return s;
}
string reverseStr(string s, int k) {
string str;
for (int index = 0, leftover = s.size(); leftover > 0; index += 2 * k, leftover = s.size() - index) {
if (leftover < k) {
str.append(swap(s.substr(index, leftover)));
break; // 剩余字符小于k,全部反转,然后退出循环
}
else {
str.append(swap(s.substr(index, k)));
if (leftover >= 2 * k) str.append(s.substr(index + k, k)); // 剩余字符大于2k的情况
else str.append(s.substr(index + k, leftover - k)); // 剩余字符大于k,小于2k的情况
}
}
return str;
}
};
优化过的程序:
class Solution {
public:
void my_swap(string &s, int start, int end) {
for (int i = start, j = end; i < j; ++i, --j) {
s[i] ^= s[j]; // ^位运算当中的异或算子
s[j] ^= s[i];
s[i] ^= s[j];
// swap(s[i],s[j]); // 调用库函数
}
}
string reverseStr(string s, int k) {
for (int index = 0; index < s.size(); index += 2 * k) {
if (index + k <= s.size() - 1) {
my_swap(s, index, index + k - 1);
}
else {
my_swap(s, index, s.size() - 1);
}
}
return s;
}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( n ) O(n) O(n),使用了额外空间str。
三、完整代码
# include <iostream>
# include <string>
using namespace std;
class Solution {
public:
string swap(string s) {
for (int i = 0, j = s.size() - 1; i < s.size() / 2; ++i, --j) {
s[i] ^= s[j]; // ^位运算当中的异或算子
s[j] ^= s[i];
s[i] ^= s[j];
}
return s;
}
string reverseStr(string s, int k) {
string str;
for (int index = 0, leftover = s.size(); leftover > 0; index += 2 * k, leftover = s.size() - index) {
if (leftover < k) {
str.append(swap(s.substr(index, leftover)));
break; // 剩余字符小于k,全部反转,然后退出循环
}
else {
str.append(swap(s.substr(index, k)));
if (leftover >= 2 * k) str.append(s.substr(index + k, k)); // 剩余字符大于2k的情况
else str.append(s.substr(index + k, leftover - k)); // 剩余字符大于k,小于2k的情况
}
}
return str;
}
};
int main()
{
int k = 2;
string s = "abcdefg";
Solution s1;
cout << "目标字符串:\n" << s << endl;
string str = s1.reverseStr(s, k);
cout << "翻转后的字符数组:\n" << str << endl;
system("pause");
return 0;
}
end