344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
思路分析
双指针法
使用两个指针l,和r,一个在最左边一个在最右边,每次交换两个位置的内容,直至l=r结束移动.
参考代码
//双指针法 void reverseString(vector<char>& s) { int l = 0; int r = s.size()-1; int temp; while(l<r){ temp = s[l]; s[l] = s[r]; s[r] = temp; l++; r++; } }
541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2 输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2 输出："bacd"
思路分析
这个题和上题思路一样.具体思路如下:
- 每2k个字符长度,反转前k个的字符==> 这也就决定了i每一轮的增量是2k
- 如果不够2k但大于k则反转前k个.
- 如果剩余的小于k,则全部进行反转.
参考代码
string reverseStr(string s, int k) { //每次i向后移动2k个单位长度 //如果剩余少于k,则将剩余全部反转 // 如果剩余字符小于2k但大于等于k,则反转前k个字符 for(int i = 0;i < s.size();i += 2*k){ if(i+k <= s.size()){//如果剩余字符小于2k但大于等于k,则反转前k个字符 reverse(s.begin()+i,s.begin()+i+k); continue; } reverse(s.begin()+i,s.end());//如果剩余少于k,则将剩余全部反转 } return s; }
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy." 输出："We%20are%20happy."
方法一:双指针
由于C++ 的string底层维护的也是一个字符数组.我们知道数组元素的删除和插入有时候会导致所有元素都向后移动,这样很花费时间.所有我们可以提前统计字符串中的空格,然后为字符串重新到最终需要的空间.
处理时我们使用快慢指针,从后往前一边将空格转换成%20,一边将元素放在对应的位置.最终返回字符串即可.
算法步骤:
- 统计字符串s中的空格个数:cnt
- 为s重新分配更大的空间:s.size()+cnt*2
- 定义两个指针i,j从后往前,一边将空格转换成%20,一边将元素放在对应的位置
- 返回字符串s
参考代码1
//双指针法 string replaceSpace(string s) { int cnt = 0;//统计字符串中的空格个数 int len1 = s.size(); for(int i = 0;i < len1;i++){ if(s[i]==' '){ cnt++; } } s.resize(len1+cnt*2); //从后往前替换成 %20 for(int i = len1-1,j = s.size()-1; i < j; i--){//i遍历老串的每一个字符 if(s[i]!=' '){ s[j] = s[i]; j--; }else{ s[j] = '0'; s[j-1] = '2'; s[j-2] = '%'; j-=3; } } return s; }
方法二:字符串拼接
定义一个字符串变量,如果是非空格字符则直接进行拼接,如果是空格则拼接上%20. 虽然是最普通的方法,但是这个效率还蛮高的,嘿嘿
参考代码2
string replaceSpace(string s) { string ans=""; for(int i = 0;i < s.size();i++){ if(s[i]!=' '){ ans+=s[i]; }else{ ans +="%20"; } } return ans; }
151. 翻转字符串里的单词
给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。
示例 1：
输入：s = "the sky is blue" 输出："blue is sky the"
示例 2：
输入：s = " hello world " 输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
示例 3：
输入：s = "a good example" 输出："example good a"
示例 4：
输入：s = " Bob Loves Alice " 输出："Alice Loves Bob"
示例 5：
输入：s = "Alice does not even like bob" 输出："bob like even not does Alice"
菜鸡做法
本题对字符串考察的很综合,是一个很不错的题目!!!
使用split()函数,定义一个新字符串,然后把字符串倒叙相加,
但是这样的话,好像配不上中等题的标签了,这道题核心就是去空格,倒叙,拼接,结果你直接把split()就完成了最难的工作.除非是在实在没有其他思路时可以试一下这个方法.毕竟最核心的不要直接用库搞定…
参考代码1
明日补充…
方法二
我们可以尝试一下成为大佬,提高一下题目的难度:不要使用辅助空间,空间复杂度要求为O ( 1 ) O(1)O(1)
所以解题思路:
移除多余空格
将整个字符串反转
将每个单词反转
举个栗子,源字符串为："the sky is blue "
移除多余空格 : “the sky is blue”
字符串反转：“eulb si yks eht”
单词反转：“blue is sky the”
这样我们就完成了翻转字符串里的单词。
但是如何去除单词间的空格呢?
下面是菜鸡的做法:哎,菜鸡到凤凰,哪能一夜之间就变呢?
void removeExtraSpaces(string& s) { for (int i = s.size() - 1; i > 0; i--) { if (s[i] == s[i - 1] && s[i] == ' ') { s.erase(s.begin() + i); } } // 删除字符串最后面的空格 if (s.size() > 0 && s[s.size() - 1] == ' ') { s.erase(s.begin() + s.size() - 1); } // 删除字符串最前面的空格 if (s.size() > 0 && s[0] == ' ') { s.erase(s.begin()); } }
但是呢,兄弟们,erase的复杂度是O(n),因为字符串的底层也是字符数组呢.而且外部还有一个for循环,所以整体时间复杂度为:O ( n 2 )
所以最好的办法是 使用双指针来去除空格,然后resize一下字符串的大小,我们就可以做到O(n)的时间复杂度了.
代码如下:
//移除冗余空格,使用双指针(快慢指针)法, 复杂度:O(n) void removeExtraSpaces(string &s){ int slowIndex = 0,fastIndex = 0;//定义快慢指针 //去掉前面的空格 while(s.size()>0&&fastIndex < s.size()&&s[fastIndex]==' '){ fastIndex++; } //去掉字符串中间的冗余空格 for(;fastIndex<s.size();fastIndex++){ if(fastIndex>1&&s[fastIndex-1]==s[fastIndex]&&s[fastIndex]==' '){//s当前:"x "我们只需要从第三个字符判断就可以了. continue; }else{ s[slowIndex++] = s[fastIndex]; } } //去掉末尾字符串并重置字符串大小. if(slowIndex-1>0 && s[slowIndex-1]==' '){//字符串的结束下标是slowIndex-1,而且可能是空格.所以需要去重. s.resize(slowIndex-1); } else{ s.resize(slowIndex);//重置字符串大小. 字符串的底层是一个字符数组. } }
参考代码2
//字符串反转 void reverse(string& s,int start,int end){ for(int i = start,j = end;i<j;i++,j--){ swap(s[i],s[j]); } } //移除冗余空格,使用双指针(快慢指针)法, 复杂度:O(n) void removeExtraSpaces(string &s){ int slowIndex = 0,fastIndex = 0;//定义快慢指针 //去掉前面的空格 while(s.size()>0&&fastIndex < s.size()&&s[fastIndex]==' '){ fastIndex++; } //去掉字符串中间的冗余空格 for(;fastIndex<s.size();fastIndex++){ if(fastIndex>1&&s[fastIndex-1]==s[fastIndex]&&s[fastIndex]==' '){//s当前:"x "我们只需要从第三个字符判断就可以了. continue; }else{ s[slowIndex++] = s[fastIndex]; } } //去掉末尾字符串并重置字符串大小. if(slowIndex-1>0 && s[slowIndex-1]==' '){//字符串的结束下标是slowIndex-1,而且可能是空格.所以需要去重. s.resize(slowIndex-1); } else{ s.resize(slowIndex);//重置字符串大小. 字符串的底层是一个字符数组. } } string reverseWords(string s) { removeExtraSpaces(s); reverse(s,0,s.size()-1);//反装整个字符串 for(int i = 0;i < s.size();i++){ int j = i; //查找单词间的空格, while(j<s.size()&&s[j]!=' '){ j++; } //j位置是空格 reverse(s,i,j-1); i = j;//重新赋值而且i++,下一次i从j+1开始,也就是下一个单词开始. } return s; }
