1.反轉字符串（要求O(1)的額外空間）
LeetCode鏈接
編寫一個函數(shù)，其作用是將輸入的字符串反轉過來。輸入字符串以字符數(shù)組 s 的形式給出。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。
- swap常見的兩種交換形式
- 常見的值交換
- 通過位運算
class Solution {
public:
void reverseString(vector<char>& s) {
int l=0, h=s.size()-1;
char temp;
while(l<=h){
// temp = s[l];
// s[l++] = s[h];
// s[h--] = temp;
swap(s[l++], s[h--]);
}
}
};
2. 反轉字符串2
LeetCode鏈接
給定一個字符串 s 和一個整數(shù) k，從字符串開頭算起，每計數(shù)至 2k 個字符，就反轉這 2k 字符中的前 k 個字符。
如果剩余字符少于 k 個，則將剩余字符全部反轉。
如果剩余字符小于 2k 但大于或等于 k 個，則反轉前 k 個字符，其余字符保持原樣。
- 在寫循環(huán)的時候，可以直接每次+2*k
- 每次判斷+k是否符超出size的范圍
class Solution {
public:
void reverse(string &s, int start, int end){ // 這里是左閉右開
for(int i=start, j=end; i<j; i++, j--){
swap(s[i], s[j]);
}
}
string reverseStr(string s, int k) {
for(int i=0; i<s.size(); i+=(2*k)){
if(i + k <= s.size()){
reverse(s, i, i+k-1);
}else{
reverse(s, i, s.size()-1);
}
}
return s;
}
};
3.替換空格
LeetCode鏈接
請實現(xiàn)一個函數(shù)，把字符串 s 中的每個空格替換成"%20"。
- 卡哥建議：對于線性數(shù)據(jù)結構，填充或者刪除，后序處理會高效的多。好好體會一下。(4中的刪除后序會跟高效嗎)
- resize() 重新分配空間
- 一個指針指向舊的地址，新指針指向新的地址
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 統(tǒng)計空格出現(xiàn)的次數(shù)
for(int i=0; i<s.size(); i++){
if(s[i] == ' '){
count++;
}
}
int i=s.size()-1, j=s.size()+2*count - 1;
s.resize(s.size() + 2*count);
// 從后往前，使用雙指針法，快指針指向原來的為末尾，慢指針指向新的末尾
for(; i>=0; i--, j--){
if(s[i] != ' '){
s[j] = s[i];
}else{
s[j] = '0';
s[j-1] = '2';
s[j-2] = '%';
j-=2;
}
}
return s;
}
};
4.反轉字符串中的單詞
LeetCode鏈接
- 給你一個字符串 s ，請你反轉字符串中 單詞 的順序。
- 單詞 是由非空格字符組成的字符串。s 中使用至少一個空格將字符串中的 單詞 分隔開。
- 返回 單詞 順序顛倒且 單詞 之間用單個空格連接的結果字符串。
- 注意：輸入字符串 s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。
- 先去除字符串中多余的空格(刪除單個字符建議從后向前進行)
- 直接反轉整合字符串
- 最后反轉字符串中的每個單詞
class Solution {
public:
// 1.去除多余的空格
void replaceWhite(string &s){
// 1. 如果字符串開頭全是空格，就先遍歷high直到不是空格位置
int low = 0, high = 0; // 定義快慢指針
while(high<s.size() && s[high] == ' ') high++;
// 2.去除字符串中間的空格
// while(high < s.size()){
// // 去掉字符串中間冗余的空格
// if(s[high]!=' ' && s[high+1] == ' '){
// s[low++] = s[high];
// s[low++] = ' ';
// }else if(s[high] != ' '){
// s[low++] = s[high];
// }
// high++;
// }
for(; high<s.size(); high++){
if(high-1 > 0 && s[high-1]==s[high] && s[high]== ' '){ // 如果當前字符是' '并且前一個字符是空
continue; // 不做任何處理
}else{
s[low++] = s[high]; // 如果不是空格，并且是字符后的第一個空格就復制
}
}
// 3.去除字符串末尾的空格
if(low - 1 > 0 && s[low-1] == ' '){
s.resize(low-1);
}else{
s.resize(low);
}
}
// 雙指針法快速刪除多余空格
void removeExtraSpace(string &s){
int low = 0;
for(int i=0; i<s.size(); i++){
if(s[i] != ' '){
if(low != 0) s[low++] = ' ';
while(i < s.size() && s[i] != ' '){
s[low++] = s[i++];
}
}
}
s.resize(low);
}
// 2.反轉整個字符串
void reverseString(string &s){
for(int i=0, j=s.size()-1; i<=j; i++, j--){
swap(s[i], s[j]);
}
}
// 3.反轉每個單詞
void reverseSingleWord(string &s, int start, int end){
for(int i=start, j=end; i<j; i++, j--){ // 左閉右閉
swap(s[i], s[j]);
}
}
string reverseWords(string s) {
replaceWhite(s);
reverseString(s);
for(int i=0, j=0; j<=s.size(); j++){
if(j==s.size() || s[j]==' '){ // 到達最后一個單詞 或者是遇到了空格
reverseSingleWord(s, i, j-1); //
i = j+1;
}
}
return s;
}
};
5. 劍指Offer58-II.左旋轉字符串
LeetCode鏈接文章來源：http://www.zghlxwxcb.cn/news/detail-439552.html
字符串的左旋轉操作是把字符串前面的若干個字符轉移到字符串的尾部。請定義一個函數(shù)實現(xiàn)字符串左旋轉操作的功能。比如，輸入字符串"abcdefg"和數(shù)字2，該函數(shù)將返回左旋轉兩位得到的結果"cdefgab"。文章來源地址http://www.zghlxwxcb.cn/news/detail-439552.html
- 先反轉前半部分和后半部分，再整體反轉
class Solution {
public:
void reverse(string &s, int start, int end){
while(start <= end){
swap(s[start++], s[end--]);
}
}
string reverseLeftWords(string s, int n) {
// 1.先反轉前半部分和后半部分，再反轉整體
reverse(s, 0, n-1);
reverse(s, n, s.size()-1);
reverse(s, 0, s.size()-1);
return s;
}
};
到了這里，關于第8天-代碼隨想錄刷題訓練-字符串● 344.反轉字符串 ● 541. 反轉字符串II ● 劍指Offer 05.替換空格 ● 151.翻轉字符串里的單詞 ● 劍指Offer58-II.左旋轉字符串的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
