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

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

（1）方法：雙指針

1.將 left 指向字符數(shù)組首元素，right 指向字符數(shù)組尾元素。

2.當(dāng) left < right：

交換 s[left] 和 s[right]；

3.left 指針右移一位，即 left = left + 1；

4.right 指針左移一位，即 right = right - 1。

5.當(dāng) left >= right，反轉(zhuǎn)結(jié)束，返回字符數(shù)組即可。

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

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

給定一個(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）方法一：模擬

我們直接按題意進(jìn)行模擬：反轉(zhuǎn)每個(gè)下標(biāo)從 2k 的倍數(shù)開始的，長(zhǎng)度為 k 的子串。若該子串長(zhǎng)度不足 k，則反轉(zhuǎn)整個(gè)子串。

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.length();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};

（2）方法二：雙指針

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

3.leetcode-劍指 Offer 05. 替換空格

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串 s 中的每個(gè)空格替換成"%20"。

（1）方法一：遍歷字符串

1.創(chuàng)建一個(gè)空字符串a(chǎn)ns，用于存儲(chǔ)替換空格字符后的結(jié)果。

2.對(duì)于字符串s中的每個(gè)字符a，進(jìn)行以下判斷：

3.如果字符a是空格字符（即a==’ '），則在ans字符串中依次添加字符 ‘%’、‘2’、‘0’。這相當(dāng)于用"%20"來替換每個(gè)空格字符。

4.如果字符a不是空格字符，則直接將字符a添加到ans字符串中。

5.循環(huán)結(jié)束后，將得到的ans字符串作為結(jié)果進(jìn)行返回。

class Solution {
public:
    string replaceSpace(string s) {
        string ans;
        for(auto& a:s)
        {
            if(a==' ')
            {
                ans.push_back('%');
                ans.push_back('2');
                ans.push_back('0');
            }
            else
            {
                ans.push_back(a);
            }
        }
        return ans;
    }
};

（2）方法二：數(shù)組填充

如果想把這道題目做到極致，就不要只用額外的輔助空間了！

首先擴(kuò)充數(shù)組到每個(gè)空格替換成"%20"之后的大小。

然后從后向前替換空格，也就是雙指針法，過程如下：

i指向新長(zhǎng)度的末尾，j指向舊長(zhǎng)度的末尾。

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 統(tǒng)計(jì)空格的個(gè)數(shù)
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 擴(kuò)充字符串s的大小，也就是每個(gè)空格替換成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 從后先前將空格替換為"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

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

給你一個(gè)字符串 s ，請(qǐng)你反轉(zhuǎn)字符串中 單詞 的順序。

單詞 是由非空格字符組成的字符串。s 中使用至少一個(gè)空格將字符串中的 單詞 分隔開。

返回 單詞 順序顛倒且 單詞 之間用單個(gè)空格連接的結(jié)果字符串。

注意：輸入字符串 s中可能會(huì)存在前導(dǎo)空格、尾隨空格或者單詞間的多個(gè)空格。返回的結(jié)果字符串中，單詞間應(yīng)當(dāng)僅用單個(gè)空格分隔，且不包含任何額外的空格。

（1）方法一：棧模擬

1.創(chuàng)建一個(gè)棧 s1 用于存儲(chǔ)每個(gè)單詞。

2.創(chuàng)建一個(gè)空字符串 word 用于暫存每個(gè)單詞。

3.創(chuàng)建一個(gè)空字符串 result 用于存儲(chǔ)最終的翻轉(zhuǎn)結(jié)果。

4.對(duì)于字符串s中的每個(gè)字符a，進(jìn)行以下判斷：

*如果字符a不是空格字符（即a != ’ ')，說明當(dāng)前字符屬于一個(gè)單詞的一部分，則將其添加到 word 字符串中。

*如果字符a是空格字符，并且 word 字符串非空，說明一個(gè)完整單詞結(jié)束了，將 word 字符串壓入棧 s1 中，并重置 word 為空字符串。

*如果循環(huán)結(jié)束后，word 不為空，說明最后一個(gè)單詞還未壓入棧中，所以將它壓入棧 s1 中。

5.當(dāng)棧 s1 非空時(shí)，依次將棧頂?shù)膯卧~彈出并添加到 result 字符串的末尾，并附加一個(gè)空格。

6.如果 result 非空，那么最后一個(gè)字符是多余的空格，所以將它從 result 中移除。

7.將最終的結(jié)果 result 返回。

class Solution {
public:
    string reverseWords(string s) {
        stack<string> s1;
        string word;
        string result;
        for(auto& a:s)
        {
            if(a!=' ')
            {
                word+=a;
            }
            else if(a==' '&&!word.empty())
            {
                s1.push(word);
                word="";
            }
        }
        if(!word.empty())
        {
            s1.push(word);
        }
        while(!s1.empty())
        {
            result+=s1.top()+' ';
            s1.pop();
        }
        if(!result.empty())
        {
            result.pop_back();
        }
        return result;
    }
};

（2）方法二：雙指針

使用雙指針法來去移除空格，最后resize（重新設(shè)置）一下字符串的大小，就可以做到O(n)的時(shí)間復(fù)雜度。

void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定義快指針，慢指針
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中間部分的冗余空格
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // 重新設(shè)置字符串大小
    }
}

有的同學(xué)可能發(fā)現(xiàn)用erase來移除空格，在leetcode上性能也還行。主要是以下幾點(diǎn)；：

leetcode上的測(cè)試集里，字符串的長(zhǎng)度不夠長(zhǎng)，如果足夠長(zhǎng)，性能差距會(huì)非常明顯。
leetcode的測(cè)程序耗時(shí)不是很準(zhǔn)確的。
版本一的代碼是一般的思考過程，就是 先移除字符串前的空格，再移除中間的，再移除后面部分。

不過其實(shí)還可以優(yōu)化，這部分和27.移除元素 (opens new window)的邏輯是一樣一樣的，本題是移除空格，而 27.移除元素 就是移除元素。

所以代碼可以寫的很精簡(jiǎn)，大家可以看 如下 代碼 removeExtraSpaces 函數(shù)的實(shí)現(xiàn)：

// 版本二 
void removeExtraSpaces(string& s) {//去除所有空格并在相鄰單詞之間添加空格, 快慢指針。
    int slow = 0;   //整體思想?yún)⒖糷ttps://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就處理，即刪除所有空格。
            if (slow != 0) s[slow++] = ' '; //手動(dòng)控制空格，給單詞之間添加空格。slow != 0說明不是第一個(gè)單詞，需要在單詞前添加空格。
            while (i < s.size() && s[i] != ' ') { //補(bǔ)上該單詞，遇到空格說明單詞結(jié)束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即為去除多余空格后的大小。
}

還要實(shí)現(xiàn)反轉(zhuǎn)字符串的功能，支持反轉(zhuǎn)字符串子區(qū)間，這個(gè)實(shí)現(xiàn)我們分別在344.反轉(zhuǎn)字符串 (opens new window)和541.反轉(zhuǎn)字符串II (opens new window)里已經(jīng)講過了。

代碼如下：

// 反轉(zhuǎn)字符串s中左閉右閉的區(qū)間[start, end]
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}

整體代碼如下：

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻轉(zhuǎn)，區(qū)間寫法：左閉右閉 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相鄰單詞之間添加空格, 快慢指針。
        int slow = 0;   //整體思想?yún)⒖糷ttps://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就處理，即刪除所有空格。
                if (slow != 0) s[slow++] = ' '; //手動(dòng)控制空格，給單詞之間添加空格。slow != 0說明不是第一個(gè)單詞，需要在單詞前添加空格。
                while (i < s.size() && s[i] != ' ') { //補(bǔ)上該單詞，遇到空格說明單詞結(jié)束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即為去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保證單詞之間之只有一個(gè)空格，且字符串首尾沒空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保證第一個(gè)單詞的開始下標(biāo)一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到達(dá)空格或者串尾，說明一個(gè)單詞結(jié)束。進(jìn)行翻轉(zhuǎn)。
                reverse(s, start, i - 1); //翻轉(zhuǎn)，注意是左閉右閉 []的翻轉(zhuǎn)。
                start = i + 1; //更新下一個(gè)單詞的開始下標(biāo)start
            }
        }
        return s;
    }
};

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

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

（1）方法一：模擬

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

（2）方法二：string函數(shù)

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        s.append(s.substr(0,n));
        s.erase(s.begin(),s.begin()+n);
        return s;
    }
};

6.leetcode-459. 重復(fù)的子字符串

給定一個(gè)非空的字符串 s ，檢查是否可以通過由它的一個(gè)子串重復(fù)多次構(gòu)成。

（1）方法一：枚舉

1.首先獲取字符串s的長(zhǎng)度，用變量n表示。

2.通過遍歷的方式嘗試找到可能的重復(fù)子字符串的長(zhǎng)度。從1開始遍歷到n的一半（i*2<=n），以保證子字符串的長(zhǎng)度不超過原字符串的一半。

3.當(dāng)找到一個(gè)可能的重復(fù)子字符串長(zhǎng)度i后，判斷原字符串是否可以被i整除（即n%i==0），如果可以整除，則繼續(xù)判斷是否存在重復(fù)子字符串的情況。

4.進(jìn)入內(nèi)層循環(huán)，從第i個(gè)字符開始遍歷到字符串末尾。對(duì)于每個(gè)位置 j，檢查當(dāng)前位置字符s[j]是否與距離i個(gè)位置之前的字符s[j-i]相等，如果不相等，則說明不是重復(fù)子字符串。

5.如果內(nèi)層循環(huán)完全遍歷，并且沒有發(fā)現(xiàn)不匹配的情況，則標(biāo)記變量match為true，表示存在重復(fù)子字符串，并立即返回true。

6.如果外層循環(huán)結(jié)束，仍沒有返回true，則說明不存在重復(fù)子字符串，返回false。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n=s.size();
        for(int i=1;i*2<=n;++i)
        {
            if(n%i==0)
            {
                bool match=true;
                for(int j=i;j<n;++j)
                {
                    if(s[j]!=s[j-i])
                    {
                        match=false;
                        break;
                    }
                }
                if(match)
            {
                return true;
            }
            }
        }
        return false;
    }
};

（2）方法二：字符串匹配

1.將原字符串s與自身進(jìn)行拼接，得到一個(gè)新的字符串。例如，如果s是"abc"，那么(s + s)的結(jié)果是"abcabc"。

2.使用字符串的find函數(shù)來在拼接后的字符串中查找原字符串s的第一個(gè)出現(xiàn)位置。函數(shù)的參數(shù)為要查找的子字符串s和搜索起始位置為1（即從第二個(gè)字符開始搜索）。

3.將查找結(jié)果與原字符串s的大小進(jìn)行比較。如果二者相等，表示在拼接后的字符串中，只有一個(gè)出現(xiàn)位置，即沒有重復(fù)的子字符串。如果不相等，表示在拼接后的字符串中存在多個(gè)子字符串的出現(xiàn)位置，即存在重復(fù)的子字符串。

4.根據(jù)比較結(jié)果，如果存在重復(fù)的子字符串，則返回true；否則，返回false。文章來源地址http://www.zghlxwxcb.cn/news/detail-690081.html

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

到了這里，關(guān)于【算法刷題之字符串篇】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！