子數(shù)組系列題目

1.最??數(shù)組和

力扣鏈接：力扣

給你一個整數(shù)數(shù)組?nums?，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

子數(shù)組?是數(shù)組中的一個連續(xù)部分。

?這道題是子數(shù)組問題中的經(jīng)典問題，同時也非常簡單，題目告訴子數(shù)組可以是一個元素，在這里要注意子數(shù)組和子序列的區(qū)別（子數(shù)組是連續(xù)的，子序列可以連續(xù)可以不連續(xù)，子序列包含了子數(shù)組）

1.狀態(tài)表示

根據(jù)經(jīng)驗我們就以常用的以某一個位置為結(jié)尾來定義狀態(tài)表示，如果可以推出狀態(tài)轉(zhuǎn)移方程，那么我們的狀態(tài)表示就是沒有問題的，如果推不出來狀態(tài)轉(zhuǎn)移方程，那么就需要重新狀態(tài)表示。

dp[i]表示以i位置為結(jié)尾的連續(xù)子數(shù)組的最大和

2.狀態(tài)轉(zhuǎn)移方程

我們要求狀態(tài)轉(zhuǎn)移方程，首先要看如何求i位置的最大和，這里其實只有兩種情況1.我們的i位置的數(shù)比前面的所有子數(shù)組的最大和加上我們i位置的數(shù)都要大，那么i位置的最大和就是nums[i]。如果i位置前面的所有連續(xù)子數(shù)組的最大和加上i位置的值是小于前面的所有連續(xù)子數(shù)組的最大和的，那么i位置的最大和就是前面的所有連續(xù)子數(shù)組的最大和。我們的狀態(tài)表示是以i位置為結(jié)尾的連續(xù)子數(shù)組的最大和，那么i位置前面的i-1不就是前面的所有子數(shù)組的最大和嗎，所以狀態(tài)轉(zhuǎn)移方程為：

dp[i] = max(dp[i-1]+nums[i],nums[i])

3.初始化

從狀態(tài)轉(zhuǎn)移方程中我們可以看到只有第一個位置會越界，所以我們初始化dp[0]即可，一個元素的最大和就是這個元素本身，所以dp[0] = nums[0]

4.填表

從左向右

5.返回值

我們dp表中存放的是從0~n-1每一個位置為結(jié)尾的連續(xù)子數(shù)組的最大和，所以返回的是表中最大的值。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       int n = nums.size();
       vector<int> dp(n,0);
       dp[0] = nums[0];
       int ret = dp[0];
       for (int i = 1;i<n;i++)
       {
           dp[i] = max(dp[i-1]+nums[i],nums[i]);
           ret = max(dp[i],ret);
       }
       return ret;
    }
};

2.環(huán)形子數(shù)組的最大和

力扣鏈接：力扣

給定一個長度為?n?的環(huán)形整數(shù)數(shù)組?nums?，返回?nums?的非空?子數(shù)組?的最大可能和?。

環(huán)形數(shù)組?意味著數(shù)組的末端將會與開頭相連呈環(huán)狀。形式上，?nums[i]?的下一個元素是?nums[(i + 1) % n]?，?nums[i]?的前一個元素是?nums[(i - 1 + n) % n]?。

子數(shù)組?最多只能包含固定緩沖區(qū)?nums?中的每個元素一次。形式上，對于子數(shù)組?nums[i], nums[i + 1], ..., nums[j]?，不存在?i <= k1, k2 <= j?其中?k1 % n == k2 % n?。

?對于環(huán)形的問題，我們的解決辦法一般都是將環(huán)形問題轉(zhuǎn)換成普通子數(shù)組問題，下面我們分析一下：

1.狀態(tài)表示

首先我們還是根據(jù)經(jīng)驗將狀態(tài)表示為：dp[i]表示以i位置為結(jié)尾的子數(shù)組最大和，這個時候我們發(fā)現(xiàn)這一個狀態(tài)表示無法解決下面這種情況：

紅色劃線部分就是環(huán)形區(qū)域，對于在環(huán)形區(qū)域的最大和我們無法用第一個狀態(tài)表示求出，那么如何將這個環(huán)形問題轉(zhuǎn)化為普通問題呢？其實我們只需要求出中間這部分區(qū)域的子數(shù)組的最小和：

?因為我們每次求出的都是一段連續(xù)的子數(shù)組，所以當我們求出從0~n-1位置以其中任何位置為結(jié)尾的子數(shù)組的最小值，那么一旦最大值是在環(huán)形區(qū)域，我們只需要讓整個數(shù)組的和減去最小值那么就得到了環(huán)形區(qū)域的最大和。

f[i]表示以i位置為結(jié)尾的子數(shù)組最大和。

g[i]表示以i位置為結(jié)尾的子數(shù)組的最小和。

2.狀態(tài)轉(zhuǎn)移方程

f[i] = max(f[i-1] + nums[i],nums[i])

g[i] = min(g[i-1]+nums[i],nums[i])

3.初始化

通過狀態(tài)轉(zhuǎn)移方程我們可以看到只有第一個位置會越界，所以只初始化第一個位置。

f[0] = nums[0],g[0] = nums[0]

4.填表

從左向右，兩個表一起填

5.返回值

返回f表中最大值和sum-g表中最小值的最大值：

return max(fmax,sum-gmin),但是這里還有一個小細節(jié)：

如果數(shù)組中全是負數(shù)的話，那么我們求出的子數(shù)組中的最小和就是整個數(shù)組的和，這種情況下最大值只有f表中存在，如果像上面那樣就會發(fā)現(xiàn)sum-gmin==0,0肯定比fmax大就返回0了，實際上我們要返回的是數(shù)組中的最大值，0不是數(shù)組中的值所以不能返回，所以正確的返回是：

return sum==gmin?fmax:max(fmax,sum-gmin)

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
       int n = nums.size();
       if (n==1) return nums[0];
       vector<int> f(n,0),g(n,0);
       f[0] = nums[0];
       g[0] = nums[0];
       int fmax = INT_MIN;
       int gmin = INT_MAX;
       int sum = nums[0];
       for (int i = 1;i<n;i++)
       {
           f[i] = max(f[i-1]+nums[i],nums[i]);
           fmax = max(f[i],fmax);
           g[i] = min(g[i-1]+nums[i],nums[i]);
           gmin = min(g[i],gmin);
           sum+=nums[i];
       }
       return sum==gmin?fmax:max(fmax,sum-gmin);
    }
};

當我們運行起來發(fā)現(xiàn)當數(shù)組只有一個元素的時候是跑不過的，因為只有一個元素的時候不會進入for循環(huán)，直接就return了，但是這個時候fmax還是整形最小值,gmin還是整形最大值，max()中做判斷的時候sum-gmin就會發(fā)生整形溢出，所以只有一個元素的時候我們直接返回這個元素即可。

3.乘積最??數(shù)組

力扣鏈接：力扣

給你一個整數(shù)數(shù)組?nums?，請你找出數(shù)組中乘積最大的非空連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字），并返回該子數(shù)組所對應(yīng)的乘積。

測試用例的答案是一個?32-位?整數(shù)。

子數(shù)組?是數(shù)組的連續(xù)子序列。

1.狀態(tài)表示

我們假如以前面的經(jīng)驗以dp[i]表示以i位置為結(jié)尾的子數(shù)組的最大乘積的話，代碼寫出來與上一題并沒有多少差別，但是允許的時候只能過一般測試用例，這是因為數(shù)中有負數(shù)的存在，負數(shù)與最小的負數(shù)相乘就是一個大的正數(shù)，這一點用一個狀態(tài)是解決不了的，所以：

f[i]表示i位置為結(jié)尾的子數(shù)組的最大乘積

g[i]表示i位置為結(jié)尾的子數(shù)組的最小乘積

2.狀態(tài)轉(zhuǎn)移方程

我們以i位置劃分，發(fā)現(xiàn)i位置有三種狀態(tài)，n[i]大于0或者n[i]小于0或者n[i]等于0，對于等于0的狀態(tài)，乘任何數(shù)還是0，所以可以先不用考慮，當n[i]大于0時，最大值有可能是n[i]*f[i-1]也有可能是n[i]，最小值有可能是n[i]*g[i-1]也有可能是n[i]。

所以：當n[i]>0,f[i] = max(f[i-1]*n[i],n[i])? ,? g[i] = min(g[i-1]*n[i],n[i])

對于n[i]<0的情況，與上面的相反：

當n[i]<0,f[i] = max(n[i]*g[i-1],n[i])? ,? g[i] = min(f[i-1]*n[i],n[i])

3.初始化

第一個位置會越界，所以初始化兩個表第一個位置：

f[0] = g[0] = nums[0]

4.填表

兩個表一起填，從左向右。

5.返回值?

返回f表中的最大值

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n==1) return nums[0];
        vector<int> f(n,0),g(n,0);
        f[0] = g[0] = nums[0];
        int ret = f[0];
        for (int i = 1;i<n;i++)
        {
            if (nums[i]>0)
            {
                f[i] = max(nums[i]*f[i-1],nums[i]);
                g[i] = min(g[i-1]*nums[i],nums[i]);
            }
            else if(nums[i]<0)
            {
                f[i] = max(nums[i]*g[i-1],nums[i]);
                g[i] = min(f[i-1]*nums[i],nums[i]);
            }
            ret = max(ret,f[i]);
        }
        return ret;
    }
};

當我們初始化第1一個位置時會出現(xiàn)兩個問題，一個數(shù)的時候無法進入for循環(huán)，所以需要提前處理一個數(shù)的情況。當nums[0]是f表中最大值時，我們發(fā)現(xiàn)如果讓ret是整形最小值時是不能通過程序的，所以我們可以將ret初始化為f[0]。

當然我們上面的寫法實際上優(yōu)點繁瑣，下面我們用開虛擬節(jié)點的方式簡化一下代碼：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n+1,0),g(n+1,0);
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for (int i = 1;i<=n;i++)
        {
            f[i] = max(nums[i-1],max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
            g[i] = min(nums[i-1],min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));
            ret = max(ret,f[i]);
        }
        return ret;
    }
};

我們優(yōu)化了兩點：

1.通過加虛擬節(jié)點可以解決第一次的代碼中只有一個元素和nums[0]就是最大值的情況

2.我們不用考慮n[i]大于0還是小于0，直接一股腦都做判斷找出最大值即可。

4.乘積為正數(shù)的最長子數(shù)組長度

力扣鏈接：力扣

給你一個整數(shù)數(shù)組?nums?，請你求出乘積為正數(shù)的最長子數(shù)組的長度。

一個數(shù)組的子數(shù)組是由原數(shù)組中零個或者更多個連續(xù)數(shù)字組成的數(shù)組。

請你返回乘積為正數(shù)的最長子數(shù)組長度。

?根據(jù)上一題的經(jīng)驗，要求正數(shù)我們一種狀態(tài)肯定是不可以的，要考慮負負得正的情況就必須有兩種狀態(tài)。

1.狀態(tài)表示

f[i]表示以i位置為結(jié)尾乘積為正數(shù)的最長子數(shù)組長度

g[i]表示以i位置為結(jié)尾乘積為負數(shù)的最長子數(shù)組長度

2.狀態(tài)轉(zhuǎn)移方程

我們可以將i位置分為3種狀態(tài)，等于0，大于0，小于0.要注意的是：不管是g表還是f表如果n[i]等于0那么長度一定為0，因為0（0乘任何數(shù)都為0）既不是正數(shù)也不是負數(shù).當n[i]大于0時，只需要找到i位置前面的乘積為正數(shù)的最長子數(shù)組然后加上本身長度1即可，即使f[i-1]=0，由于n[i]大于0自己本身也是1所以f[i] = f[i-1]+1.對于g[i]，如果n[i]大于0那么要找負數(shù)的最長長度的話前面必須是負數(shù)，所以g[i-1]+1，但是如果g[i-1]為0?的話，就說明i前面沒有乘積為負數(shù)的最長子數(shù)組，而又因為自己本身是大于0的，我們的g表要的負數(shù)，所以當g[i-1]等于0時，g[i]=0.

對于n[i]小于0的情況，那么找到i前面的乘積為負數(shù)的子數(shù)組然后相乘就變成了正數(shù)，所以f[i] = g[i-1]+1,但是g[i-1]有可能為0，一旦為0說明i前面沒有乘積為負數(shù)的子數(shù)組，又因為n[i]是小于0的，所以當g[i-1]等于0時，f[i]只能為0.g[i]中如果n[i]小于0，那么只要找到i前面的乘積為正數(shù)的子數(shù)組（負數(shù)乘正數(shù)還是負數(shù)）然后加上自身的長度，即使f[i-1]等于0，但是n[i]本身小于0長度為1，所以不用特殊判斷f[i-1]是否為0.

3.初始化

我們采用開虛擬節(jié)點的方式，第一個元素的時候需要dp[i-1]的值，從狀態(tài)轉(zhuǎn)移方程來看，為了不影響后續(xù)填表，將兩個虛擬位置初始化為0即可。

?4.填表

從左向右兩個表一起填

5.返回值

由于f表中存放的是多個子數(shù)組的結(jié)果，所以需要遍歷找到f表中最大值。

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
       int n = nums.size();
       vector<int> f(n+1,0),g(n+1,0);
       int ret = 0;
       for (int i = 1;i<=n;i++)
       {
           if (nums[i-1]>0)
           {
               f[i] = f[i-1]+1;
               g[i] = g[i-1]==0?0:g[i-1]+1;
           }
           else if(nums[i-1]<0)
           {
               f[i] = g[i-1]==0?0:g[i-1]+1;
               g[i] = f[i-1]+1;
           }
           ret = max(ret,f[i]);
       }
       return ret;
    }
};

5.等差數(shù)列劃分

力扣鏈接：力扣

如果一個數(shù)列?至少有三個元素?，并且任意兩個相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。

• 例如，[1,3,5,7,9]、[7,7,7,7]?和?[3,-1,-5,-9]?都是等差數(shù)列。

給你一個整數(shù)數(shù)組?nums?，返回數(shù)組?nums?中所有為等差數(shù)組的?子數(shù)組?個數(shù)。

子數(shù)組?是數(shù)組中的一個連續(xù)序列。

?這道題中題目給的有用信息有：必須是一個等差數(shù)組，每個等差數(shù)組至少3個元素。

1.狀態(tài)表示

根據(jù)經(jīng)驗我們以dp[i]表示以i位置為結(jié)尾的等差數(shù)組的子數(shù)組的個數(shù)。

2.狀態(tài)轉(zhuǎn)移方程

當以i位置為結(jié)尾時，要想是一個等差數(shù)列，滿足的條件必須是n[i]-n[i-1] = n[i-1]-n[i-2],只有滿足了這個條件，說明i位置元素可以和前面的等差數(shù)列匹配，這個時候dp[i] = dp[i-1] + 1.

如果不滿足剛剛等差數(shù)列的條件，那么以i位置為結(jié)尾是沒有等差數(shù)列的，所以dp[i] = 0

3.初始化

通過狀態(tài)轉(zhuǎn)移方程我們可以看到0,1這兩個位置會越界，所以我們直接初始化這兩個位置，由于等差數(shù)組必須有3個元素，剛開始的兩個元素無法組成等差數(shù)組，所以dp[0]和dp[1]都是0

4.填表

從左向右

5.返回值

我們題目要求的是返回所有等差數(shù)組的個數(shù)，而我們dp[i]計算的是i位置為結(jié)尾的等差數(shù)組的個數(shù)，所以我們應(yīng)該將dp表中每個位置的等差數(shù)組的個數(shù)相加最后返回。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,0);
        int sum = 0;
        for (int i = 2;i<n;i++)
        {
            if (nums[i]-nums[i-1]==nums[i-1]-nums[i-2])
            {
                dp[i] = dp[i-1]+1;
            }
            else 
            {
                dp[i] = 0;
            }
            sum+=dp[i];
        }
        return sum;
    }
};

注意：我們填dp表的時候一定是從第3個位置也就是下標為2的位置開始填，因為前兩個元素是無法構(gòu)成等差數(shù)組的。

6.最長湍流子數(shù)組

力扣鏈接：力扣

給定一個整數(shù)數(shù)組?arr?，返回?arr?的?最大湍流子數(shù)組的長度?。

如果比較符號在子數(shù)組中的每個相鄰元素對之間翻轉(zhuǎn)，則該子數(shù)組是?湍流子數(shù)組?。

更正式地來說，當?arr?的子數(shù)組?A[i], A[i+1], ..., A[j]?滿足僅滿足下列條件時，我們稱其為湍流子數(shù)組：

• 若?i <= k < j?：
  • 當?k?為奇數(shù)時，?A[k] > A[k+1]，且
  • 當?k?為偶數(shù)時，A[k] < A[k+1]；
• 或?若?i <= k < j?：
  • 當?k?為偶數(shù)時，A[k] > A[k+1]?，且
  • 當?k?為奇數(shù)時，?A[k] < A[k+1]。

?這道題我們不用看題目描述，因為說的有些繁瑣了，我們直接看測試用例，通過測試用例我們發(fā)現(xiàn)湍流子數(shù)組實際上就是下圖這樣的：

?上圖中曲線的上升或者下降其實就是兩個數(shù)的差是正還是負，只要滿足正負正負或者負正負正就是湍流子數(shù)組，并且通過題目描述我們得知，相等情況并不屬于湍流，但是一個元素的時候也屬于湍流。

1.狀態(tài)表示

如果以dp[i]表示以i位置為結(jié)尾的最長湍流子數(shù)組的話，我們發(fā)現(xiàn)運行后的測試用例的結(jié)果每次都會少，這是因為i位置的狀態(tài)其實是有兩種狀態(tài)的，如果是湍流子數(shù)組，那么i-1到i位置有可能是上升狀態(tài)，也有可能是下降狀態(tài)，所以我們有兩個狀態(tài)表示：

f[i]表示以i位置為結(jié)尾并且呈上升狀態(tài)的最長湍流子數(shù)組

g[i]表示以i位置為結(jié)尾并且呈下降狀態(tài)的最長湍流子數(shù)組

2.狀態(tài)轉(zhuǎn)移方程

既然i位置有兩種狀態(tài)，下面我們就分析一下：

當n[i]>n[i-1]，說明到i位置是上升狀態(tài)，這個時候要組成湍流子數(shù)組那么i-1前面就必須是下降狀態(tài)，所以f[i] = g[i-1]+1。當n[i]>n[i-1]時，我們的g[i]存放的結(jié)尾是下降狀態(tài)，這個時候條件不滿足，但是我們說過一個元素也算湍流子數(shù)組，并且一個元素的時候既可以代表上升也可以代表下降狀態(tài)，所以g[i] = 1.

當n[i]<n[i-1]，說明到i位置是下降狀態(tài)，這個時候要組成湍流子數(shù)組那么i-1前面就必須是上升狀態(tài)，所以g[i] = f[i-1]+1。當n[i]<n[i-1]時，我們的f[i]存放的結(jié)尾是上升狀態(tài)，這個時候條件不滿足，但是我們說過一個元素也算湍流子數(shù)組，并且一個元素的時候既可以代表上升也可以代表下降狀態(tài)，所以f[i] = 1.

3.初始化

由于一個元素也屬于湍流子數(shù)組，所以我們將兩個表都初始化為1，這樣遇到dp[i]為1的情況我們就不用考慮了。

4.填表

從左向右兩個表一起填

5.返回值

返回g表和f表中的最大值

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n,1),g(n,1);
        int ret = f[0];
        for (int i = 1;i<n;i++)
        {
            if (arr[i]>arr[i-1])
            {
                f[i] = g[i-1]+1;
            }
            else if(arr[i]<arr[i-1])
            {
                g[i] = f[i-1]+1;
            }
            ret = max(f[i],max(g[i],ret));
        }
        return ret;
    }
};

讓ret為f[0]的時候可以解決只有一個元素無法進入for循環(huán)的情況。

7.單詞拆分

力扣鏈接：力扣

給你一個字符串?s?和一個字符串列表?wordDict?作為字典。請你判斷是否可以利用字典中出現(xiàn)的單詞拼接出?s?。

注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復(fù)使用。

?這道題讓我們用字典中的字符拼接字符串，下面我們就分析一下：

1.狀態(tài)表示

我們就以經(jīng)常用的dp[i]來表示：

dp[i]表示從0~i這個區(qū)間的字符串能否被拼接

2.狀態(tài)轉(zhuǎn)移方程

我們要驗證以i為結(jié)尾的字符串是否可以被憑借，那么就需要找到以i為結(jié)尾的單詞的首部，比如說leetcode中以d為結(jié)尾的時候我們枚舉>=d的任何一個字符發(fā)現(xiàn)都沒有在字典中找到對應(yīng)的單詞，那么就說明dp[i]為false，那么什么情況下是找到的呢？當我們以t為結(jié)尾，在找以t為結(jié)尾的字符串時發(fā)現(xiàn)首部為L的字符到t是一個完成的字符串leet，這個時候還沒有結(jié)束，我們還需要判斷首部前面的單詞是否可以在字典中找到。

?如上圖，當以e結(jié)尾時，我們除了要判斷以e結(jié)尾的單詞是否能夠找到，同時還要判斷j前面的單詞是否可以找到，但是我們的狀態(tài)表示的是以某個位置為結(jié)尾的字符串能否被拼接，所以j前面的單詞的狀態(tài)就可以表示為dp[j-1](因為j是i結(jié)尾的首單詞，所以j前面的狀態(tài)是dp[j-1]

dp[i] =?如果dp[j-1]為真并且substr(j,i-j+1)這個單詞能被找到，那么dp[i] = true

3.初始化

這里我們用虛擬節(jié)點的方式，不用虛擬節(jié)點初始化會麻煩很多，這里已經(jīng)試過了。采用虛擬節(jié)點首先虛擬節(jié)點不能影響后續(xù)填表，所以dp[0] =?true,可以看我們的狀態(tài)轉(zhuǎn)移方程，如果第一個虛擬節(jié)點為false,那么即使dp[i]實際為true，但是由于dp[j-1]為false，導(dǎo)致無法正確判斷。

我們加了虛擬節(jié)點后，那么dp表就應(yīng)該從1位置（初始化了0位置）開始填，但是字符串中的第一個字符實際下標是0，所以為了和實際的字符串下標匹配，我們在字符串前面加個空格，這樣字符串的第一個字符的下標就是1了，與我們的dp表匹配。

4.填表

從左向右

5.返回值

題目要求整個字符串是否可以被拼接，所以我們應(yīng)該是以最后一個字符為結(jié)尾的結(jié)果，所以返回dp[n]（因為虛擬節(jié)點所以可以訪問n位置）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
         int n = s.size();
         vector<bool> dp(n+1,false);
         dp[0] = true;
         unordered_set<string> hash;
         for (auto& s:wordDict) hash.insert(s);
         s = ' '+s;
         for (int i = 1;i<=n;i++)
         {
             for (int j = 1;j<=i;j++)
             {
                 if (dp[j-1]&&hash.count(s.substr(j,i-j+1)))
                 {
                     dp[i] = true;
                 }
             }
         }
         return dp[n];
    }
};

可以看到我們?yōu)榱藘?yōu)化每次查找字符串是否在字典中的效率，我們將字典中的單詞直接映射到了哈希表中。

8.環(huán)繞字符串中唯一的子字符串

力扣鏈接：力扣

定義字符串?base?為一個?"abcdefghijklmnopqrstuvwxyz"?無限環(huán)繞的字符串，所以?base?看起來是這樣的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

給你一個字符串?s?，請你統(tǒng)計并返回?s?中有多少?不同非空子串?也在?base?中出現(xiàn)。

?通過測試用例我們可以發(fā)現(xiàn)，這道題讓我們求的實際上是連續(xù)的子字符串，比如實例3中，z,a,b三個單個的字符都可以在Base中找到，然后再看連續(xù)的子字符串，za是一個,ab是一個，zab也是一個，因為是環(huán)繞的z的后面就是a，所以zab也可以。

1.狀態(tài)表示

dp[i]表示以i字符為結(jié)尾的子字符串的個數(shù)

2.狀態(tài)轉(zhuǎn)移方程

我們發(fā)現(xiàn)i位置如果能和前面匹配那么就會多一種方法，那么匹配的條件是什么呢？實際上就是s[i-1]+1==s[i]或者s[i-1]=='z'&&s[i]=='a'的時候符合條件，這個時候dp[i] = dp[i-1]+1

3.初始化

首先能越界的只有dp[0]，并且s[0]一定可以在base中找到，所以dp[0] = 1

因為題目給的字符串一定是小寫字母組成，所以這一個字符一定屬于26個字母中的任意一個，所以我們將dp表全部初始化為1，如果不滿足轉(zhuǎn)移方程的條件那么默認的1剛好合適。

4.填表

從左向右依次填表

5.返回值

我們要求的是s中所有在base中出現(xiàn)的子字符串，而我們dp[i]只是某一個位置的結(jié)果，所以我們應(yīng)該加上dp表中所有的值才是正確答案。

當我們提交代碼后發(fā)現(xiàn)很多測試用例都跑不過，這個時候我們發(fā)現(xiàn)我們的dp表是有重復(fù)結(jié)果的，如下圖：

同樣以c字符為結(jié)尾，我們保存兩個結(jié)果，就比如下面這個例子更清晰：

?比如這個字符串的結(jié)果應(yīng)該是6，但是我們?nèi)考悠饋硎?，因為b自己本身多算了一次，所以我們需要對相同字符結(jié)尾的字符串去重，比如：ab和zab的結(jié)果我們只保留最大的那一個，因為最大的那個一定包含了之前的任何一個例子。我們?nèi)ブ氐乃枷胍埠芎唵?，開一個26大小的數(shù)組，每一個字符的結(jié)尾只會在數(shù)組中映射一遍，比如b?和?ab只能映射到hash[b-a]這個位置，而這個位置我們保存的是以b結(jié)尾的子字符串的最大值。

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        vector<int> dp(n,1);
        int sum = 0;
        for (int i = 1;i<n;i++)
        {
            if (s[i-1]+1==s[i] || s[i-1]=='z'&&s[i]=='a')
            {
                dp[i] = dp[i-1]+1;
            }
        }
        //去重dp表中相同的字符結(jié)尾的最小值，只保留最大值
        int hash[26] = {0};
        for (int i = 0;i<n;i++)
        {
            hash[s[i]-'a'] = max(hash[s[i]-'a'],dp[i]);
        }
        for (auto& e : hash) sum+=e;
        return sum;
    } 
};

?這道題最抽象的部分在于去重，如果有不理解的可以將圖畫出來。文章來源地址http://www.zghlxwxcb.cn/news/detail-557830.html

到了這里，關(guān)于60題學(xué)會動態(tài)規(guī)劃系列：動態(tài)規(guī)劃算法第五講的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！