代码随想录刷题题Day7
刷题的第七天,希望自己能够不断坚持下去,迎来蜕变。😀😀😀
刷题语言:C++ / Python
Day7 任务
● 344.反转字符串
● 541. 反转字符串II
● 卡码网:54.替换数字
● 151.翻转字符串里的单词
● 卡码网:55.右旋转字符串
1 反转字符串
如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数,如果库函数仅仅是解题过程中的一小部分,并且已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。
本题考虑双指针
伪代码:
len = s.size();
for(i = 0, j = len - 1 ; i < len / 2; i++, j--)
swap(s[i], s[j]);
C++:
class Solution {
public:
void reverseString(vector<char>& s) {
int len = s.size();
for (int i = 0, j = len - 1; i < len / 2; i++, j--)
{
swap(s[i], s[j]);
}
}
};
或者:
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while (left < right)
{
swap(s[left], s[right]);
left++;
right--;
}
}
};
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
O(1)
Python:
class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
2 反转字符串II
在遍历字符串的过程中,只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间
当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章
伪代码:
for (i = 0; i < s.size(); i += 2k)
{
if (i + k <= s.size())
{
reverse(s, i, i + k);
continue;
}
reverse(s, i, s.size());
}
C++中的reverse()函数
C++:
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += 2 * k)
{
if (i + k <= s.size())
{
reverse(s.begin() + i, s.begin() + i + k);
continue;
}
reverse(s.begin() + i, s.end());
}
return s;
}
};
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
O(1)
Python:
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
def reverse_substring(text):
left, right = 0, len(text) - 1
while left < right:
text[left], text[right] = text[right], text[left]
left += 1
right -= 1
return text
res = list(s)
for i in range(0, len(s), 2 * k):
res[i : i + k] = reverse_substring(res[i : i + k])
return ''.join(res)
3 替换数字
把这道题目做到极致,就不要只用额外的辅助空间
思路:
首先扩充数组到每个数字字符替换成 “number” 之后的大小
然后从后向前替换数字字符,也就是双指针法,过程如下:i指向新长度的末尾,j指向旧长度的末尾
从前向后填充就是 O ( n 2 ) O(n^2) O(n2)的算法,因为每次添加元素都要将添加元素之后的所有元素整体向后移动
很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作
好处:(1)不用申请新数组(2)从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题
伪代码:
while (cin >> s)
{
count = 0;
oldSize = s.size();
for (i = 0; i < s.size(); i++)
{
if (s[i] >= '0' && s[i] <= '9')
count++;
}
}
s.resize(s.size() + count * 5);
newSize = s.size();
for (i = newSize - 1, j = oldSize - 1; j < i; i--, j--)
{
if (s[i] > '9' || s[i] < '0')
s[i] = s[j];
else
{
s[i] = 'r';
s[i - 1] = 'e';
s[i - 2] = 'b';
s[i - 3] = 'm';
s[i - 4] = 'u';
s[i - 5] = 'n';
i -= 5;
}
}
cout << s << endl;
C++:
#include <iostream>
using namespace std;
int main()
{
string s;
while (cin >> s)
{
int oldSize = s.size();
int count = 0;
for (auto i : s)
{
if (i >= '0' && i <= '9')
{
count++;
}
}
s.resize(s.size() + count * 5);
int newSize = s.size();
for (int i = newSize - 1, j = oldSize - 1; j < i; i--, j--)
{
if (s[j] < '0' || s[j] > '9') s[i] = s[j];
else
{
s[i] = 'r';
s[i - 1] = 'e';
s[i - 2] = 'b';
s[i - 3] = 'm';
s[i - 4] = 'u';
s[i - 5] = 'n';
i -= 5;
}
}
cout << s << endl;
}
}
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
O(1)
拓展:
双指针方法:
(1)移除元素
(2)三数之和
(3)四数之和
(3)翻转链表
(4)环形链表II
(5)反转字符串
字符串和数组的区别:
C语言中,把一个字符串存入一个数组时,也把结束符 '\0’存入数组,并以此作为该字符串是否结束的标志
char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {}
在C++中,提供一个string类,string类会提供 size接口,可以用来判断string类字符串是否结束,就不用’\0’来判断是否结束。
string a = "asd";
for (int i = 0; i < a.size(); i++) {}
翻转字符串里的单词
思路:
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
例子:
源字符串为:"the sky is blue "
(1)移除多余空格:“the sky is blue”
(2)将整个字符串反转:“eulb si yks eht”
(3)单词反转:“blue is sky the”
使用双指针法来去移除空格,最后resize(重新设置)一下字符串的大小,就可以做到O(n)的时间复杂度
伪代码:
// 去除所有空格并在相邻单词之间添加空格, 快慢指针
slow = 0;
for (fast = 0; fast < s.size(); fast++)
{
if (s[fast] != ' ') // 遇到非空格就处理,即删除所有空格
{
if (slow != 0) s[slow++] = ' ';//手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格
while (fast < s.size() && s[fast] != ' ')// 补上该单词,遇到空格说明单词结束
{
s[slow++] = s[fast++];
}
}
}
s.resize(slow);//slow的大小即为去除多余空格后的大小
reverse(s, 0, s.size() - 1);
int start = 0;//removeExtraSpaces后保证第一个单词的开始下标一定是0
for (i = 0; i <= s.size(); i++)
{
if (i == s.size || s[i] == ' ')// 到达空格或者串尾,说明一个单词结束。进行翻转
{
reverse(s, start, i - 1);// 翻转,注意是左闭右闭 []的翻转
start = i + 1;// 更新下一个单词的开始下标start
}
}
return s;
C++:
class Solution {
public:
void reverse(string& s, int start, int end)// 翻转,区间写法:左闭右闭 []
{
for (int i = start, j = end; i < j; i++, j--)
{
swap(s[i], s[j]);
}
}
// 去除所有空格并在相邻单词之间添加空格, 快慢指针
void removeExtraSpace(string& s)
{
int slow = 0;
for (int fast = 0; fast < s.size(); fast++)
{
if (s[fast] != ' ') //遇到非空格就处理,即删除所有空格
{
if (slow != 0) s[slow++] = ' ';// 手动控制空格,给单词之间添加空格
while (fast < s.size() && s[fast] != ' ')
{// 补上该单词,遇到空格说明单词结束
s[slow++] = s[fast++];
}
}
}
s.resize(slow);// slow的大小即为去除多余空格后的大小
}
string reverseWords(string s) {
removeExtraSpace(s);// 去除多余空格,保证单词之间之只有一个空格,且字符串首尾没空格
reverse(s, 0, s.size() - 1); // 翻转s
int start = 0;//removeExtraSpaces后保证第一个单词的开始下标一定是0
for (int i = 0; i <= s.size(); i++)
{
if (i == s.size || s[i] == ' ')// 到达空格或者串尾,说明一个单词结束。进行翻转
{
reverse(s, start, i - 1);// 翻转,注意是左闭右闭 []的翻转
start = i + 1;// 更新下一个单词的开始下标start
}
}
return s;
}
};
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
O(1) 或
O
(
n
)
O(n)
O(n)
class Solution {
public:
void removeExtraSpace(string& s)
{
int slow = 0;
for (int fast = 0; fast < s.size(); fast++)
{
if (s[fast] != ' ')
{
if (slow != 0) s[slow++] = ' ';
while (fast < s.size() && s[fast] != ' ')
{
s[slow++] = s[fast++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
removeExtraSpace(s);
reverse(s.begin(), s.end());
int start = 0;
for (int i = 0; i <= s.size(); i++)
{
if (i == s.size() || s[i] == ' ')
{
reverse(s.begin() + start, s.begin() + i);
start = i + 1;
}
}
return s;
}
};
Python:
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
# 将字符串拆分为单词,即转换成列表类型
words = s.split()
left, right = 0, len(words) - 1
# 反转单词
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
# 将列表转换成字符串
return " ".join(words)
5 右旋转字符串
思路:
通过整体倒序,在将两段子串顺序颠倒
C++:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string s;
int k;
cin >> k >> s;
reverse(s.begin(), s.end());
reverse(s.begin(), s.begin() + k);
reverse(s.begin() + k, s.end());
cout << s << endl;
return 0;
}
先局部反转,再整体反转
C++:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string s;
int k;
cin >> k >> s;
int len = s.size();
reverse(s.begin(), s.begin() + len - k);
reverse(s.begin() + len - k, s.end());
reverse(s.begin(), s.end());
cout << s << endl;
return 0;
}
鼓励坚持八天的自己😀😀😀
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!