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

原題鏈接

解題思路：

雙指針：自己的

1. 雙指針，左指針指向開頭，右指針指向末尾。
2. 交換兩個(gè)左右指針。
3. 左右指針向中間移動(dòng)。

時(shí)間復(fù)雜度：O(n)；
空間復(fù)雜度：O(1)；

實(shí)現(xiàn)代碼：

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int l = 0, r = n - 1;
        while (l < r) {
            swap(s[l ++], s[r --]);
        }
        return ;
    }
};

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

原題鏈接

解題思路：

分類討論：自己的

分類討論：

1. 如果剩余字符少于k個(gè)，則將剩余字符全部反轉(zhuǎn)。
2. 如果剩余字符大于或等于k個(gè)，則反轉(zhuǎn)前k個(gè)字符,其余字符保持原樣?？梢悦看翁幚?k個(gè)字符，判斷并調(diào)用庫函數(shù)reverse進(jìn)行反轉(zhuǎn)操作。

時(shí)間復(fù)雜度：O(n/2) = O(n)；
空間復(fù)雜度：O(1)；

實(shí)現(xiàn)代碼：

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();

        for (int i=0; i < n; i += 2*k) {
            //2k < n 的情況：
            if (2*k <= n - i) {
                reverse (s.begin() + i, s.begin() + i + k);
            }
            // k <= n < 2k
            else if (n-i >= k) {
                reverse(s.begin() + i, s.begin() + i + k);
            }
            // n < k；
            else {
                reverse (s.begin() + i, s.end());
            }
        }

        return s;
    }
};

優(yōu)化：

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();

        for (int i=0; i < n; i += 2*k) {
            if (k <= n - i) {
                reverse (s.begin() + i, s.begin() + i + k);
            }
            else {
                reverse (s.begin() + i, s.end());
            }
        }
        return s;
    }
};

劍指Offer 05.替換空格

原題鏈接

解題思路：

原數(shù)組上替換空格：自己的

1. 擴(kuò)充字符串的長(zhǎng)度，由于一個(gè)空格 = “%20”，即相當(dāng)于三個(gè)字符，等價(jià)于多了兩個(gè)字符。
2. 通過resize()函數(shù)，重新設(shè)置大小。即統(tǒng)計(jì)空格的數(shù)量，新字符串的大小 = 原字符串長(zhǎng)度的大小 + 空格數(shù)量 * 2；
3. 所以第一步是統(tǒng)計(jì)空格的數(shù)量。
4. 第二步擴(kuò)容。
5. 第三步：從后往前遍歷字符串，將一個(gè)指針指向新字符串的末尾。另一個(gè)指針指向舊字符串的末尾，然后若當(dāng)前舊字符串的指針指向的是字母，則將其丟給新的字符串。如果是空格的話，則先處理新字符串的指針，從后往前填充三個(gè)字符：“%20”；然后再使得新舊字符串的指針同時(shí)向前移動(dòng)！

實(shí)現(xiàn)代碼：

class Solution {
public:
    string replaceSpace(string s) {
        int cnt=0;
        int old = s.size();
        for (int i=0; i <  old; i ++) {
            if (s[i] == ' ') {
                cnt ++;
            }
        }

        s.resize(old + cnt * 2);

        int n = s.size();
        for (int l = old-1, r=n-1; l < r; l --, r --) {
            if (s[l] != ' ') {
                s[r] = s[l];
            }
            else {
                s[r--] = '0';
                s[r--] = '2';
                s[r] = '%';
            }
        }
        return s;
    }
};

151.翻轉(zhuǎn)字符串里的單詞

原題鏈接

解題思路：

雙指針：別人的

本題要求返回單詞順序顛倒且單詞之間用單個(gè)空格連接的結(jié)果字符串。僅反轉(zhuǎn)字符串中單詞的順序，單詞本身并沒有反轉(zhuǎn)。也就是說，最后一個(gè)單詞反轉(zhuǎn)到第一個(gè)位置，單詞本身沒有變?？梢韵确崔D(zhuǎn)整個(gè)字符串，然后再反轉(zhuǎn)每個(gè)單詞，在反轉(zhuǎn)過程中，去掉多余空格。

如何反轉(zhuǎn)單詞 ：
用start變量掃描字符串，遇到第一個(gè)非空格字符時(shí)，end=start;讀取字符s[end]，放入s[i]，然后end++，i++，i用來控制反轉(zhuǎn)后的字符串下標(biāo)，當(dāng)s[end]為空格時(shí)，就找到了一個(gè)單詞。使用reverse函數(shù)反轉(zhuǎn)該單詞更新start為end，反轉(zhuǎn)下一個(gè)單詞。

實(shí)現(xiàn)代碼：

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        reverse(s.begin(), s.end());
        int i=0;
        for (int start = 0; start < n; start ++) {
            //先找到第一個(gè)不為空格的字符，等于跳過行首空格！
            if (s[start] != ' ') {
                //單詞之間加個(gè)空格：
                if (i != 0) {   //i!=0，是為了排除行首添加空格！
                    s[i ++] = ' ';
                }
                int end = start;
                //不停尋找當(dāng)前單詞的末尾，直到找到空格為止，則當(dāng)前單詞一定是在[start, end)；
                while (end < n && s[end] != ' ') {
                    s[i ++] = s[end ++];
                }
                //翻轉(zhuǎn)單詞，由于i指向的是末尾，所以通過計(jì)算當(dāng)前單詞的長(zhǎng)度，然后求得左右端點(diǎn)
                //然后反轉(zhuǎn)區(qū)間內(nèi)的單詞。
                reverse (s.begin() + i - (end - start), s.begin() + i);
                // 處理下一個(gè)單詞
                start = end;
            }
        }
        s.erase (s.begin() + i, s.end());
        return s;
    }
};

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

原題鏈接

解題思路：

局部反轉(zhuǎn) ->整體反轉(zhuǎn)：

題意：將字符串的前n個(gè)字符移動(dòng)到末尾。
而我們的reverse函數(shù)翻轉(zhuǎn)的話，會(huì)改變單詞之間的順序。
但很重要的一點(diǎn)是：一個(gè)字符串，進(jìn)行兩次reverse翻轉(zhuǎn)的話，等價(jià)于沒有變動(dòng)！

所以我們可以先將前 n 個(gè)字符串進(jìn)行翻轉(zhuǎn)，然后再將 第 n 個(gè) 之后的字符串進(jìn)行翻轉(zhuǎn)。（兩次局部的翻轉(zhuǎn)）

然后再整體翻轉(zhuǎn)：則得到理想的效果！

若先整體翻轉(zhuǎn)的話，的確，我們想要的字符串部分，是移動(dòng)到了末尾，但是字符串內(nèi)部的字符順序是顛倒的，也可以這時(shí)候來索引n，劃分區(qū)間，然后進(jìn)行兩次局部翻轉(zhuǎn)。不過這時(shí)候的話：區(qū)間為：[… ，倒數(shù)第n個(gè)]，[倒數(shù)第n個(gè)，之后]；

不過倒數(shù)的n，不如正數(shù)的n；

總之：兩次局部翻轉(zhuǎn) + 一次整體翻轉(zhuǎn)！

實(shí)現(xiàn)代碼：

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é)：

雙指針還可以用來翻轉(zhuǎn)字符串、索引區(qū)間、原數(shù)組上更新、文章來源地址http://www.zghlxwxcb.cn/news/detail-616537.html

到了這里，關(guān)于力扣 [344、541、劍指offer 05.、151、劍指offer58-ll]的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！