前言

歡迎來(lái)到小K的Leetcode|代碼隨想錄|專題化專欄，今天將為大家?guī)?lái)字符串~反轉(zhuǎn)字符串 | 反轉(zhuǎn)字符串 II | 替換空格 | 反轉(zhuǎn)字符串中的單詞 | 左旋轉(zhuǎn)字符串的分享?

344. 反轉(zhuǎn)字符串

?題目鏈接點(diǎn)這里
編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)。輸入字符串以字符數(shù)組 s 的形式給出。不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問(wèn)題。

示例 1：
輸入：s = [“h”,“e”,“l(fā)”,“l(fā)”,“o”]
輸出：[“o”,“l(fā)”,“l(fā)”,“e”,“h”]

示例 2：
輸入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
輸出：[“h”,“a”,“n”,“n”,“a”,“H”]

提示：
1 <= s.length <= 105
s[i] 都是 ASCII 碼表中的可打印字符

就是實(shí)現(xiàn)庫(kù)函數(shù)reverse

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

541. 反轉(zhuǎn)字符串 II

?題目鏈接點(diǎn)這里
給定一個(gè)字符串 s 和一個(gè)整數(shù) k，從字符串開頭算起，每計(jì)數(shù)至 2k 個(gè)字符，就反轉(zhuǎn)這 2k 字符中的前 k 個(gè)字符。如果剩余字符少于 k 個(gè)，則將剩余字符全部反轉(zhuǎn)。
如果剩余字符小于 2k 但大于或等于 k 個(gè)，則反轉(zhuǎn)前 k 個(gè)字符，其余字符保持原樣。

示例 1：
輸入：s = “abcdefg”, k = 2
輸出：“bacdfeg”

示例 2：
輸入：s = “abcd”, k = 2
輸出：“bacd”

提示：
1 <= s.length <= 104
s 僅由小寫英文組成
1 <= k <= 104

分情況討論一下就可以了~

class Solution {
public:
    string reverseStr(string s, int k) {
        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;
    }
};

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;
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        int pos = 0, n = s.size();
        while (pos < n) {
            if (pos + k < n) 
                reverse(s.begin() + pos, s.begin() + pos + k);
            else reverse(s.begin() + pos, s.end());
            pos += 2 * k;
        }
        return s;
    }
};

劍指 Offer 05. 替換空格

?題目鏈接點(diǎn)這里
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串 s 中的每個(gè)空格替換成"%20"。

示例 1：
輸入：s = “We are happy.”
輸出：“We%20are%20happy.”

限制：
0 <= s 的長(zhǎng)度 <= 10000

思路：

擴(kuò)容+雙指針
為什么要從后往前遍歷？

1. 不用申請(qǐng)新數(shù)組。
2. 從后向前填充元素，避免了從前向后填充元素時(shí)，每次添加元素都要將添加元素之后的所有元素向后移動(dòng)的問(wèn)題。

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int sOldSize = s.size();
        for (int i = 0; i < sOldSize; i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        s.resize(sOldSize + 2 * count);
        int sNewSize = s.size();
        for (int i = sOldSize - 1, j = sNewSize - 1; 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;
    }
};

151. 反轉(zhuǎn)字符串中的單詞

?題目鏈接點(diǎn)這里
給你一個(gè)字符串 s ，請(qǐng)你反轉(zhuǎn)字符串中 單詞 的順序。單詞 是由非空格字符組成的字符串。s 中使用至少一個(gè)空格將字符串中的 單詞 分隔開。返回 單詞 順序顛倒且 單詞 之間用單個(gè)空格連接的結(jié)果字符串。注意：輸入字符串 s中可能會(huì)存在前導(dǎo)空格、尾隨空格或者單詞間的多個(gè)空格。返回的結(jié)果字符串中，單詞間應(yīng)當(dāng)僅用單個(gè)空格分隔，且不包含任何額外的空格。

示例 1：
輸入：s = “the sky is blue”
輸出：“blue is sky the”

示例 2：
輸入：s = " hello world "
輸出：“world hello”
解釋：反轉(zhuǎn)后的字符串中不能存在前導(dǎo)空格和尾隨空格。

示例 3：
輸入：s = “a good example”
輸出：“example good a”
解釋：如果兩個(gè)單詞間有多余的空格，反轉(zhuǎn)后的字符串需要將單詞間的空格減少到僅有一個(gè)。

提示：
1 <= s.length <= 104
s 包含英文大小寫字母、數(shù)字和空格 ’ ’
s 中 至少存在一個(gè) 單詞

思路：

1. 移除多余空格
2. 將整個(gè)字符串反轉(zhuǎn)
3. 將每個(gè)單詞反轉(zhuǎn)
   移除多于空格大家可以參照移除元素，思路是一模一樣的，最后的單詞翻轉(zhuǎn)if (i == s.size() || s[i] == ' ')是到達(dá)單詞末尾或者遇到空格，翻轉(zhuǎn)

lass 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]);
        }
    }
    void removeExtraSpace(string& s) {
        int slow = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                if (slow != 0) {
                    s[slow++] = ' ';
                }
                while (i < s.size() && s[i] != ' ') {
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }
    string reverseWords(string s) {
        removeExtraSpace(s);
        reverse(s, 0, s.size() - 1);
        int start = 0;
        for (int i = 0;i <= s.size(); i++) {
            if (i == s.size() || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        return s;
    }
};

劍指 Offer 58 - II. 左旋轉(zhuǎn)字符串

?題目鏈接點(diǎn)這里
字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個(gè)字符轉(zhuǎn)移到字符串的尾部。請(qǐng)定義一個(gè)函數(shù)實(shí)現(xiàn)字符串左旋轉(zhuǎn)操作的功能。比如，輸入字符串"abcdefg"和數(shù)字2，該函數(shù)將返回左旋轉(zhuǎn)兩位得到的結(jié)果"cdefgab"。

示例 1：
輸入: s = “abcdefg”, k = 2
輸出: “cdefgab”

示例 2：
輸入: s = “l(fā)rloseumgh”, k = 6
輸出: “umghlrlose”

限制：
1 <= k < s.length <= 10000

思路：

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;
    }
};

總結(jié)

字符串第一感覺(jué)很樸實(shí)，但是要提高執(zhí)行效率，還是可以玩的很花的，比如反轉(zhuǎn)~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-609397.html

到了這里，關(guān)于【代碼隨想錄 | Leetcode | 第十一天】字符串 | 反轉(zhuǎn)字符串 | 反轉(zhuǎn)字符串 II | 替換空格 | 反轉(zhuǎn)字符串中的單詞 | 左旋轉(zhuǎn)字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！