344:反轉字符串
編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組?s?的形式給出。
不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
示例 1：
輸入：s = ["h","e","l","l","o"] 輸出：["o","l","l","e","h"]
注意不能使用額外空間，這里就使用左右雙指針來進行翻轉
class Solution {
public:void reverseString(vector<char>& s) {int l = 0, r = s.size() - 1;while(l < r){char tmp;tmp = s[l];s[l] = s[r];s[r] = tmp;l++;r--;}}
};541:反轉字符串II
給定一個字符串?s?和一個整數?k，從字符串開頭算起，每計數至?2k?個字符，就反轉這?2k?字符中的前?k?個字符。
- 如果剩余字符少于?
k?個，則將剩余字符全部反轉。 - 如果剩余字符小于?
2k?但大于或等于?k?個，則反轉前?k?個字符，其余字符保持原樣。
示例 1：
輸入：s = "abcdefg", k = 2 輸出："bacdfeg"
根據題目意思走，步長設置為2k，左右指針的設定上右指針需要判斷右邊的剩余元素是否小于k，只要不小于就正常進行替換，如果小于k，將右指針設置為右邊界并進行替換。
class Solution {
public:string reverseStr(string s, int k) {int n = s.size();for(int i = 0; i < s.size(); i += 2 * k){int l = i, r = min(l + k - 1, n - 1);while(l < r){char tmp = s[l];s[l] = s[r];s[r] = tmp;l++;r--;}}return s;}
};?54:替換數字
給定一個字符串 s，它包含小寫字母和數字字符，請編寫一個函數，將字符串中的字母字符保持不變，而將每個數字字符替換為number。 例如，對于輸入字符串 "a1b2c3"，函數應該將其轉換為 "anumberbnumbercnumber"。
輸入描述
輸入一個字符串 s,s 僅包含小寫字母和數字字符。
輸出描述
打印一個新的字符串，其中每個數字字符都被替換為了number
輸入示例
a1b2c3輸出示例
anumberbnumbercnumber?先進行一遍遍歷確定數字個數，然后新建一個合適大小的數組，這里注意開空間的時候為數字個數n*6-n = 5 * n,然后使用前后兩個指針一個指向新數組的末尾，一個指向原數組的末尾，左指針檢測到數字就從右指針開始填充number，不然就將當前元素賦值給當前右指針位置然后一起前移。
#include<bits/stdc++.h>
using namespace std;int main(){string s;cin >> s;int n = s.size();int count = 0;for(int i = 0; i < n; i++){if(s[i] >= '0' && s[i] <= '9'){count++;}}vector<char> new_nums(n + count * 5);for(int i = 0; i < n; i++){new_nums[i] = s[i];}int l = n - 1, r = new_nums.size() - 1;while(l >= 0){if(new_nums[l] >= '0' && new_nums[l] <= '9'){new_nums[r--] = 'r';new_nums[r--] = 'e';new_nums[r--] = 'b';new_nums[r--] = 'm';new_nums[r--] = 'u';new_nums[r--] = 'n';l--;}else{new_nums[r--] = new_nums[l]; l--;}}for(int i = 0; i < new_nums.size(); i++){cout << new_nums[i];}return 0;
}151：翻轉字符串中的單詞
給你一個字符串?s?，請你反轉字符串中?單詞?的順序。
單詞?是由非空格字符組成的字符串。s?中使用至少一個空格將字符串中的?單詞?分隔開。
返回?單詞?順序顛倒且?單詞?之間用單個空格連接的結果字符串。
注意：輸入字符串?s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。
示例 1：
輸入：s = "the sky is blue" 輸出："blue is sky the"
class Solution {
public: void reverse(string& s, int start, int end){int l = start, r = end;while(l < r){swap(s[l++], s[r--]);}}void removeextrablank(string& s){// 先去除頭部的空白int slow = 0, fast = 0; while(fast < s.size() && s[fast] == ' '){fast++;}// 處理單詞之間多余的空格for(;fast < s.size(); fast++){if(fast - 1 > 0 && s[fast] == ' ' && s[fast - 1] == s[fast]){continue;}else{s[slow++] = s[fast];}}if(slow - 1 > 0 && s[slow - 1] == ' '){s.resize(slow - 1);}else{s.resize(slow);}}string reverseWords(string s) {removeextrablank(s);reverse(s, 0, s.size() - 1);int left = 0;for(int i = 0; i <= s.size(); i++){if(s[i] == ' ' || i == s.size()){reverse(s, left, i - 1);if(i != s.size() - 1){left = i + 1; }}}return s;}
};?先進行對冗余空格的處理，使用雙指針來進行，快指針通過while循環越過所有頭部的空格，后續用slow和fast互換完成對空格的覆蓋，然后對單詞間的冗余空格進行處理，還是同樣的操作當判斷連續兩個空格以上的時候使用continue越過冗余的空格，然后通過后續的互換來覆蓋，最后通過慢指針判斷末尾的空格，如果末尾有空格則將數組大小控制在slow - 1，不然控制在slow。
在主函數中，我們先進行冗余空格的處理，然后反轉字符串，通過一個for循環對逐個單詞進行翻轉。
55:右旋字符串
字符串的右旋轉操作是把字符串尾部的若干個字符轉移到字符串的前面。給定一個字符串 s 和一個正整數 k，請編寫一個函數，將字符串中的后面 k 個字符移到字符串的前面，實現字符串的右旋轉操作。?
例如，對于輸入字符串 "abcdefg" 和整數 2，函數應該將其轉換為 "fgabcde"。
輸入描述
輸入共包含兩行，第一行為一個正整數 k，代表右旋轉的位數。第二行為字符串 s，代表需要旋轉的字符串。
輸出描述
輸出共一行，為進行了右旋轉操作后的字符串。
輸入示例
2
abcdefg輸出示例
fgabcde就是找規律然后翻轉特定區間內的字符串，現將整體反過來，然后換分為兩個區域進行翻轉即可。?
#include<bits/stdc++.h>
using namespace std;
void reverse(string& s, int start, int end){int l = start, r = end;while(l < r){swap(s[l++], s[r--]);}
}
int main(){int k;string s;cin >> k >> s;int n = s.size();reverse(s, 0, n - 1);reverse(s, 0, k - 1);reverse(s, k, n - 1);for(int i = 0; i < n; i++){cout << s[i];} return 0;
}子串匹配：（連續字符串）
KMP算法：
28:找出字符串中第一個匹配項的下標
給你兩個字符串?haystack?和?needle?，請你在?haystack?字符串中找出?needle?字符串的第一個匹配項的下標（下標從 0 開始）。如果?needle?不是?haystack?的一部分，則返回??-1?。
示例 1：
輸入：haystack = "sadbutsad", needle = "sad" 輸出：0 解釋："sad" 在下標 0 和 6 處匹配。 第一個匹配項的下標是 0 ，所以返回 0 。
NEXT數組的建立：
設置兩個指針：前綴指針指向公共前后綴中前綴的最后一個字符，后綴指針指向公共前后綴中后綴的最后一個字符。
遍歷過程：比較兩個指針所指向的元素如果相同，兩個指針一起向前移動，并將前綴指針的下標復制給next[i]表示當前前綴指針指向的元素所在的前面的子串中公共前后綴的字符數為j，如果不同就需要對前綴指針回退并檢查。這里我們檢查當前兩個指針所遍歷過得最長公共前后綴中是否含有子公共前后綴，這樣前綴指針就不需要回退到0
處重現開始檢查而是縮小了公共前后綴的長度（父到子的關系）再檢查j此時的字符是否與i相等，如果不等接著回退到上一級公共前綴的位置知到j到了初始位置0處停止回退。
模式串與字符串的比較：
與next數組的建立過程一致，只不過少了對next數組的賦值過程。保證遍歷字符串的指針i穩定前移，遇到相等的字符，模式串指針和字符串指針一起前進，當兩指針指向的字符不同時，此時next[ j ]表示當前模式串遍歷過去的子串中公共前后綴中前綴的最后一位的下一位位置，也就是說當前字符串指針遍歷過的i， j指向元素相等的這個子串中去除當前不同元素的子串中公共前后綴中公共前綴的下一位，從這一位直接開始比較而不需要從頭開始比較。
為了防止字符串每移動一位就需要遍歷一遍模式串，會不斷的縮小比較的范圍，當前位不一致時，從前面已經遍歷過的子串中回退到子串的公共前綴的下一位再開始比較，避免回退到初始位置進行比較。
class Solution {
public:// &:引用 void get_next(const string& s, int* next){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; // next的賦值是在對j處理全部完成之后}}int strStr(string haystack, string needle) {if(needle.size() == 0){return 0;}vector<int> next(needle.size());get_next(needle, &next[0]);int j = 0;for(int i = 0; i < haystack.size(); i++){while(j > 0 && needle[j] != haystack[i]){j = next[j - 1];}if(needle[j] == haystack[i]){j++;}// 當模式串與主串比較完最后一個模式串的字符時j進行了加1操作if(j == needle.size()){return i - needle.size() + 1;}}return -1;}
};注意if和while的順序，如果兩者順序顛倒就會出現j指針跑到i指針的前面去了會導致兩者從開始一直同步向前走時，在最后一處相同的位置比較完成之后j進行自增操作導致此時j+1和i不同導致錯位，提前進入while的錯誤循環。
