字符串|344.反轉(zhuǎn)字符串、541. 反轉(zhuǎn)字符串II吼驶、劍指Offer 05.替換空格、151.翻轉(zhuǎn)字符串里的單詞店煞、劍指Offer58-II.左旋轉(zhuǎn)字符串
344.反轉(zhuǎn)字符串
自己審題思路
遍歷字符串?dāng)?shù)組蟹演，然后交換
看完代碼隨想錄題解后的收獲
思路基本一致
代碼：
class Solution {
public:
void swap(char* a, char* b) {
char tmp = *a;
*a = *b;
*b = tmp;
}
void reverseString(vector<char>& s) {
int n = s.size();
for(int i = 0; i < n/2; i++) {
swap(&s[i], &s[n - i -1]);
}
}
};
/* 引用
class Solution {
public:
void swap(char& a, char& b) {
char tmp = a;
a = b;
b = tmp;
}
void reverseString(vector<char>& s) {
int n = s.size();
for(int i = 0; i < n/2; i++) {
swap(s[i], s[n - i -1]);
}
}
};
*/
這里需要注意，
swap()函數(shù)形參如果使用int&或者 int* 會(huì)報(bào)錯(cuò)顷蟀，雖然字符可以轉(zhuǎn)化成其ASCII碼酒请，但是這里類型不匹配還是會(huì)報(bào)錯(cuò)。
就算可以進(jìn)行類型轉(zhuǎn)換鸣个，這里也會(huì)報(bào)錯(cuò)羞反，因?yàn)槿绻噲D將一個(gè)臨時(shí)對(duì)象綁定在非reference to const類型的reference上布朦，那么編譯器會(huì)給出錯(cuò)誤。
參考
參考詳解
541. 反轉(zhuǎn)字符串II
自己審題思路
前一個(gè)算法題的進(jìn)階昼窗，處理好2k中的前k個(gè)和最后不多于k個(gè)的情況是個(gè)難點(diǎn)
看完代碼隨想錄題解后的收獲
遍歷字符串的過(guò)程中是趴，只要讓 i += (2 * k)，i 每次移動(dòng) 2 * k 就可以了澄惊，然后判斷是否需要有反轉(zhuǎn)的區(qū)間唆途。這樣方便很多，后續(xù)只需要判斷剩余字符串長(zhǎng)度是否大于k掸驱，大于k翻轉(zhuǎn)前k個(gè)肛搬，小于k全部翻轉(zhuǎn)。
代碼：
class Solution {
public:
// void reverse(vector<char>& s) {
// int n = s.size() -1;
// for (int i = 0; i < s.size() / 2; i++) {
// swap(s[i], s[n - i]);
// }
// }
string reverseStr(string s, int k) {
// vector<char> str(s.begin(), s.end());
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;
}
};
參考詳解
劍指Offer 05.替換空格
自己審題思路
第一時(shí)間想到雙指針毕贼，但是從前往后比較麻煩温赔，每次遇到空格都需要移動(dòng)空格后面的所有元素
看完代碼隨想錄題解后的收獲
數(shù)組填充類的問(wèn)題，都可以先預(yù)先給數(shù)組擴(kuò)容帶填充后的大小鬼癣，然后再?gòu)暮笙蚯斑M(jìn)行操作陶贼。
代碼：
class Solution {
public:
string replaceSpace(string s) {
int size = s.size();
int count = 0; // 統(tǒng)計(jì)空格的個(gè)數(shù)
for (int i = 0; i < size; i++) {
if (s[i] == ' ') {
count++;
}
}
int oldSize = s.size();
s.resize(size + 2 * count); // 根據(jù)空格個(gè)數(shù)擴(kuò)充字符串
int newSize = s.size();
// 從后往前將空格替換為"%20"
for (int i = oldSize, j = newSize; i < j;i--, j-- ) {
if (s[i] != ' ') {
s[j] = s[i];
} else {
s[j] = '0';
s[j - 1] = '2';
s[j - 2] = '%';
j -= 2;
}
}
return s;
}
};
參考詳解
151.翻轉(zhuǎn)字符串里的單詞
自己審題思路
這道題初拿到?jīng)]有什么思路
看完代碼隨想錄題解后的收獲
題解思路：
1、刪除多余空格
2扣溺、反轉(zhuǎn)整個(gè)字符串（難點(diǎn)）
3骇窍、反轉(zhuǎn)每個(gè)單詞
循環(huán)里處理了某個(gè)參數(shù)，就需要在循環(huán)判斷里額外判斷一下這個(gè)參數(shù)锥余，避免越界
// 去掉字符串前面的空格
while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
fastIndex++;
}
代碼：
/*
*1腹纳、刪除多余空格
*2、反轉(zhuǎn)整個(gè)字符串
*3驱犹、反轉(zhuǎn)每個(gè)單詞
*/
class Solution {
public:
void reverse(string& s, int start, int end) {//左閉右開(kāi)
for (int i = start, j = end - 1; i < j; i++,j--) {
swap(s[i], s[j]);
}
}
void delSpace(string& s) {
int slow = 0;
int fast = 0;
for (; fast < s.size();fast++) {
if (s[fast] != ' ') {
if (slow != 0) s[slow++] = ' ';//手動(dòng)控制空格嘲恍，給單詞之間添加空格。slow != 0說(shuō)明不是第一個(gè)單詞雄驹，需要在單詞前添加空格佃牛。
while (fast < s.size() && s[fast] != ' ') {
s[slow++] = s[fast++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
int count = 0; // 記錄空格的下一個(gè)元素（即下一個(gè)字符的開(kāi)始位置）
delSpace(s);
reverse(s, 0, s.size());
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') { // if (s[i] == ' ') 這里這么寫(xiě)字符串尾最后一個(gè)單詞不會(huì)翻轉(zhuǎn)
reverse(s, count, i); // reverse(s, count + 1, i); count = i; 這里這么寫(xiě)第一個(gè)字符不會(huì)被翻轉(zhuǎn)
count = i + 1;
}
}
return s;
}
};
參考詳解
劍指Offer58-II.左旋轉(zhuǎn)字符串
自己審題思路
申請(qǐng)一個(gè)新的數(shù)組，不包含前n個(gè)元素医舆，然后將前n個(gè)元素依次插到數(shù)組后面俘侠。
代碼：
class Solution {
public:
string reverseLeftWords(string s, int n) {
vector<char> str(s.begin() + n, s.end());
for (int i = 0; i < n; i++) {
str.emplace_back(s[i]);
}
return std::string(str.begin(), str.end());
}
};
看完代碼隨想錄題解后的收獲
不申請(qǐng)額外空間的思路：
1、反轉(zhuǎn)區(qū)間為前n的子串
2蔬将、反轉(zhuǎn)區(qū)間為n到末尾的子串
3爷速、反轉(zhuǎn)整個(gè)字符串
代碼
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
參考詳解
今日感悟：
字符串翻轉(zhuǎn)和替換優(yōu)先想到雙指針
