今天，帶來字符串相關算法的講解。文中不足錯漏之處望請斧正！
理論基礎點這里
1. 替換空格
題目描述：請實現一個函數，把字符串 s 中的每個空格替換成"%20"。
來源：力扣（LeetCode）
難度：簡單
提示：
0 <= s 的長度 <= 10000
示例 1：
輸入：s = “We are happy.” 輸出：“We%20are%20happy.”
題意轉化
把字符串內的所有' '替換為%20.
解決思路(抽象)
使用額外空間
創建一個空字符串, 遍歷給定字符串s, 遇到字符的時候直接插入空字符串, 遇到空格的時候插入%20.
不使用額外空間
不用額外空間就要擴容：統計空格個數，每個空格替換成“%20”，就意味著每個空格都需要額外兩個字符的空間。
擴容后，從后向前替換。
為什么是從后向前？因為從前向后替換數組元素，每次替換完都要把后面所有元素往后移動，這就是O(n^2)的復雜度了。
編程實現(具體)
使用額外空間
class Solution {
public:string replaceSpace(string s) {string ret;for(char &ch : s) {if(ch == ' ') ret += "%20";else ret += ch;}return ret;}
};
不使用額外空間
class Solution {
public:string replaceSpace(string s) {// 擴容int count = 0; //空格個數for(char &ch : s) if(ch == ' ') ++count;int oldSize = s.size();s.resize(s.size() + count * 2);int newSize = s.size();// 從后向前替換for(int i = oldSize - 1, j = newSize - 1; i < j; --i, --j) {if(s[i] != ' ') {s[j] = s[i];} else {s[j] = '0';s[j - 1] = '2';s[j - 2] = '%';j -= 2; //多了兩次操作，j指針對應移動}}return s;}
};
2. 反轉單詞
給你一個字符串 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”
解釋：如果兩個單詞間有多余的空格，反轉后的字符串需要將單詞間的空格減少到僅有一個。
提示：
1 <= s.length <= 104
s 包含英文大小寫字母、數字和空格 ’ ’
s 中 至少存在一個 單詞
進階：如果字符串在你使用的編程語言中是一種可變數據類型，請嘗試使用 O(1) 額外空間復雜度的 原地 解法。
題意轉化
返回 單詞 順序顛倒且 單詞 之間用單個空格連接的結果字符串.
解決思路(抽象)
首先, 要保證單詞之間用單個空格連接(頭尾沒有空格).
原地處理的話, 可以使用雙指針重新填充字符串:
- fast：遍歷s拿字符（遇到空格就跳過）
- slow：從頭填充合法字符串
簡單說, 每次遇到空格就自己把單詞填充上, 再手動添加一個空格, 就可以滿足題目要求.
單詞順序顛倒, 我們無法直接實現, 但我們能做什么?
- 顛倒字符串順序
- 顛倒單個單詞順序
前者就可以顛倒單詞順序, 只不過會讓單個單詞也顛倒, 我們再次顛倒每個單詞, 不就得到了題目要求的字符串了嗎.
比如 如 hello world , 整體反轉后是 dlrow olleh；然后對單詞反轉 world hello .
簡單說, 先總體反轉, 再局部反轉.
編程實現(具體)
最后一個單詞, 可以在反轉單詞內部順序的循環中處理, 也可以跳出循環單獨處理.
最后一個單詞反轉單詞內部順序的循環中處理:
class Solution {
public:string reverseWords(string s) {//雙指針重新填充字符串int slow; // 填充字符串int fast; // 遍歷sfor (slow = 0, fast = 0; fast < s.size(); ++fast) {if (s[fast] == ' ') continue; // 如果是空格就跳過// 填充當前單詞while (fast < s.size() && s[fast] != ' ') s[slow++] = s[fast++];// 填充空格(只有最后一個單詞后不需要填充)s[slow++] = ' ';}s.resize(slow - 1); // 去掉多余的空格(最后一個單詞后不需要填充, 但我們默認填充了)cout << "處理后的字符串: " << s << endl;// 整體反轉reverse(s.begin(), s.end());// 局部反轉int wordBegin = 0;int wordEnd= 0;while (wordEnd <= s.size()) {if (s[wordEnd] == ' ' || wordEnd == s.size()) {reverse(s.begin() + wordBegin, s.begin() +wordEnd);wordBegin = wordEnd + 1;wordEnd = wordBegin;}++wordEnd;}return s;}
};
最后一個單詞跳出循環單獨處理:
class Solution {
public:string reverseWords(string s) {//雙指針重新填充字符串int slow; // 填充字符串int fast; // 遍歷sfor (slow = 0, fast = 0; fast < s.size(); ++fast) {if (s[fast] == ' ') continue; // 如果是空格就跳過// 填充當前單詞while (fast < s.size() && s[fast] != ' ') s[slow++] = s[fast++];// 填充空格(只有最后一個單詞后不需要填充)s[slow++] = ' ';}s.resize(slow - 1); // 去掉多余的空格(最后一個單詞后不需要填充, 但我們默認填充了)cout << "處理后的字符串: " << s << endl;// 整體反轉reverse(s.begin(), s.end());// 局部反轉int wordBegin = 0;int wordEnd= 0;while (wordEnd < s.size()) {if (s[wordEnd] == ' ') {reverse(s.begin() + wordBegin, s.begin() +wordEnd);wordBegin = wordEnd + 1;wordEnd = wordBegin;}++wordEnd;}reverse(s.begin() + wordBegin, s.begin() +wordEnd); // 反轉最后一個單詞return s;}
};
今天的分享就到這里了，感謝您能看到這里。
這里是培根的blog，期待與你共同進步！
)
