- 344. 反转字符串
- 541. 反转字符串 II
- 剑指 Offer 05. 替换空格
- 151. 颠倒字符串中的单词
- 剑指 Offer 58 - II. 左旋转字符串
- 28. 实现 strStr()
- 459. 重复的子字符串
- 总结
1 反转字符串
- 题目链接：344. 反转字符串
1.1 题目描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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”]
1.2 思路
设置两个指针，分别指向vector的头和尾，然后两两进行交换，交换完成则头指针后移、尾指针前移直至二者相遇。
完整代码如下：
Cpp实现
class Solution {
public:
void reverseString(vector<char>& s) {
int l = 0, r = s.size()-1;
while(l < r){
char ch = s[l];
s[l++] = s[r];
s[r--] = ch;
}
}
};C实现
void reverseString(char* s, int sSize){
if(sSize<=1){
return s;
}
int left=0,right=sSize-1;
while(left<right){
s[left]=s[left]^s[right];
s[right]=s[left]^s[right];
s[left]=s[left]^s[right];
left++;right--;
}
return s;
} 2 反转字符串 II
- 题目链接：541. 反转字符串 II
2.1 题目描述
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于 `k`` 个，则将剩余字符全部反转。
- 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
示例1:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”
示例2:
输入: s = “abcd”, k = 2
输出: “bacd”
2.2 思路
简单的模拟，题目给出两个条件：1.剩余字符少于k则全部翻转；2. 剩余字符大于 k 小于 2k 则翻转前 k 个字符。那么就有一种特殊情况，就是k > s.length(), 此时这一题就是反转字符串了；然后进行循环对字符串进行反转，设置两个指针，分别指向待反转子串的起始与结尾，l 和 r，并初始化为0和k-1(即反转前k个字符)，然后进行反转，接着将l 和r 分别加上2k，也就是进行下一组子串的反转，当进入下一个循环前需要先进行判断：如果下一组的l>=s.length 则说明已经反转完成，结束循环；如果下一组的r>=s.length则说明是题目中说的第一种情况(剩余字符少于k)，将r更改为s.length()-1并进行循环。
完整代码如下：
Cpp实现
class Solution {
public:
void reverse(string& s, int l, int r){
while(l < r){
char ch = s[l];
s[l++] = s[r];
s[r--] = ch;
}
}
string reverseStr(string s, int k) {
int len = s.length();
if(len <= 1) return s;
if(k >= len){
reverse(s, 0, len-1);
}else{
int l = 0, r = k-1;
while(1){
reverse(s, l, r);
l += 2*k, r+= 2*k;
if(len <= l){
break;
}else if(len <= r){
r = len-1;
}
}
}
return s;
}
};C实现
char * reverse(char *s, int left, int right){
while(left < right){
s[left] = s[left]^s[right];
s[right] = s[left]^s[right];
s[left] = s[left]^s[right];
left++;right--;
}
return s;
}
char * reverseStr(char * s, int k){
int cnt = strlen(s)/(2*k);
int nubbin = strlen(s)%(2*k);
for(int i = 0; i < cnt; i++){
s = reverse(s, 2*i*k, (2*i+1)*k-1);
}
if(nubbin < k){
s = reverse(s, 2*cnt*k, strlen(s)-1);
}else{
s = reverse(s, 2*cnt*k, (2*cnt+1)*k-1);
}
return s;
} 3 替换空格
- 题目链接：剑指 Offer 05. 替换空格
3.1 题目描述
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例1:
输入: s = “We are happy.”
输出: “We%20are%20happy.”
3.2 思路
遍历s，当当前字符不为空格时直接将当前字符加到答案res后边，否则则在res后边加上"%20"即可。
完整代码如下：
Cpp实现
class Solution {
public:
string replaceSpace(string s) {
string res;
int ptr = 0;
for(char ch: s){
if(ch != ' '){
res += ch;
}else{
res += "%20";
}
}
return res;
}
};C实现
char* replaceSpace(char* s){
char *res = (char *)malloc(sizeof(char)*(3*strlen(s)+1));
int index = 0;
char tmpChar[4] = "%20";
for(int i = 0; i < strlen(s); i++){
if(s[i] != ' '){
res[index++] = s[i];
}else{
res[index++] = '%';
res[index++] = '2';
res[index++] = '0';
//strcat(res, tmpChar);
//index += 3;
}
}
res[index] = '\0';
return res;
}
C实现中记得最后在答案res的末端加上空字符\0, 否则报错.
4 颠倒字符串中的单词
- 题目链接：151. 颠倒字符串中的单词
4.1 题目描述
给你一个字符串 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.2 思路
先将s 的头尾多余的空格去掉，然后遍历s并将当前的字符插入到res中，注意，当单词间出现多余的空格直接continue。遍历完成后，将res翻转，然后遍历res，一遇到空格就将当前的单词翻转。
完整代码如下：
Cpp实现
class Solution {
public:
void reverse(string& s, int l, int r){
while(l < r){
char ch = s[l];
s[l] = s[r];
s[r] = ch;
++l, --r;
}
}
string reverseWords(string s) {
int l = 0, r = s.length() - 1;
while(s[r] == ' '){
--r;
}
while(s[l] == ' '){
++l;
}
string res;
for(int i = l; i <= r; ++i){
if((res.length() && res.back() != ' ') || s[i] != ' '){
res.push_back(s[i]);
}
}
reverse(res, 0, res.length()-1);
l = 0, r= 0;
for(; r < res.length(); r++){
if(res[r] != ' '){
continue;
}
reverse(res, l, r-1);
l = r + 1;
}
reverse(res, l, r-1);
return res;
}
};C实现
char* reverse(char* s, int left, int right){
while(left < right){
s[left] = s[left]^s[right];
s[right] = s[left]^s[right];
s[left] = s[left]^s[right];
left++;
right--;
}
return s;
}
char * reverseWords(char * s){
int slow = 0, fast = 0;
while(s[fast]==' ') fast++;
for(; fast<strlen(s)-1; fast++){ //处理前后、单词间多余的空格
if(s[fast] == ' ' && s[fast+1] ==' '){
continue;
}else{
s[slow++] = s[fast];
}
}
if(s[fast]==' '){
s[slow] = '\0';
}else{
s[slow++] = s[fast];
s[slow] = '\0';
}
reverse(s, 0, slow-1);
int left = 0, right = 0;
while(right < slow){
while(right < slow&&s[right] != ' ') right++;
reverse(s, left, right-1);
right += 1;
left = right;
}
return s;
} 5 左旋转字符串
5.1 题目描述
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例1:
输入: s = “abcdefg”, k = 2
输出: “cdefgab”
示例2:
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”
5.2 思路
三种思路：
- 切片，使用
substr()将s切为两部分，然后进行拼接即可。 - 思路与第一种一样，只是不调用库函数，采用取余的方式
res[i] = s[(i+n)%s.length()],这样就可以把大于n的部分前移n位，小于n的放在最后。 - 进行三次反转，首先翻转
0~(n-1),然后翻转n~(s.length()-1)，最后再对整个字符串进行翻转。
完整代码如下：
Cpp实现
class Solution {
public:
//第1种：
/*string reverseLeftWords(string s, int n) {
string res = "";
res = s.substr(n, s.length()-n);
res += s.substr(0, n);
return res;
}*/
//第2种：
/*string reverseLeftWords(string s, int n) {
string res = "";
for(int i = 0; i < s.length(); i++){
res.push_back(s[(i+n)%s.length()]);
}
return res;
}*/
//第3种：
void reverse(string& s, int l , int r){
while(l < r){
char ch = s[l];
s[l++] = s[r];
s[r--] = ch;
}
}
string reverseLeftWords(string s, int n) {
reverse(s, 0, n-1);
reverse(s, n, s.length()-1);
reverse(s, 0, s.length()-1);
return s;
}
};C实现
void reverse(char* s, int len){
int l = 0, r = len - 1;
while(l < r){
char ch = s[l];
s[l++] = s[r];
s[r--] = ch;
}
}
char* reverseLeftWords(char* s, int n){
int len = strlen(s);
reverse(s, n);
reverse(s+n, len-n);
reverse(s, len);
return s;
} 6 实现 strStr()
- 题目链接：28. 实现 strStr()
6.1 题目描述
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例1:
输入: haystack = “hello”, needle = “ll”
输出: 2
示例2:
输入: haystack = “aaaaa”, needle = “bba”
输出: -1
示例3:
输入: haystack = “”, needle = “”
输出: 0
6.2 思路
字符串匹配，KMP算法。
完整代码如下：
class Solution {
public:
vector<int> calNext(string needle){
int n = needle.length();
vector<int> next(n, -1);
int k = -1;
next[0] = -1;
for(int i = 1; i < n; ++i){
while(k > -1 && needle[i] != needle[k+1]){
k = next[k];
}
if(needle[i] == needle[k+1]){
++k;
}
next[i] = k;
}
return next;
}
int KMPSearch(string haystack, string needle){
vector<int> next = calNext(needle);
int k = -1, n = haystack.length(), m = needle.length();
for(int i = 0; i < n; ++i){
while(k > -1 && haystack[i]!=needle[k+1]){
k = next[k];
}
if(haystack[i] == needle[k+1]){
++k;
}
if(k == m-1){
return i-k;
}
}
return -1;
}
int strStr(string haystack, string needle) {
return KMPSearch(haystack, needle);
}
}; 总结
7 重复的子字符串
- 题目链接：459. 重复的子字符串
7.1 题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例1:
输入: s = “abab”
输出: true
示例2:
输入: s = “aba”
输出: false
示例3:
输入: s = “abcabcabcabc”
输出: true
7.2 思路
创建一个字符串tmpstr，令其值为s+s，即复制两边字符串s；如果字符串s可以由其一个子串重复多次构成，则在tmpstr中查找s，如果查找到的位置小于s.length()，则返回true，否则返回false。
完整代码如下：
class Solution {
public:
vector<int> calNext(string needle){
int n = needle.length();
vector<int> next(n, -1);
int k = -1;
next[0] = -1;
for(int i = 1; i < n; ++i){
while(k > -1 && needle[i] != needle[k+1]){
k = next[k];
}
if(needle[i] == needle[k+1]){
++k;
}
next[i] = k;
}
return next;
}
bool KMPSearch(string haystack, string needle){
vector<int> next = calNext(needle);
int k = -1, n = haystack.length(), m = needle.length();
for(int i = 1; i < n-1; ++i){
while(k > -1 && haystack[i]!=needle[k+1]){
k = next[k];
}
if(haystack[i] == needle[k+1]){
++k;
}
if(k == m-1){
return true;
}
}
return false;
}
bool repeatedSubstringPattern(string s) {
return KMPSearch(s+s, s);
}
}; 总结
要学会KMP！！！
