算法學(xué)習(xí)——LeetCode力扣字符串篇

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

344. 反轉(zhuǎn)字符串 - 力扣（LeetCode）

描述

編寫一個(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 碼表中的可打印字符

代碼解析

中間變量交換

class Solution {
public:
    void reverseString(vector<char>& s) {

        char temp;
        
        for(int i=0 ;i<s.size()/2;i++)
        {
            temp = s[i];
            s[i] = s[s.size()-1 - i];
            s[s.size()-1 - i] = temp;
        }
    }
};

使用對(duì)調(diào)函數(shù)

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

使用反轉(zhuǎn)庫(kù)函數(shù)

class Solution {
public:
    void reverseString(vector<char>& s) {

       reverse(s.begin(),s.end());
    }
};

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

541. 反轉(zhuǎn)字符串 II - 力扣（LeetCode）

描述

給定一個(gè)字符串 s 和一個(gè)整數(shù) k，從字符串開(kāi)頭算起，每計(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:
    void rever(string &s ,int left ,int right)
    {
        while(left<right)
        {
            char tmp = s[right];
            s[right] = s[left];
            s[left] = tmp;
            left++;
            right--;
        }
        return;
    }
    string reverseStr(string s, int k) {
       int i=0;
       int flag=1;;
       for(i=0 ; i+k <s.size() ; i+=k)
       {
           if(flag==1) flag = 0;
           else if(flag == 0) 
           {
               flag =1;
               continue;
           }
            int left = i;
            int right = left+k-1;
            rever(s,left,right);
       }
         if( flag==1 ) rever(s,i,s.size()-1);
        return s;
    }
};

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

151. 反轉(zhuǎn)字符串中的單詞 - 力扣（LeetCode）

描述

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

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

返回 單詞 順序顛倒且 單詞 之間用單個(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è) 單詞

進(jìn)階

如果字符串在你使用的編程語(yǔ)言中是一種可變數(shù)據(jù)類型，請(qǐng)嘗試使用 O(1) 額外空間復(fù)雜度的 原地 解法。

代碼解析

雙指針

class Solution {
public:
    string reverseWords(string s) {

       int left=0 ,right=1;
        string result , temp;

        if(s.size()==1) return s;//針對(duì)單一字母
        
        while( left < right && right<s.size() )//找到左指針位置，單詞第一個(gè)字母處
        {
            while(s[left]==' ')
            {
                left++;
                right++;
                if(right > s.size()) %應(yīng)對(duì)單詞后面多個(gè)空格沒(méi)有新單詞，類似“abc        ”
                {
                     result.erase(result.size()-1,1);
                     return result;
                }
            }
            while(s[right]!=' '&& s[right]!='\0')//確定右指針位置，在單詞最后一個(gè)字母后
            {
                right++;
            }
            temp = s.substr(left,right-left);//抽取子串
            temp +=' ';//添加空格
            result.insert(0, temp);//頭插字串

            left = right;
            right= left+1;
        }
        result.erase(result.size()-1,1);//去除最后一個(gè)空格
        return result;
    }
};

低空間復(fù)雜度，反轉(zhuǎn)庫(kù)函數(shù)

首先去除多余空格，之后整個(gè)字符串反轉(zhuǎn)，最后每個(gè)單詞反轉(zhuǎn)

class Solution {
public:
    string reverseWords(string s) {

        int left=0 , right=0;
        //去除多余的空格
        while(right < s.size())
        {
            if(left==0 && s[right] ==' ')
            {
                right++;
            }
            else if(left != 0 &&  s[right-1] ==' '&&s[right] ==' ')
            {
                right++;
            }else
            {
                s[left] = s[right];
                left++;
                right++;
            }
        }
        if(s[left-1]==' ')left--;//針對(duì)最后一個(gè)是空格
        s.resize(left);
        //反轉(zhuǎn)字符串
        reverse(s.begin(),s.end());
        //反轉(zhuǎn)單詞
        left=0 , right=0;
        while(right <= s.size())
        {
            while(s[right] != ' '&& right<s.size()) right++;
            reverse(s.begin() + left, s.begin() + right);
            left = right+1;
            right=left+1;
         }

        return s;
    }
};

低空間復(fù)雜度，無(wú)庫(kù)函數(shù)

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說(shuō)明不是第一個(gè)單詞，需要在單詞前添加空格。
                while (i < s.size() && s[i] != ' ') { //補(bǔ)上該單詞，遇到空格說(shuō)明單詞結(jié)束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即為去除多余空格后的大小。
    }

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

28. 找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)

28. 找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo) - 力扣（LeetCode）

描述

給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開(kāi)始）。如果 needle 不是 haystack 的一部分，則返回 -1 。

示例

示例 1：

輸入：haystack = “sadbutsad”, needle = “sad”
輸出：0
解釋：“sad” 在下標(biāo) 0 和 6 處匹配。
第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ，所以返回 0 。

示例 2：

輸入：haystack = “l(fā)eetcode”, needle = “l(fā)eeto”
輸出：-1
解釋：“l(fā)eeto” 沒(méi)有在 “l(fā)eetcode” 中出現(xiàn)，所以返回 -1 。

提示

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 僅由小寫英文字符組成

代碼解析

庫(kù)函數(shù)

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

暴力法

class Solution {
public:
    int strStr(string haystack, string needle) {

        for(int left=0 ; left < haystack.size() ;left++)
        {
            if(haystack[left] == needle[0])
            {
                for(int right = left ,i=0; right < haystack.size() && i<needle.size(); right++,i++)
                {
                    if(haystack[right] == needle[i])
                    {
                        if(i==needle.size()-1)
                        {
                            return left;
                        }
                        continue;
                    }
                    else break;
                }
            }
        }

        return -1;

    }
};

KMP

class Solution {
public:
    void getNext(int *next ,const string &s)
    {
        int j=-1;
        next[0] = j;
        for(int i=1 ; i<s.size();i++)
        {
            while( j>=0 && s[i] != s[j+1] )
                j = next[j];

            if(s[i] == s[j+1]) j++;
            
            next[i] = j;
        }

    }
    int strStr(string haystack, string needle) {
       if(needle.size() == 0 ) return 0;

       int next[needle.size()];
       int j=-1;
       getNext(next , needle);
       
       for(int i=0 ; i<haystack.size() ;i++)
       {
            while(j>=0 && haystack[i] != needle[j+1])
                j = next[j];

            if(haystack[i] == needle[j+1]) j++;

            if( j == needle.size() - 1 )
                return (i-needle.size()+1);
       }
       return -1;
    }
};

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

459. 重復(fù)的子字符串 - 力扣（LeetCode）

描述

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

示例

示例 1:

輸入: s = “abab”
輸出: true
解釋: 可由子串 “ab” 重復(fù)兩次構(gòu)成。

示例 2:

輸入: s = “aba”
輸出: false

示例 3:

輸入: s = “abcabcabcabc”
輸出: true
解釋: 可由子串 “abc” 重復(fù)四次構(gòu)成。 (或子串 “abcabc” 重復(fù)兩次構(gòu)成。)

提示

• 1 <= s.length <= 104
• s 由小寫英文字母組成

代碼解析

移動(dòng)匹配

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string tmp = s + s;
        tmp.erase(0,1);
        tmp.erase(tmp.size()-1,1);

        if(tmp.find(s) == -1) return false;
        else return true;
    }
};

KMP

代碼隨想錄文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-828627.html

class Solution {
public:
    void getNext(int* next, const string& s)
    {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++)
        {
            while (j >= 0 && s[i] != s[j + 1])
            {
                j = next[j ];
            }
            if (s[i] == s[j + 1]) j++;

            next[i] = j;
        }
    }


    bool repeatedSubstringPattern(string s) {

       if (s.size() == 0) {
            return false;
        }
        int *next = new int[substr.size()];
        //計(jì)算整個(gè)文字串的next數(shù)組，如果文字串是循環(huán)的，一個(gè)循環(huán)next都是-1，之后的從0開(kāi)始遞增。next的最后一位的值=（循環(huán)次數(shù)-1）*循環(huán)體長(zhǎng)度 -1
        getNext(next, s);
        int len = s.size();
        //文字串的長(zhǎng)度減去next數(shù)組最后一位+1 ，得到是循環(huán)體長(zhǎng)度
        // 如果next數(shù)組最后一位不是-1（意味著之前匹配成功） ， 并且文字串長(zhǎng)度對(duì)循環(huán)體長(zhǎng)度可以整除
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) 
        {
            delete[] next;
            return true;
        }
        delete[] next;
        return false;
    }
};

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