8.Rotate String
题解1:
class Solution {
public:
/**
* @param str: An array of char
* @param offset: An integer
* @return: nothing
*/
void rotateString(string &str, int offset) {
string t_str;
int len = str.length();
if (len == 0 || offset == 0)return;
int new_offset = offset % len;
int j = len - 1;
for (int i = 0; i< new_offset; i++)
{
t_str.insert(0,1 ,str[j]);
j--;
}
if (new_offset == 0)new_offset = len;
for (int i=0;i!=j+1;i++)
{
t_str.push_back(str[i]);
}
for (int i = 0; i < len; i++)
{
str[i] = t_str[i];
}
}
};
没能想出空间复杂度O(1)的题解
所以就直接暴力解了,复杂度勉强能接受
反思:
- 一开始没看清题目就直接编程,以为offset表示的是字符串的从0开始的下标,其实不然,实际题目的要求是把 offset%len 个末尾字符移动到前面. 就这一点卡了很久,所以正确理解题目很关键,不要急于码代码.
- 当 offset > len 时,可以通过 offset%len处理一下,避免重复的循环
题解2
class Solution {
public:
/**
* @param str: An array of char
* @param offset: An integer
* @return: nothing
*/
void rotateStr(string &str,int left,int right)
{
while (left < right)
{
char tc = str[left];
str[left] = str[right];
str[right] = tc;
left++;
right--;
}
}
void rotateString(string &str, int offset) {
int len = str.length();
if(len == 0)return;
int new_offset = offset % len;
rotateStr(str, 0, len-new_offset-1);
rotateStr(str, len-new_offset, len-1);
rotateStr(str, 0, len-1);
}
};
反思
- 第二次刷仍然犯了第一次的错误,实际题目的要求是把 offset%len 个末尾字符移动到前面
- 实现原理是1 翻转左边 2 翻转右边 3 翻转整个字符串
处理时间稍微优化了下,实现了O(1)的空间复杂度