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"]
思路分析
双指针法反转数组
参考代码
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) { int i = 0; for(; i < s.size();i+=2*k){ if(i+k<s.size()) {//如果每次剩余的字符>k,那么就可以进行反转前k个 reverse(s.begin()+i,s.begin()+i+k); }else{//如果不够k个,则反转剩余的全部 reverse(s.begin()+i,s.end()); } } 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
方法二:字符串拼接
定义一个字符串变量,如果是非空格字符则直接进行拼接,如果是空格则拼接上%20. 虽然是最普通的方法,但是这个效率还蛮高的,嘿嘿
参考代码
方法一:双指针
#include<bits/stdc++.h> using namespace std; string replaceSpace(string s) { int j,k,cnt = 0; for(int i = 0;i < s.size();i++){ if(s[i]==' '){ cnt++; } } j = s.size()-1; k = s.size()+cnt*2-1; //进行扩容 s.resize(s.size()+cnt*2) ; //从后往前进行遍历 while(j<k) { if(s[j]!=' '){ s[k] = s[j];//不是空格,则将元素放在指定位置 j--; k--; }else{//为空格,则替换空格为%20 s[k] = '0'; s[k-1] = '2'; s[k-2] = '%'; j--; k-=3; } } return s; }
方法二:字符串拼接
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 B
示例 5：
输入：s = "Alice does not even like bob" 输出："bob like even not does Alice"
思路分析
提高一下题目的难度:不要使用辅助空间,空间复杂度要求为O ( 1 ) O(1)O(1)
解题思路:
移除多余空格
将整个字符串反转
将每个单词反转
举个栗子,源字符串为："the sky is blue "
移除多余空格 : “the sky is blue”
字符串反转：“eulb si yks eht”
单词反转：“blue is sky the”
这样我们就完成了翻转字符串里的单词。
但是如何去除单词间的空格呢?
身为菜鸡的我想到的是循环+判断+erase() ,但是要知道erase()的时间复杂度也是O(n),从而也就导致了整体时间复杂度为O(n^2);
想一下我们还有其他办法降低时间复杂度嘛,突然,灵光一现,俺想到了之前数组篇章的—去除数组中指定元素,我们采用的是双指针 ,从而移除空格这个方法就搞定了!
**注意:**由于自带的reverse无法满足我们对字符串中的子串进行反转,所以我们需要自定义reverse方法.
参考代码
#include<bits/stdc++.h> using namespace std; //移除空格方法 void removeExtraSpaces(string& s) { int slow = 0,fast = 0; //移除字符串前面的空格 while(fast<s.size() && s[fast]==' ') {// a good example fast++; } //移除字符串中间的空格 while(fast<s.size()) { if(fast>=1&&s[fast]==' '&&s[fast-1]==' ') { //fast>=1 fast++; } else { s[slow] = s[fast]; slow++; fast++; } } //移除字符串后面的空格(如果有则肯定是一个) if(slow-1>=0&&s[slow-1]==' ') { s.resize(slow-1);//如果最后一个字符是空格 } else { s.resize(slow);//如果最后一个字符不是空格 } } //反转字符串 时间复杂度O(N) void reverse(string& s,int i,int j) { while(i<j) { swap(s[i],s[j]); i++; j--; } } string reverseWords(string s) { removeExtraSpaces(s);//移除空格 reverse(s,0,s.size()-1);//整体反转 int i = 0,j; while(i<s.size()) {//反转单词 j = i; while(j<s.size()&&s[j]!=' '){//寻找空格的位置 j j++; } reverse(s,i,j-1);//反转单词 i = j+1;//更新i } return s; }
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
题目描述
示例 1：
输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
思路分析
方法一
直接进行字符串截取,然后拼接在一块就行(毫无技术含量)
方法二
我们再次成为大佬,提高下难度:不能申请额外空间，只能在本串上操作
做法:局部+整体反转
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
参考代码
#include<bits/stdc++.h> using namespace std; //手动实现的reverse void reverse(string& s,int begin,int end) { while(begin<end){ swap(s[begin],s[end]) ; begin++; end--; } } //其中可以手动实现个reverse string reverseLeftWords(string s, int n) { // reverse(s.begin(),s.-()+n); // reverse(s.begin()+n,s.end()); // reverse(s.begin(),s.end()); reverse(s,0,n-1) ; reverse(s,n,s.size()-1) ; reverse(s,0,s.size()-1 ; return s; }
28. 实现 strStr()
题目描述
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
输入：haystack = "hello", needle = "ll" 输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba" 输出：-1
示例 3：
输入：haystack = "", needle = "" 输出：0
思路分析
纯正的KMP算法,不懂的可以看我这篇博客
求Next()数组的方法.
参考代码
//haystack:文本串 needle:模板串 void getNext(int* Next,const string& s) { int i = 1,j = 0;//初始化i,j Next[0] = 0; for(; i<s.size(); i++) { //寻找相同字符 while(j>0&&s[i]!=s[j]) {//如果s[i] 和s[j] 不相等,则j进行后退当上一个公共前缀位置,直到相等或者j=0(也就是无法继续后退) j = Next[j-1]; } if(s[i]==s[j]) { //判断后退之后的两个字符是否相等 j++; } Next[i] = j;//更新Next. } } //haystack:文本串 needle:模板串 int strStr(string haystack, string needle) { int Next[needle.size()] ;//定义Next数组 getNext(Next,needle);//初始化 int j = 0,i = 0; for(; i<haystack.size(); i++) { //如果不相等,则模板串调到最长公共前缀的下一个位置 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;//没有找到则返回-1 }
459. 重复的子字符串
题目描述
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab" 输出: True
解释: 可由子字符串 “ab” 重复两次构成。
示例 2:
输入: "aba" 输出: False
示例 3:
输入: "abcabcabcabc" 输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
思路分析
KMP算法的经典使用 外加一点小技巧
假设数组长度为len,如果len % (len - next[len - 1]) == 0 ,则说明字符串有重复的子字符串.
为什么呢?
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
我们看一下Next数组就很清楚了,如下:
**分析:**在第一个周期内next[x]=0,当走出第一个周期后next[i]>0,所以如果该字符串可以由某一个子串组成,那么len - next[len - 1] 一定会被len整除的.
参考代码
#include<bits/stdc++.h> using namespace std; void getNext(int* Next,const string& s){ int i = 1,j = 0;//定义及 初始化 Next[0] = 0; for(;i<s.size();i++) { while(j>0&&s[i]!=s[j]){//如果不相等,则j进行后退当上一个公共前缀位置,直到相等或者j=0(也就是无法继续后退) j = Next[j-1]; } //判断是否相等 if(s[i]==s[j]) { j++; } //更新Next[i] Next[i] = j; } } bool repeatedSubstringPattern(string s) { //主要思想是:字符串长度 % (字符串长度-最长公共前缀 ) = 0,则说明出现重复的子字符串 int len = s.size(); int Next[len] ;//定义Next数组 getNext(Next,s) ; if(Next[len-1]&&len % (len - Next[len-1])==0){ return true; } return false; } int main(){ string str = "abababaaba"; cout<<repeatedSubstringPattern(str)<<endl; return 0; }
总结
OK，今天关于字符串算法整理就到这里的，希望本篇文章能够帮助到大家，同时也希望大家看后能学有所获！！！
好了，我们下期见~
