字符串
- 代码随想录
-
如果想让这套题目有意义，就不要申请额外空间。
344.反转字符串
- 双指针
// 时间复杂度O(n),执行n/2次交换
// 空间复杂度O(1)
class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
for(int left = 0,right = n-1;left <= right;left++,right--){
swap(s[left],s[right]);
}
}
};
541. 反转字符串II
- 分情况讨论，其实除去剩余字符数量小于k个，将剩余全部反转；
- 大于k个小于2k,与正常反转2k个中的前k个，是相同的(即i+k <= n)，都是反转该子串中的前k个。
// 时间复杂度 O(n)
// 空间复杂度 o(1)-字符串
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
// 先进入循环，然后判断剩余的数量，再分情况讨论。
for(int i = 0 ;i < n;i+=2*k){
if(i + k < n){
// 剩余字符大于k小于2k，其实这种情况就与正常的剩余2k个字符一样，反转当前字符该k个字符
// 反转2k个字符的前k个字符
reverse(s.begin()+i,s.begin()+i+k);
}else{
// 剩余字符小于k个,反转剩余所有字符
reverse(s.begin()+i,s.end());
}
}
return s;
}
};
- 自己实现reverse
- 注意区间控制
// 时间复杂读O(n)
// 空间复杂度O(1)
class Solution {
public:
void myReverse(int begin,int end,string& s){
// 左闭右闭
for(int l = begin,r = end;l <= r;l++,r--){
swap(s[l],s[r]);
}
}
string reverseStr(string s, int k) {
int n = s.size();
for(int i = 0;i < n;i += 2*k){
if(i + k < n){
myReverse(i,i+k-1,s);// 右边界i+k-1
}else{
myReverse(i,n-1,s);
}
}
return s;
}
};
剑指Offer 05.替换空格
- 搜寻空格个数，扩充数组，起两个指针，从后向前遍历，一个指针(慢)指向新开辟数组的最后一个位置，一个指针(快)指向旧数组大小的位置。
- 快指针不为空格，与慢指针交换到最后，反之使用慢指针填充%20。
- 要是用快指针填充，就覆盖前面还没判断的了。
- 填充过程如下图所示:
- 如果从前往后填充，就变成O(n²)的算法了，因为每次添加元素过后都要将后面的元素往后移动。
-
很多数组填充类问题，都可以预先给数组扩容为填充后的大小，然后再从后向前进行操作
- 这么做有两个好处:
- 不用申请新数组
- 从后向前填充元素，避免从前往后填充导致的元素向后移动。
// 时间复杂度 O(n)
// 空间复杂度 O(1)
class Solution {
public:
string replaceSpace(string s) {
int oldSize = s.size();
int count = 0;
for(char& c:s){
if(c == ' ')count++;
}
s.resize(oldSize+2*count);// 注意是2,因为原来的空格是占一个，所以每个空格再扩充2个即可
int newSize = s.size();
for(int slow = newSize-1,fast = oldSize-1;fast < slow;slow--,fast--){
if(s[fast] != ' '){
s[slow] = s[fast];
}else{
s[slow] = '0';
s[slow-1] = '2';
s[slow-2] = '%';
slow -= 2;
}
}
return s;
}
};
151. 反转字符串中的单词
- 空间复杂度O(1)实现思路:
- 去掉多余空格，重新添加空格。
- 整体反转
- 遍历，以单词为整体再次反转。
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
// 反转左闭右闭区间
void myReverse(string& s,int start,int end){
for(int i = start,j = end; i < j;i++,j--){
swap(s[i],s[j]);
}
}
// 去掉多余空格——不能这么删除，这么删，一个空格都不留了
// void removeExSpace(string& s){
// int n = s.size();
// int slow = 0;
// for(int fast = 0;fast < n; fast++){
// if(s[fast] != ' '){
// s[slow++] = s[fast];
// }
// }
// s.resize(slow);
// }
// 去掉多余空格，手动添加正确的空格
// 方法类似于24.移除元素-快慢指针
void removeExSpace(string& s){
int n = s.size();
int slow = 0;
for(int fast = 0; fast < n;fast++){
if(s[fast] != ' '){
if(slow != 0)s[slow++]=' ';//注意是slow，除去第一个单词，在每个单词的前面添加空格。
// 边界控制 fast < n
while(fast < n && s[fast] != ' '){
s[slow++] = s[fast++];
}
}
}
// slow最后停在最后一个字符后，即元素个数。
s.resize(slow);
}
string reverseWords(string s) {
removeExSpace(s);// 去掉多余空格
int n = s.size();
myReverse(s,0,n-1);// 整体反转
// 遍历，按照空格反转每个单词
int slow = 0;
// 注意边界控制，i <= n，是因为要划到最后一个单词。
for(int i = 0;i <= n;i++){
if(i == n || s[i] == ' '){// i== n的意思是反转最后一个单词
myReverse(s,slow,i-1);// 到i-1的意思是，这里是到了空格才开始反转的，前一个就是上一个单词的最后一个字母，myReverse是左闭右闭区间的。
slow = i+1;
}
}
return s;
}
};
- 分开删除前面、中间、后面，多余空格的方法如下所示:
- 双指针删除，O(n)时间复杂度
void removeExSpaceII(string& s){
// 先删除头部多余的空格
int fast = 0;
int slow = 0;
int n = s.size();
while(n > 0 && fast < n && s[fast] == ' ')fast++;
// 删除中间的多余空格
for(;fast < n;fast++) {
if (fast > 0 && s[fast] == s[fast - 1] && s[fast] == ' ') {// 出现多个空格
continue;
} else {
s[slow++] = s[fast];
}
}
// 删除最后的多余空格
if(slow-1 > 0 && s[slow] == ' '){
s.resize(slow-1);
}else{
s.resize(slow);
}
}
剑指Offer58-II.左旋转字符串
- 不申请额外空间,有趣的做法， 如下图所示:
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(),s.begin()+n);
reverse(s.begin()+n,s.end());
reverse(s.begin(),s.end());
return s;
}
};
- 申请额外空间,substr拼接
class Solution {
public:
string reverseLeftWords(string s, int n) {
int _Size = s.size();
string front = s.substr(0,n);
string back = s.substr(n,_Size-n);
return back+front;
}
};
28. 找出字符串中第一个匹配项的下标
- 暴力算法
// 时间复杂度O(n²)
class Solution {
public:
int strStr(string haystack, string needle) {
int hs = haystack.size();
int ns = needle.size();
for(int i = 0; i < hs;i++){
int tmp = i;// 保存开始匹配i的位置
for(int j = 0;j < ns;j++){
if(haystack[i] != needle[j]){
i = tmp;// 将i重置回去
break;
}else{
if(j == ns-1)return tmp;// 相等并且已经到达结尾模式串结尾
i++;// 继续走
}
}
}
return -1;
}
};
- KMP算法
- KMP算法相关补充——【KMP】KMP算法的一些小理解&总结
- 这里仅给出代码实现，详见上述文章中。
// 时间复杂度O(n)
class Solution {
public:
void getNext(int* next,const string s){
int n = s.size();
int j = 0;
next[0] = 0;
// i 为前缀末尾
// j 为后缀末尾
for(int i = 1; i < n ;i++){
while(j > 0 && s[i] != s[j]){// 控制回退，最多回退到开头，即j=0
j = next[j-1];
}
if(s[i] == s[j])j++;
next[i] = j;
}
}
int strStr(string haystack, string needle) {
int next[needle.size()];
// j负责遍历模式串
// i负责遍历文本串
getNext(next,needle);
int j = 0;
for(int i = 0;i < haystack.size();i++){
// 当前这个字符不同，通过移动j指针指向的模式串位置，来调整继续匹配的位置。
while(j > 0 && haystack[i] != needle[j]){
j = next[j-1];
}
if(haystack[i] == needle[j])j++;
if(j == needle.size()){
return i-needle.size()+1;
}
}
return -1;
}
};
459. 重复的子字符串
- 移动匹配
// 时间复杂度 O(n),不确定
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t = s + s;
// 掐头去尾
t.erase(t.begin());
t.erase(t.end()-1);// 注意end指向最后一个元素后
return t.find(s)!=string::npos?true:false;
}
};
- KMP算法
- 详情也请见上题所给出的KMP相关文章链接。
// 时间复杂度O(n)
class Solution {
public:
void getNext(int* next,const string& s){
int j = 0;
next[0] = 0;
for(int i =1; i < s.size();i++){
while(j > 0 && s[i] != s[j]){
j = next[j-1];
}
if(s[i] == s[j])j++;
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
if(s.size() == 0)return false;
int next[s.size()];
getNext(next,s);
int len = s.size();
// next[len-1] == 0就说明，以整体为子串的最长相等前后缀为0。
// 如果是通过某一字串重复得到的，以整体为子串的最长相等前后缀不会为0。
// 最小重复单位如果能被字符串的长度整除，说明该字符串是由重复的子串构成的。
if(next[len-1] != 0 && len % (len-(next[len-1])) == 0)return true;
return false;
}
};
