344.反轉字符串I

文檔講解：代碼隨想錄算法訓練營
視頻講解：算法視頻公開課
狀態：做出來了，用了一個臨時字符，反復交換就行了

思路

本道題是實現reverse()函數，所以不要直接使用reverse()函數。
本道題是要使用雙指針，使用相向雙指針的方法。

class Solution {
public:void reverseString(vector<char>& s) {int n = s.size();for (int i = 0, j = n - 1; i < n / 2; i++, j--) {swap(s[i], s[j]);}}
};

這里swap()交換函數的實現如下：

        	// swap()函數實現方法一tmp = s[i];s[i] = s[j];s[j] = tmp;

        	// swap()函數實現方法二s[i] ^= s[j];s[j] ^= s[i];s[i] ^= s[j];

541.反轉字符串II

文檔講解：代碼隨想錄算法訓練營
視頻講解：算法視頻公開課
狀態：沒做出來，沒讀懂題，繞蒙了。

題目理解

這道題讀題有點難理解。
這道題是在講，一個字符串s，每2k個為一組。
每組中前k個元素反轉，后k個不變。
如果剩下的字符數目不足2k個，那么還有兩種情況：
（1）如果不足k個，那么這些元素反轉
（2）如果k < 剩下字符數目 < 2k，那么前k個反轉，剩下的不變。

解題思路

這道題我們for循環里，i += 2k進行循環，每次循環中，只反轉[i, i + k)區間的字符，反轉完結束本次循環。如果剩余字符不足k個，那么反轉[i, n)區間的字符。
代碼：

class Solution {
public:string reverseStr(string s, int k) {int n = s.size();// 進入循環，每 2k 個字符為一組for (int i = 0; i < n; i += 2 * k) {// 如果這組字符數 > k 個，那么前 k 個字符反抓if (i + k <= n) {reverse(s.begin() + i, s.begin() + i + k);continue;}// 如果不足 k 個元素，反轉剩余元素reverse(s.begin() + i, s.begin() + n);}return s;}
};

邊界細節

這里有幾個邊界問題的細節
1）if()的判斷條件：i + k <= n。假設n = 3，k = 3，i = 0，第一次是符合的，如果沒有等于，那么就不符合，明顯不對。
2）reverse()傳入的參數：這里是左閉右開區間，第 k 個元素的下表是 i + k - 1，那么反轉的區間是[i, i + k - 1]。

reverse()函數的實現

class Solution {
public:void reverse(string& s, int start, int end) {for (int i = start, j = end - 1; i < j; i++, j--) {swap(s[i], s[j]);}}string reverseStr(string s, int k) {int n = s.size();for (int i = 0; i < n; i += 2 * k) {if (i + k <= n) {reverse (s, i, i + k);continue;}reverse (s, i, n);}return s;}
};

kamacoder54.替換數字 – 第八期模擬筆試

文檔講解：代碼隨想錄算法訓練營
狀態：看題解懂了

解題思路

第一步：
首先我們要給原來字符串擴容，這里用到的是resize()函數。遇到數字，就給原來字符串擴容5個空間

    int count = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] >= '0' && s[i] <= '9') {count ++;}}

第二步：
我們設原來字符串的最后字符索引為n1 = s.size() - 1，擴容后新字符串的最后一個字符的索引為n2 = s.size() - 1。

    int n1 = s.size() - 1;s.resize(s.size() + 5 * count);int n2 = s.size() - 1;

第三步：
我們遍歷原字符串，如果原字符串某個字符是字母，那么就在新字符串中最后一個位置填上原來字符串的字母；
如果原來字符串某個字符是數字，那么就在新字符串從后到前依此填上r, e, b, m ,u ,n

    while (n1 >= 0) {if (s[n1] >= '0' && s[n1] <= '9') {s[n2 --] = 'r';s[n2 --] = 'e';s[n2 --] = 'b';s[n2 --] = 'm';s[n2 --] = 'u';s[n2 --] = 'n';} else {s[n2 --] = s[n1];}n1 --;}

完整代碼如下：

#include <iostream>
using namespace std;int main() {string s;cin >> s;int count = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] >= '0' && s[i] <= '9') {count ++;}}int index1 = s.size() - 1;s.resize(s.size() + 5 * count);int index2 = s.size() - 1;while (index1 >= 0) {if (s[index1] >= '0' && s[index1] <= '9') {s[index2 --] = 'r';s[index2 --] = 'e';s[index2 --] = 'b';s[index2 --] = 'm';s[index2 --] = 'u';s[index2 --] = 'n';} else {s[index2 --] = s[index1];}index1 --;}cout << s << endl;
}

注意：
（1）while()循環的條件是index1 >= 0，而不是index1 --，因為最后已經減了，index1的范圍可以到0，它指的是索引下標。
（2）注意index1和index2的含義，不要弄混。