字符串
1 反转字符串
题目：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路：
双指针法
代码：
void reverseString(vector<char>& s) {
for(int i = 0,j=s.size()-1;i < s.size()/2 ;i++,j--){
swap(s[i],s[j]);
}
}
2 反转字符串Ⅱ
题目：
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路：
2k为一段，for循环反转
代码：
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);
else reverse(s.begin()+i,s.end());
}
return s;
}
3 替换空格
题目：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1： 输入：s = "We are happy."
输出："We%20are%20happy.
思路：
第一遍检查空格数量，第二遍从后往前开始替换
代码：
string replaceSpace(string s) {
int spaceNum = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == ' ') spaceNum++;
}
int oldSize = s.size();
s.resize(oldSize + spaceNum * 2);
for(int left = oldSize - 1,right = s.size() - 1; left < right;left--,right--){
if(s[left]!= ' ') {
s[right] = s[left];
}
else {
s[right--] = '0';
s[right--] = '2';
s[right] = '%';
}
}
return s;
}
4 翻转字符串里的单词
题目：
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路：
双指针法去除多余空格，先整体反转，再反转每一个单词。
代码：
void reverse(string&s,int start ,int end){
for(int i = start,j = end-1;i<j;i++,j--){
swap(s[i],s[j]);
}
}
void removeExtraSpace(string&s){
int slow = 0;
for(int i=0;i<s.size();++i){
if(s[i] != ' '){
if(slow != 0){
s[slow++] = ' ';
}
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
removeExtraSpace(s);
reverse(s,0,s.size());
for(int i = 0,j=0;i<s.size();i++){
if(s[i]==' ') {
reverse(s,j,i);
j = i + 1;
}
if(i == s.size()-1) reverse(s,j,i+1);
}
return s;
注意点reverse的开闭区间问题
5 左旋转字符串
题目：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
思路：
分成两个部分，左旋的部分反转一次，其余部分翻转一次，整体再反转一次即可
代码：
void reverse(string &s,int i,int j){
for(;i<j;i++,j--) swap(s[i],s[j]);
}
string reverseLeftWords(string s, int n) {
reverse(s,0,n-1);
reverse(s,n,s.size()-1);
reverse(s,0,s.size()-1);
return s;
}
注意点：边界条件
6 实现strStr()
题目：
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符
思路：
滑动窗口法
代码：
int strStr(string haystack, string needle) {
if(haystack.size()< needle.size()) return -1;
for(int i = 0;i <= haystack.size()-needle.size();i++){
int fast_i = i;
int fast_j = 0;
while(haystack[fast_i]==needle[fast_j]){
if(fast_j == needle.size() - 1) return i;
fast_i++;
fast_j++;
}
}
return -1;
}
7 重复的字符串
题目：
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
思路：
KMP
代码：