刷題記錄（8）string類操作使用

一、僅反轉字母

917. 僅僅反轉字母 - 力扣（LeetCode）

簡單來說輸入字符串，要求你返回所有僅字母位置反轉后的字符串。

簡單看一個樣例加深理解：

前后互換，我想思路基本很明顯了，雙指針，或者說前后指針法。

基本上循環停止的條件就是指針交匯，具體還是拿這個樣例畫圖看看：

下次就該交匯了，等于當兩指針相遇或者錯過了，那么循環就該停止，換言之，head < tail循環才能進行。

簡單寫寫代碼嘗試嘗試：

沒啥問題，思路也沒多難，就是個指針，一個從前往后，一個從后往前，三種情況，如果倆指針指向的都是字母那就互換；哪個不是哪個就繼續遍歷，直到倆都是字母。

最后返回即可。

重點是有了STL以后明顯看出來，s.size是庫里的，swap也不用自己寫了，isalpha用的是C學的字符函數，自己出出思路，麻煩事都有庫和編譯器解決，好不快活。

二、字符串中第一個唯一字符

387. 字符串中的第一個唯一字符 - 力扣（LeetCode）

1.第一次嘗試

看見這一道題第一反應是寫個雙指針，一個指針站崗，另一個指針遍歷。這個方法大概率就是O( $n^{2}$ )。

而且可恨的是我自己寫的時候其實很搞笑：

class Solution {
public:int firstUniqChar(string s) {int ptree = 0;int ps = 1;if (s.size() == 1)return 0;while (ptree < s.size()){while (ps < s.size()&&s[ptree] != s[ps]){ps++;}if (ps < s.size() && s[ptree] == s[ps]){ptree++;}if(ps == s.size())return ptree;}return -1;}
};

錯誤原因倒是也簡單：

按照我寫的代碼邏輯，很明顯只會站到ptree的下一個位置開始遍歷，這樣第二個a就會被誤認為是第一個唯一字符。

2.歸巢原理

class Solution {
public:int firstUniqChar(string s) {int arr[26] = { 0 };int ps = 0;while (ps < s.size()){int value = s[ps] - 'a';arr[value]++;ps++;}int i = 0;while (arr[i] != 1){i++;}if (i < 26){char rep = i + 'a';ps = 0;while (ps < s.size()){if (s[ps] == rep)return ps;ps++;}}elsereturn -1;}
};

因為第一次嘗試末尾的錯誤，我大腦里并不是說繼續走下去那個O( $n^{2}$ )的算法，因為那樣真的是實打實的高復雜度。我想到歸巢原理就是因為我冒出來了一個念頭，如果前后都能知道都能照顧的到就好了，就想到了計數，也就是類似于我們之前寫過的計數排序一樣。

當然，這段代碼還是有問題，不是全部路徑都有返回值就不說了。

最開始的歸巢寫的倒是沒啥問題，但是后面判斷的順序我錯了：

在后面的調試中可以看到，我的邏輯是哪個是第一個1那就是第一個唯一字符，其實這段代碼寫出來就有問題，你arr中是以英文字母表的順序排列的，又不是原字符串s，所以就會出現錯誤。

最后我把歸巢化簡，并遍歷s來確定誰是第一個唯一字符：

class Solution {
public:int firstUniqChar(string s) {int count[26] = { 0 };for (auto ch : s){count[ch - 'a']++;}for (size_t i = 0; i < s.size(); i++){if (count[s[i] - 'a'] == 1)return i;}return -1;}
};

入鄉隨俗了，C++里有這么個方便的遍歷方式就用起來，然后根據下標從頭開始對比這個字符在數組中映射的值是不是1。

三、字符串最后一個單詞的長度

字符串最后一個單詞的長度_牛客題霸_牛客網

其實這么看來還簡單了一點，簡單到哪了呢？

每個單詞之間用' '分割，這樣的話你倒著讀取，找到最后一個空格，最后一個空格后不就是最后一個單詞嘛，有了最后一個空格的位置何愁最后一個單詞的長度呢。

#include <iostream>
using namespace std;int main() {string s("hellonowcoder");cin >> s;int space = s.size() - 1;while (space >= 0 && s[space] != ' '){space--;}if (space < 0)cout<< s.size() <<endl;elsecout<< s.size() - space - 1 << endl;return 0;
}

但是天有不測風云：

原因也簡單，cin和scanf讀數據的時候默認跳過空格，所以這樣的話只能讀到第一個單詞，永遠輸出的值都是第一個單詞的值，在VS上調試可知：

所以這里就用到我們說的getline函數了：

講string的時候就說了，這玩意平常不顯山不露水的，一遇到事它是真上啊，你把默認分界符（空格）改了不就行了。

#include <iostream>
using namespace std;int main() {string s("hellonowcoder");getline(cin,s);int space = s.size() - 1;while (space >= 0 && s[space] != ' '){space--;}if (space < 0)cout<< s.size() <<endl;elsecout<< s.size() - space - 1 << endl;return 0;
}

直接大功告成。

四、驗證回文串

125. 驗證回文串 - 力扣（LeetCode）

別管思路不思路，上來你就得干個大小寫轉換，因為只要是相同的字母，不管大小寫都算相同，所以索性直接全變大或者全變小。

然后其實也簡單，直接雙指針前后對照就行，這個題其實超級像反轉字母，只不過對遍歷到的對象的操作不一樣。

class Solution {
public:bool isalphaornum(char ch){if(isalpha(ch)||(ch >= '0'&&ch <= '9'))return true;elsereturn false;}bool isPalindrome(string s) {//轉換for(auto& ch: s){if(isupper(ch))ch = tolower(ch);}int phead = 0;int ptail = s.size() - 1;while(phead <= ptail){while(phead < ptail&&!isalphaornum(s[phead]))phead++;while(phead < ptail&&!isalphaornum(s[ptail]))ptail--;if(s[phead] != s[ptail])return false;phead++;ptail--;}return true;}
};

需要強調的有兩點，雖然最后題目通過了，tolower函數的返回值：

返回對應小寫字母的ASCII碼，也就是說傳參不能改變實參的值，我自己寫的時候直接是tolower(ch)，結果拿著一調試我發現自己壓根沒變大小寫。

然后就是注意題上要求的是字符串只剩字母和數字。

五、字符串相加

415. 字符串相加 - 力扣（LeetCode）

為什么說有這種需求呢，沒事搞啥字符串相加。

看題上給的樣例不也就正常數字相加嘛：

實際上樣例的意思是讓你寫出來函數讓字符串實現整型的相加減，因為正常情況下一個int最多存42億多的值，而longlong啥的肯定更大，只不過總歸是有限度的，有極個別，航天領域之類的可能會遇到整型無法計算的值，而字符串的長度可是無限的啊，這玩意就說存個42億，也就十位數大概11個字節存下，重點這玩意還能繼續存啊。你把char[10000]填滿，longlong啥的或者更大的能達到嗎？

所以實現字符串相加其實還挺合理的。

思路：

我的思路很簡單，末尾對齊當豎式算，從后往前依次取出來字符，并將其轉換為整型計算，把進位記錄下來進入下次的計算，直至最長的都被加完。

這個直至有點麻煩，也就是說你一直得檢查是否越界，越界以后那就不用再加了基本上。

具體代碼里分析怎么解決：

一寫代碼就有思路了，那就是先把短的能加的位加完，出了這個循環再寫倆循環去把倆字符串檢查檢查是不是全部算完了。

轉換成整型算數，算出來比如6+7就是13，1得進位，3得留下，所以就處理一下。然后存到最后返回的字符串里，但是問題就來了，那就是用insert那就O(n^2)了，所以我寫的代碼其實是push_back，這么搞不就反了，不過也簡單：

庫里面有reverse算法。

所以算完最后reverse就行。

隨便寫一個數看看剩下沒有計算的位數怎么插入，很明顯，繼續從后往前尾插就算了：

只可能存在一個越界另一個沒越界和兩個同時越界的情況，同時越界那后面兩段代碼也能兼顧得到，只不過不走而已。另外就是特別注意短的走完了也可能進位，別忘加一下。

而且保證所有循環結束后進位加完了，避免有9 + 1的情況：

class Solution {
public:string addStrings(string num1, string num2) {string ret;int p1 = num1.size() - 1;int p2 = num2.size() - 1;int sum = 0;//記錄和int carry = 0;//記錄進位int value = 0;//記錄留下的值while(p1 >= 0 && p2 >= 0){sum = num1[p1] - '0' + num2[p2] - '0' + carry;carry = sum / 10;//進位value = sum % 10;//除去進位的值ret.push_back(value + '0');p1--;p2--;}if(p1 < 0){while(p2 >= 0){sum = num2[p2] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p2--;}}if(p2 < 0){while(p1 >= 0){sum = num1[p1] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p1--;}}if(carry > 0)ret.push_back(carry + '0');reverse(ret.begin(),ret.end());return ret;}
};

六、反轉字符串

541. 反轉字符串 II - 力扣（LeetCode）

其實讀了讀這段話每k個字符反轉一次，每2k重置一次。

我個人看了這么多傾向于寫個循環處理整個字符串是k的倍數的情況，至于不是k的倍數的，大致上分的兩種其實基本差不多：

到時候遍歷肯定是用指針遍歷，畫圖的時候就當成指針了，但是等到需要reverse的時候一定得轉換成迭代器（因為有迭代器就可以用STL庫里的reversel了，超級省事）剛開始不妨都放到字符串的頭，后面的指針往后一直走，走到k個就傳迭代器調reverse算法，然后走到2k個就把前面的迭代器拉過來。

簡單來說循環里就是一個站崗一個遍歷。

一旦出了循環，剛好是2k的倍數，這種情況不多說。

這個時候計算。后面指針，就說叫soldier吧，畢竟老累了，沖鋒陷陣，前面站崗的我也不知道哨兵是啥，就起個tree。如果soldier-tree<k那就不用費勁了，傳tree和end()不就完成任務了；如果k<soldier-tree<2k，其實根本不用管了，因為前面每2k個不用說了，剩下的前k個肯定會被處理，只不過重置前直接跳出循環了，剩下那不足k個又不用管他。

當然還是舉例子看一眼合適，這玩意總會出現+1-1的問題：

結果就發現，如果直接用下標-，還需要+1才準。

class Solution {
public:string reverseStr(string s, int k) {int tree = 0;int soldier = 0;while(soldier < s.size()){if(soldier - tree + 1 == k){string::iterator it1 = s.begin() + tree;//迭代器用的時候左閉右開string::iterator it2 = s.begin() + soldier + 1;reverse(it1,it2);}if(soldier - tree + 1 == 2 * k){tree = ++soldier;}soldier++;}if(soldier - tree + 1 <= k){string::iterator it = s.begin() + tree;reverse(it,s.end());}return s;}
};

強調一個點，最后if的時候其實我寫的是soldier - tree + 1 < k，不足k個的話直接全部反轉唄，但是難免出現特例：

7個元素，不夠8個，上面的循環僅僅是soldier一直后移，啥也沒干，但是最后soldier的位置拿下標來說的話，其實是下標7的位置，7 + 1剛好是8，剛好不符合小于，也就沒辦法給它reverse，一修就行了。

七、反轉字符串中的單詞

557. 反轉字符串中的單詞 III - 力扣（LeetCode）

再看一眼例子：

思路直接出來了，還是兩個指針，一個指針只要碰見字母就停下，一個指針碰到空格或'\0'就停下，這樣這倆指針站的也剛好就是reverse的兩個迭代器的位置，所以這次直接嘗試用迭代器遍歷吧，雖然沒有那么淺顯易懂，但是總歸reverse的時候爽。

class Solution {
public:string reverseWords(string s) {string::iterator alpha = s.begin();string::iterator space = s.begin();while(space != s.end()){   if(!isalpha(*alpha))alpha++;if(*space != ' ')space++;if(isalpha(*alpha)&&*space == ' '){reverse(alpha,space);alpha = space++;}}//到最后直接跳出來了，并沒有reverse最后一個單詞reverse(alpha,space);return s;}
};

代碼看著沒啥毛病，但是架不住題陰啊：

合著把(也給我當成單詞里的字符了，我真服了，所以alpha的遍歷我也不整那么多虛的了，初始化為begin，以后全部改為' '位置+1包對的，我不再用isalpha做判斷條件了，太陰了。

class Solution {
public:string reverseWords(string s) {string::iterator alpha = s.begin();string::iterator space = s.begin();while(space != s.end()){   if(*space != ' ')space++;if(*space == ' '){reverse(alpha,space);alpha = ++space;}}//到最后直接跳出來了，并沒有reverse最后一個單詞reverse(alpha,space);return s;}
};

陰死我了，我看見上面那個樣例其實我人是蒙的，后來單獨拉出來string和它的左括號直接無語了，現在alpha不用找了，剛開始在begin后面就在' '+1，利用的是：

太陰了，不過還是做出來了。

八、字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

其實寫字符串相加和寫這個字符串相乘都不是同一天，寫完字符串相加的時候我還在想，進位的問題嘛，加法最大9+9等于18，最多進位1；然后我就想到如果乘法那就進位大了，結果今天就看見這道字符串相乘了，果然我能想到的，出題的也能想到啊。

就拿這個例子來說，我最開始想的是把短的拆成不同位數去乘

空想完了我發現，其實還是要用到int或者更大的longlong才能用，我就回想我做字符串相加最核心的思想就是拆分，當時是對齊以后，兩數相加以后記錄下來進位記錄下來留下的值，所以核心應該還是拆分。

于是我就列了個豎式，其實我們豎式的思想就是每位乘后再加，而且我觀察到：

豎式算出來幾行也就是幾個數取決于下面的字符串有多長，完全可以創建兩個空字符串，第一個字符串記錄上次算出來的和，第二個字符串記錄這次算出來的數，并且末尾補0（to_string再push_back字符'0'即可）。最后再讓這倆字符串相加存到第一個字符串上，字符串相加已經實現過了。

上面這種操作不斷循環，直至把較短字符串從后往前遍歷完，但是如果較長字符串長度是n1，較短字符串是n2的話，那么內層再嵌套個字符串相加，基本上最少都得是n1的長度，也就是說可能是n1*n2的復雜度。

一路修修補補過來的，不再一段一段代碼復制粘貼了，直接看最后成果：

class Solution {
public:string addStrings(string num1, string num2) {string ret;int p1 = num1.size() - 1;int p2 = num2.size() - 1;int sum = 0;//記錄和int carry = 0;//記錄進位int value = 0;//記錄留下的值while(p1 >= 0 && p2 >= 0){sum = num1[p1] - '0' + num2[p2] - '0' + carry;carry = sum / 10;//進位value = sum % 10;//除去進位的值ret.push_back(value + '0');p1--;p2--;}if(p1 < 0){while(p2 >= 0){sum = num2[p2] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p2--;}}if(p2 < 0){while(p1 >= 0){sum = num1[p1] - '0' + carry;carry = sum / 10;value = sum % 10;ret.push_back(value + '0');p1--;}}if(carry > 0)ret.push_back(carry + '0');reverse(ret.begin(),ret.end());return ret;}string multiply(string num1, string num2) {//如果有一個是0就不用算了，直接return算了if(num1[0] == '0'||num2[0] == '0'){return "0";}string multi;string ret("0");string now;int carry = 0;//記錄進位int value = 0;//記錄尾插值int mul = 0;//記錄每兩位的積//還是創建倆指針來遍歷字符串int p1 = num1.size() - 1;int p2 = num2.size() - 1;//以豎式下面的值的長度定while(p2 >= 0){//計算每一位與num1這個字符串相乘的值while(p1 >= 0){int mul = (num1[p1] - '0') * (num2[p2] - '0') + carry;carry = mul / 10; value = mul % 10;multi.push_back(value + '0');p1--;}//防止9 * 9 = 81只插1，把carry清空再說if(carry != 0){multi.push_back(carry + '0');carry = 0;}//定nowreverse(multi.begin(),multi.end());now = multi;multi = "";for(int i = 0;i < num2.size() - p2 - 1;i++){now.push_back('0');}//相加ret = addStrings(ret,now);p1 = num1.size() - 1;p2--;}return ret;}
};

上面那段是字符串相加，不多解釋。

創建的multi是用來接收本次計算得到的值的，所以當本次值已經給出去以后