国产1234久久久久,99热超大,97爱爱爱

作者：寒小陽時間：2013年9月。
出處：http://blog.csdn.net/han_xiaoyang/article/details/11596001。
聲明：版權(quán)所有，轉(zhuǎn)載請注明出處，謝謝。

0、前言

這一部分的內(nèi)容原本是打算在之后的字符串或者數(shù)組專題里面寫的，但看著目前火熱進行的各家互聯(lián)網(wǎng)公司筆試面試中，出現(xiàn)了其中的一兩個內(nèi)容，就隨即將這些經(jīng)典問題整理整理，單寫一篇發(fā)上來了。這里爭取覆蓋面廣一些，列舉了7個最經(jīng)典的問題，也會是之后大家筆試面試常見到的問題，而每個問題下都列舉了幾種思路，掌握這些經(jīng)典問題的解題思路和算法相信對同類型問題的解答都能有幫助。

這里總結(jié)的幾個問題分別是最大子序列和，最長遞增子序列，最長公共子串，最長公共子序列，字符串編輯距離，最長不重復(fù)子串，最長回文子串。其中前兩個問題是針對數(shù)組求解的，后五個問題是針對字符串求解的。多數(shù)問題都有動態(tài)規(guī)劃的解法（博主不堪地表示，自己動態(tài)規(guī)劃也較弱，只能想到一些基本的思路），這些解法需要細細琢磨，可發(fā)散式地使用在很多其他的題目上。

一、最大子序列和

這里把最大子序列和放在第一個位置，它并不是字符串相關(guān)的問題，事實上它的目的是要找出由數(shù)組成的一維數(shù)組中和最大的連續(xù)子序列。比如[0，-2，3，5，-1，2]應(yīng)返回9，[-9，-2，-3，-5，-3]應(yīng)返回-2。

1、動態(tài)規(guī)劃法
你也許從這兩個例子中已經(jīng)可以看出，使用動態(tài)規(guī)劃的方法很容易完成這個任務(wù)， $\color{red}{只要前i項的和還沒有小于0那么子序列就一直向后擴展，否則丟棄之前的子序列開始新的子序列}$ ， $\color{red}{同時我們要記下各個子序列的和，最后找到和最大的子序列。}$ 但是你可能需要謹慎一些，在整個數(shù)組都為負的情況下，所以初始的和最大值賦值不當?shù)脑捒赡軙鰡栴}。

根據(jù)以上的思路我們可以有以下的代碼：

/**********************************************************************
動態(tài)規(guī)劃求最大子序列和
**********************************************************************/
int Maxsum(int * arr, int size)
{
    int maxSum = -INF; //很重要，初始值賦值為負無窮大
    int sum = 0;
    for(int i = 0; i < size; ++i)
{
//小于0則舍棄
        if(sum < 0)
        {
            sum = arr[i];
        }else
        {
            sum += arr[i];
        }
//比現(xiàn)有最大值大，則替換
        if(sum > maxSum)
        {
            maxSum = sum;
        }
    }
    return maxSum;
}


/*************************************************************************
如果想獲得最大子序列和的初始和結(jié)束位置怎么辦呢？我們知道，每當當前子數(shù)組和的小于0時，
便是新一輪子數(shù)組的開始，每當更新最大和時，便對應(yīng)可能的結(jié)束下標，這個時候，
只要順便用本輪的起始和結(jié)束位置更新始末位置就可以，程序結(jié)束，最大子數(shù)組和以及其始末位置便一起被記錄下來了
*****************************************************************************/
void Maxsum_location(int * arr, int size, int & start, int & end)
{
    int maxSum = -INF;
    int sum = 0;
    int curstart = start = 0;  /* curstart記錄每次當前起始位置 */
    for(int i = 0; i < size; ++i)
    {
        if(sum < 0)
        {
            sum = arr[i];
            curstart = i;     /* 記錄當前的起始位置 */
        }else
        {
            sum += arr[i];
        }
        if(sum > maxSum)
        {
            maxSum = sum;
            start = curstart; /* 記錄并更新最大子數(shù)組起始位置 */
            end = i;
        }
    }
}

2、分治法
其實數(shù)組的問題，最好留點心， $\color{red}{有一大部分題目是可以用分治的辦法完成的}$ ，比如說這道題里面：最大子序列和可能出現(xiàn)在三個地方，1）整個出現(xiàn)在輸入數(shù)據(jù)的左半部分，2）整個出現(xiàn)在輸入數(shù)據(jù)的右半部分，3）或者跨越輸入數(shù)據(jù)的中部從而占據(jù)左右兩個半部分?？梢杂幸韵麓a：

/**************************************************************
分治法求解最大子序列和
***************************************************************/
int MaxSumRec( const vector<int> & a, int left, int right )
{
    if( left == right )  // Base case
        if( a[ left ] > 0 )
            return a[ left ];
        else
            return 0;
    int center = ( left + right ) / 2;
    int maxLeftSum  = maxSumRec( a, left, center );
    int maxRightSum = maxSumRec( a, center + 1, right );
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for( int i = center; i >= left; i-- )
    {
        leftBorderSum += a[ i ];
        if( leftBorderSum > maxLeftBorderSum )
            maxLeftBorderSum = leftBorderSum;
    }
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for( int j = center + 1; j <= right; j++ )
    {
        rightBorderSum += a[ j ];
        if( rightBorderSum > maxRightBorderSum )
            maxRightBorderSum = rightBorderSum;
    }
    return max3( maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum );
}

二、最長遞增子序列

和上一問題一樣，這是數(shù)組序列中的問題，比如arr={1,5,8,2,3,4}的最長遞增子序列是1,2,3,4

1、動態(tài)規(guī)劃法
結(jié)合上一題的思路，在數(shù)組的這類問題里面使用動態(tài)規(guī)劃還是很常見的，從后向前分析，很容易想到， $\color{red}{第i個元素之前的最長遞增子序列的長度要么是1（比如說遞減的數(shù)列），要么就是第i-1個元素之前的最長遞增子序列加1}$ ，我們可以得到以下關(guān)系：

$\color{red}{LIS[i] = max\{1,LIS[k]+1\}}$ ，其中，對于任意的 $\color{red}{k<=i-1，arr[i] > arr[k]}$ ，這樣arr[i]才能在arr[k]的基礎(chǔ)上構(gòu)成一個新的遞增子序列。這種方法代碼如下：

#include <iostream>
using namespace std;
 
//動態(tài)規(guī)劃法求最長遞增子序列 LIS
 
int dp[101]; /* 設(shè)數(shù)組長度不超過100，dp[i]記錄到[0,i]數(shù)組的LIS */
int lis;    /* LIS 長度 */
 
int LIS(int * arr, int size)
{
    for(int i = 0; i < size; ++i)
    {
        dp[i] = 1;
        for(int j = 0; j < i; ++j)
        {
            if(arr[i] > arr[j] && dp[i] < dp[j] + 1)
            {
                dp[i] = dp[j] + 1;
                if(dp[i] > lis)
                {
                    lis = dp[i];
                }
            }
        }
    }
    return lis;
}
 
/* 輸出LIS */
void outputLIS(int * arr, int index)
{
    bool isLIS = 0;
    if(index < 0 || lis == 0)
    {
        return;
    }
    if(dp[index] == lis)
    {
        --lis;
        isLIS = 1;
    }
 
    outputLIS(arr,--index);
 
    if(isLIS)
    {
        printf("%d ",arr[index+1]);
    }
}
 
void main()
{
    int arr[] = {1,-1,2,-3,4,-5,6,-7};
 
    /* 輸出LIS長度； sizeof 計算數(shù)組長度 */
    printf("%d\n",LIS(arr,sizeof(arr)/sizeof(int)));
 
    /* 輸出LIS */
    outputLIS(arr,sizeof(arr)/sizeof(int) - 1);
    printf("\n");
}

2、數(shù)組排序后，與原數(shù)組求最長公共子序列
這個方法還是非常巧妙的，因為 $\color{red}{LIS是單調(diào)遞增的性質(zhì)，所以任意一個LIS一定跟排序后的序列有最長公共子序列，并且就是LIS本身}$ 。不過這里還沒有提到最長公共子序列，可以先移步下一節(jié)，看完后再回來看這個方法的代碼，代碼如下：

#include <iostream>
using namespace std;
 
/* 最長遞增子序列 LIS
 * 設(shè)數(shù)組長度不超過 100
 * quicksort + LCS
*/
 
void swap(int * arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
 
void qsort(int * arr, int left, int right)
{
    if(left >= right)    return ;
    int index = left;
    for(int i = left+1; i <= right; ++i)
    {
        if(arr[i] < arr[left])
        {
            swap(arr,++index,i);
        }
    }
    swap(arr,index,left);
    qsort(arr,left,index-1);
    qsort(arr,index+1,right);
}
 
int dp[101][101];
 
int LCS(int * arr, int * arrcopy, int len)
{
    for(int i = 1; i <= len; ++i)
    {
        for(int j = 1; j <= len; ++j)
        {
            if(arr[i-1] == arrcopy[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }else if(dp[i-1][j] > dp[i][j-1])
            {
                dp[i][j] = dp[i-1][j];
            }else
            {
                dp[i][j] = dp[i][j-1];
            }
        }
    }
    return dp[len][len];
}
 
void main()
{
    int arr[] = {1,-1,2,-3,4,-5,6,-7};
    int arrcopy [sizeof(arr)/sizeof(int)];
 
    memcpy(arrcopy,arr,sizeof(arr));
    qsort(arrcopy,0,sizeof(arr)/sizeof(int)-1);
 
    /* 計算LCS，即LIS長度 */
    int len = sizeof(arr)/sizeof(int);
    printf("%d\n",LCS(arr,arrcopy,len));
}

3、動態(tài)規(guī)劃和二分查找結(jié)合
我們期望在前i個元素中的所有長度為len的遞增子序列中找到這樣一個序列，它的最大元素比arr[i+1]小，而且長度要盡量的長，如此， $\color{red}{我們只需記錄len長度的遞增子序列中最大元素的最小值就能使得將來的遞增子序列盡量地長。}$

在這里我們維護一個數(shù)組MaxV[i]，記錄長度為i的遞增子序列中最大元素的最小值，并對于數(shù)組中的每個元素考察其是哪個子序列的最大元素，二分更新MaxV數(shù)組，最終i的值便是最長遞增子序列的長度。這個方法真是太巧妙了，妙不可言。

具體代碼如下：

#include <iostream>
using namespace std;
 
/* 最長遞增子序列 LIS
 * 設(shè)數(shù)組長度不超過 30
 * DP + BinarySearch
*/
 
int MaxV[30]; /* 存儲長度i+1（len）的子序列最大元素的最小值 */
int len;      /* 存儲子序列的最大長度 即MaxV當前的下標*/
 
/* 返回MaxV[i]中剛剛大于x的那個元素的下標 */
int BinSearch(int * MaxV, int size, int x)
{
    int left = 0, right = size-1;
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if(MaxV[mid] <= x)
        {
            left = mid + 1;
        }else
        {
            right = mid - 1;
        }
    }
    return left;
}
 
int LIS(int * arr, int size)
{
    MaxV[0] = arr[0]; /* 初始化 */
    len = 1;
    for(int i = 1; i < size; ++i) /* 尋找arr[i]屬于哪個長度LIS的最大元素 */
    {
        if(arr[i] > MaxV[len-1]) /* 大于最大的自然無需查找，否則二分查其位置 */
        {
            MaxV[len++] = arr[i];
        }else
        {
            int pos = BinSearch(MaxV,len,arr[i]);
            MaxV[pos] = arr[i];
        }
    }
    return len;
}
 
void main()
{
    int arr[] = {1,-1,2,-3,4,-5,6,-7};
 
    /* 計算LIS長度 */
    printf("%d\n",LIS(arr,sizeof(arr)/sizeof(int)));
}

三、最長公共子串（LCS）

回到最常見的字符串問題了，這里的找兩個字符串的最長公共子串，要求在原字符串中是連續(xù)的。其實和上面兩個問題一樣，這里依舊可以用動態(tài)規(guī)劃來求解，其實博主自己也不大擅長動態(tài)規(guī)劃，但是可以仿照上面的思路來操作。 $\color{red}{我們采用一個二維矩陣來記錄中間的結(jié)果}$ 。這個二維矩陣怎么構(gòu)造呢？直接舉個例子吧："bab"和"caba"，則數(shù)組如下：


	b	a	b
c	0	0	0
a	0	$\color{red}{1}$	0
b	$\color{red}{1}$	0	$\color{red}{1}$
a	0	$\color{red}{1}$	0

我們看 $\color{red}{矩陣的斜對角線最長的那個就是我們找的最長公共子串}$ 。

那怎么求最長的由1組成的斜對角線呢？可以做這樣的操作：當要在 $\color{red}{矩陣是填1時讓它等于其左上角元素加1}$ 。


	b	a	b
c	0	0	0
a	0	$\color{red}{1}$	0
b	$\color{red}{1}$	0	$\color{red}{2}$
a	0	$\color{red}{2}$	0

這樣矩陣中的最大元素就是最長公共子串的長度。

在構(gòu)造這個二維矩陣的過程中由于得出矩陣的某一行后其上一行就沒用了，所以 $\color{red}{實際上在程序中可以用一維數(shù)組來代替這個矩陣}$ (這樣空間復(fù)雜度就降低了哈)。

代碼如下：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
//str1為橫向，str2這縱向
const string LCS(const string& str1,const string& str2){
    int xlen=str1.size();       //橫向長度
    vector<int> tmp(xlen);        //保存矩陣的上一行
    vector<int> arr(tmp);     //當前行
    int ylen=str2.size();       //縱向長度
    int maxele=0;               //矩陣元素中的最大值
    int pos=0;                  //矩陣元素最大值出現(xiàn)在第幾列
    for(int i=0;i<ylen;i++){
        string s=str2.substr(i,1);
        arr.assign(xlen,0);     //數(shù)組清0
        for(int j=0;j<xlen;j++){
            if(str1.compare(j,1,s)==0){
                if(j==0)
                    arr[j]=1;
                else
                    arr[j]=tmp[j-1]+1;
                if(arr[j]>maxele){
                    maxele=arr[j];
                    pos=j;
                }
            }       
        }
        tmp.assign(arr.begin(),arr.end());
    }
    string res=str1.substr(pos-maxele+1,maxele);
    return res;
}
int main(){
    string str1("21232523311324");
    string str2("312123223445");
    string lcs=LCS(str1,str2);
    cout<<lcs<<endl;
    return 0;
}

四、最長公共子序列

這才是筆試面試中出現(xiàn)頻度最高的問題，前面提到了一個最長公共子串，這里的 $\color{red}{最長公共子序列與它的區(qū)別在于最長公共子序列不要求在原字符串中是連續(xù)的}$ ，比如ADEFG和ABCDEG的最長公共子序列是ADEG。

1）遞歸方法求解
這個地方可能最容易想到的方法就是遞歸處理了，設(shè)有字符串a(chǎn)[0...n]，b[0...m]， $\color{red}{則易知當數(shù)組a的i位置上和b的j位置上對應(yīng)位相同時}$ ， $\color{red}{則直接求解兩個串從下一個位置開始的剩下部分的最長公共子序列即可}$ ； $\color{red}{當不同時，則求a[i+1...n]、b[j...m]和a[i...n]、b[j+1...m]兩種情況中的較大數(shù)值即可}$ ，用公式表示如下：

代碼如下：

#include<stdio.h>
#include<string.h>
char a[100],b[100];
int lena,lenb;
int LCS(int,int);///兩個參數(shù)分別表示數(shù)組a的下標和數(shù)組b的下標
int main()
{
    strcpy(a,"ABCBDAB");
    strcpy(b,"BDCABA");
    lena=strlen(a);
    lenb=strlen(b);
    printf("%d\n",LCS(0,0));
    return 0;
}
int LCS(int i,int j)
{
    if(i>=lena || j>=lenb)
        return 0;
    if(a[i]==b[j])
        return 1+LCS(i+1,j+1);
    else
        return LCS(i+1,j)>LCS(i,j+1)? LCS(i+1,j):LCS(i,j+1);
}

這種處理方法優(yōu)點是 $\color{red}{編程簡單}$ ， $\color{red}{非常容易理解}$ 。缺點是效率太低了，有 $\color{red}{大量的重復(fù)執(zhí)行遞歸調(diào)用}$ ，一般情況下面試官是不會滿意的。另一個致命的缺點是只能求出最大公共子序列的長度，求不出具體的最大公共子序列，而在大部分筆試或者面試時會要求我們求出具體的最大公共子序列。

2）動態(tài)規(guī)劃
這里依舊可以采用動態(tài)規(guī)劃的方法來解決這個問題，可以 $\color{red}{借助一個二維數(shù)組來標識中間計算結(jié)果，避免重復(fù)的計算來提高效率}$ ，可能需要消耗一部分空間，但是時間復(fù)雜度大大降低。

如下圖所示的兩個串，求解最長公共子序列的過程很明了：

設(shè)有字符串a(chǎn)[0...n]，b[0...m]，字符串a(chǎn)對應(yīng)的是二維數(shù)組num的行，字符串b對應(yīng)的是二維數(shù)組num的列。我們有以下的遞推公式：

我們在程序中，

\color{red}{可以使用二維數(shù)組flag來記錄下標i和j的走向。數(shù)字"1"表示，斜向下；}

\color{red}{數(shù)字"2"表示，水平向右；數(shù)字"3"表示，豎直向下。這樣我們可以求解出行進的路徑}

，從而得到最長公共子序列。代碼如下：

#include<stdio.h>
#include<string.h>
char a[500],b[500];
char num[501][501]; ///記錄中間結(jié)果的數(shù)組
char flag[501][501];    ///標記數(shù)組，用于標識下標的走向，構(gòu)造出公共子序列
void LCS(); ///動態(tài)規(guī)劃求解
void getLCS();    ///采用倒推方式求最長公共子序列
int main()
{
    int i;
    strcpy(a,"ABCBDAB");
    strcpy(b,"BDCABA");
    memset(num,0,sizeof(num));
    memset(flag,0,sizeof(flag));
    LCS();
    printf("%d\n",num[strlen(a)][strlen(b)]);
    getLCS();
    return 0;
}
void LCS()
{
    int i,j;
    for(i=1;i<=strlen(a);i++)
    {
        for(j=1;j<=strlen(b);j++)
        {
            if(a[i-1]==b[j-1])   ///注意這里的下標是i-1與j-1
            {
                num[i][j]=num[i-1][j-1]+1;
                flag[i][j]=1;  ///斜向下標記
            }
            else if(num[i][j-1]>num[i-1][j])
            {
                num[i][j]=num[i][j-1];
                flag[i][j]=2;  ///向右標記
            }
            else
            {
                num[i][j]=num[i-1][j];
                flag[i][j]=3;  ///向下標記
            }
        }
    }
}
void getLCS()
{
    char res[500];
    int i=strlen(a);
    int j=strlen(b);
    int k=0;    ///用于保存結(jié)果的數(shù)組標志位
    while(i>0 && j>0)
    {
        if(flag[i][j]==1)   ///如果是斜向下標記
        {
            res[k]=a[i-1];
            k++;
            i--;
            j--;
        }
        else if(flag[i][j]==2)  ///如果是斜向右標記
            j--;
        else if(flag[i][j]==3)  ///如果是斜向下標記
            i--;
    }
    for(i=k-1;i>=0;i--)
        printf("%c",res[i]);
}

五、字符串編輯距離

給定一個源字符串和目標字符串，能夠?qū)υ创M行如下操作：

   1.在給定位置上插入一個字符

   2.替換任意字符

   3.刪除任意字符

求通過以上操作使得源字符串和目標字符串一致的最小操作步數(shù)。

簡單描述一下解該題的思想，源字符串和目標字符串分別為str_a、str_b，二者的長度分別為la、lb，定義f[i,j]為子串str_a[0...i]和str_b[0...j]的最小編輯距離，簡單分析可知求得的str_a[0...i]和str_b[0...j]的最小編輯距離有一下三種可能：

$\color{red}{（1）去掉str_a[0...i]的最后一個字符跟str_b[0...j]匹配，則f[i, j]的值等于f[i-1, j]+1；}$

$\color{red}{（2）去掉str_b[0...j]的最后一個字符跟str_a[0...i]匹配，則f[i, j]的值等于f[i, j-1]+1；}$

$\color{red}{（3）去掉str_a[0...i]和str_b[0...j]的最后一個字符，讓二者匹配求得f[i-1, j-1]，}$ $\color{red}{計算f[i, j]時要考慮當前字符是否相等，如果str_a[i]==str_b[j]說明該字符不用編輯，}$ $\color{red}{所以f[i, j]的值等于f[i-1, j-1]，如果str_a[i]!=str_b[j]說明該字符需要編輯一次}$ $\color{red}{（任意修改str_a[i]或者str_b[j]即可），所以f[i, j]的值等于f[i-1, j-1]+1。}$

因為題目要求的是最小的編輯距離，所以去上面上中情況中的最小值即可，因此可以得到遞推公式：

$\color{red}{f[i, j] = Min ( f[i-1, j]+1, f[i, j-1]+1, f[i-1, j-1]+(str_a[i]==str_b[j] ? 0 : 1) )}$

維基百科中的描述如下：

1）遞歸方法(用到動態(tài)規(guī)劃)
由上述的遞歸公式可以有以下代碼：

//求兩個字符串的編輯距離問題
//遞歸版本，備忘錄C[i,j]表示strA[i]...strA[size_A-1]與strB[j]...strB[size_B-1]的編輯距離
int editDistance_mem(char *strA,int size_A,char *strB,int size_B){
 int **C=new int*[size_A+1];
 for(int i=0;i<=size_A;i++){
  C[i]=new int[size_B+1]();
 }
 //初始化
 for(int i=0;i<=size_A;i++){
  for(int j=0;j<=size_B;j++)
   C[i][j]=INT_MAX;
 }
 int res=EDM(C,strA,0,size_A-1,strB,0,size_B-1);
 //free mem
 for(int i=0;i<=size_A;i++){
  delete [] C[i];
 }
 delete [] C;
 return res;
}
int EDM(int **C,char *strA,int i,int A_end,char *strB,int j,int B_end){
 if(C[i][j]<INT_MAX)//做備忘
  return C[i][j];
 if(i>A_end){
  if(j>B_end)
   C[i][j]=0;
  else
   C[i][j]=B_end-j+1;
 }else if(j>B_end){
  if(i>A_end)
   C[i][j]=0;
  else
   C[i][j]=A_end-i+1;
 }
 else if(strA[i]==strB[j])
  C[i][j]=EDM(C,strA,i+1,A_end,strB,j+1,B_end);
 else{
  int a=EDM(C,strA,i+1,A_end,strB,j+1,B_end);
  int b=EDM(C,strA,i,A_end,strB,j+1,B_end);
  int c=EDM(C,strA,i+1,A_end,strB,j,B_end);
  C[i][j]=min(a,b,c)+1;
 }
 return C[i][j];
}

2）矩陣標記法
遞推方法（也可稱為矩陣標記法），通過分析可知 $\color{red}{可以將f[i, j]的計算在一個二維矩陣中進行}$ ，上面的遞推式實際上可以看做是矩陣單元的計算遞推式，只要把矩陣填滿了，f[la-1, lb-1]的值就是要求得最小編輯距離。代碼如下：

//求兩個字符串的編輯距離問題
//遞推版本 C[i,j]表示strA[i]...strA[size_A-1]與strB[j]...strB[size_B-1]的編輯距離
int editDistance_iter(char *strA,int size_A,char *strB,int size_B){
 int **C=new int*[size_A+1];
 for(int i=0;i<=size_A;i++){
  C[i]=new int[size_B+1]();
 }
 for(int i=size_A;i>=0;i--){
  for(int j=size_B;j>=0;j--){
   if(i>size_A-1){
    if(j>size_B-1)
     C[i][j]=0;
    else
     C[i][j]=size_B-j;
   }else if(j>size_B-1){
    if(i>size_A-1)
     C[i][j]=0;
    else
     C[i][j]=size_A-i;
   }else if(strA[i]==strB[j])
    C[i][j]=C[i+1][j+1];
   else
    C[i][j]=min(C[i+1][j+1],C[i+1][j],C[i][j+1])+1;
  }
 }
 int res=C[0][0];
 //free mem
 for(int i=0;i<=size_A;i++){
  delete [] C[i];
 }
 delete [] C;
 return res;
}

六、最長不重復(fù)子串

很好理解，即求一個串內(nèi)最長的不重復(fù)子串。

1）使用Hash
要求子串中的字符不能重復(fù)，判重問題首先想到的就是hash，尋找滿足要求的子串，最直接的方法就是遍歷每個字符起始的子串，輔助hash，尋求最長的不重復(fù)子串，由于要遍歷每個子串故復(fù)雜度為O(n^2)，n為字符串的長度，輔助的空間為常數(shù)hash[256]。代碼如下：

/* 最長不重復(fù)子串 我們記為 LNRS */
int maxlen;
int maxindex;
void output(char * arr);
/* LNRS 基本算法 hash */
char visit[256];
void LNRS_hash(char * arr, int size)
{
    for(int i = 0; i < size; ++i)
    {
        memset(visit,0,sizeof(visit));
        visit[arr[i]] = 1;
        for(int j = i+1; j < size; ++j)
        {
            if(visit[arr[j]] == 0)
            {
                visit[arr[j]] = 1;
            }
else
            {
                if(j-i > maxlen)
                {
                    maxlen = j - i;
                    maxindex = i;
                }
                break;
            }
        }
    }
    output(arr);
}

2）動態(tài)規(guī)劃法
字符串的問題，很多都可以用動態(tài)規(guī)劃處理，比如這里求解最長不重復(fù)子串，和前面討論過的最長遞增子序列問題就有些類似，在LIS(最長遞增子序列)問題中，對于當前的元素，要么是與前面的LIS構(gòu)成新的最長遞增子序列，要么就是與前面稍短的子序列構(gòu)成新的子序列或單獨構(gòu)成新子序列。

這里我們采用類似的思路：某個當前的字符， $\color{red}{如果它與前面的最長不重復(fù)子串中的字符沒有重復(fù)，那么就可以以它為結(jié)尾構(gòu)成新的最長子串}$ ； $\color{red}{如果有重復(fù)，那么就與某個稍短的子串構(gòu)成新的子串或者單獨成一個新子串}$ 。

我們來看看下面兩個例子：

1）字符串“abcdeab”，第二個a之前的最長不重復(fù)子串是“abcde”，a與最長子串中的字符有重復(fù)，
但是它與稍短的“bcde”串沒有重復(fù)，于是它可以與其構(gòu)成一個新的子串，之前的最長不重復(fù)子串“abcde”結(jié)束；

2）字符串“abcb”，跟前面類似，最長串“abc”結(jié)束，第二個字符b與稍短的串“c”構(gòu)成新的串；

我們貌似可以總結(jié)出一些東西： $\color{red}{當一個最長子串結(jié)束時（即遇到重復(fù)的字符），新的子串的長度是與（第一個重復(fù)的字符）的下標有關(guān)的}$ 。

于是類似LIS， $\color{red}{對于每個當前的元素，我們“回頭”去查詢是否有與之重復(fù)的，}$ $\color{red}{如沒有，則最長不重復(fù)子串長度+1，如有，}$ $\color{red}{則是與第一個重復(fù)的字符之后的串構(gòu)成新的最長不重復(fù)子串，新串的長度便是當前元素下標與重復(fù)元素下標之差。}$

可以看出這里的動態(tài)規(guī)劃方法時間復(fù)雜度為O(N^2)，我們可以與最長遞增子序列的動態(tài)規(guī)劃方案進行對比，是一個道理的。代碼如下：

/* LNRS 動態(tài)規(guī)劃求解 */
int dp[100];
void LNRS_dp(char * arr, int size)
{
    int i, j;
    maxlen = maxindex = 0;
    dp[0] = 1;
    for(i = 1; i < size; ++i)
    {
        for(j = i-1; j >= 0; --j)
        {
            if(arr[j] == arr[i])
            {
                dp[i] = i - j;
                break;
            }
        }
        if(j == -1)
        {
            dp[i] = dp[i-1] + 1;
        }
        if(dp[i] > maxlen)
        {
            maxlen = dp[i];
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}

3）動態(tài)規(guī)劃和hash結(jié)合
我們發(fā)現(xiàn)在動態(tài)規(guī)劃方法中，每次都要“回頭”去尋找重復(fù)元素的位置，所以時間復(fù)雜度徒增到O(n^2)，結(jié)合方法1）中的Hash思路，我們可以用hash記錄元素是否出現(xiàn)過，我們當然 $\color{red}{也可以用hash記錄元素出現(xiàn)過的下標，，這樣就不必“回頭”了}$ ，而時間復(fù)雜度必然降為O(N)，只不過需要一個輔助的常數(shù)空間visit[256]，這也是之前我另外一篇文章找工作筆試面試那些事兒(15)---互聯(lián)網(wǎng)公司面試的零零種種和多家經(jīng)驗提到的的空間換時間思路，不過一般我們的面試里面優(yōu)先考慮時間復(fù)雜度，所以這是可取的方法。

/* LNRS 動態(tài)規(guī)劃 + hash 記錄下標 */
void LNRS_dp_hash(char * arr, int size)
{
    memset(visit, -1, sizeof visit); //visit數(shù)組是-1的時候代表這個字符沒有在集合中
    memset(dp, 0, sizeof dp);
    maxlen = maxindex = 0;
    dp[0] = 1;
    visit[arr[0]] = 0;
    for(int i = 1; i < size; ++i)
    {
        if(visit[arr[i]] == -1) //表示arr[i]這個字符以前不存在
        {
            dp[i] = dp[i-1] + 1;
            visit[arr[i]] = i; /* 記錄字符下標 */
        }else
        {
            dp[i] = i - visit[arr[i]];
            visit[arr[i]] = i; /* 更新字符下標 */
        }
        if(dp[i] > maxlen)
        {
            maxlen = dp[i];
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}

4）空間再優(yōu)化
上面的方法3）已經(jīng)將時間復(fù)雜度降到了O(n)，可是這時面試官又發(fā)言了，說你用的輔助空間多了，還有優(yōu)化方法嗎，我們仔細觀察動態(tài)規(guī)劃最優(yōu)子問題解的更新方程：

dp[i] = dp[i-1] + 1;

dp[i-1]不就是更新dp[i]當前的最優(yōu)解么？這又與之前提到的最大子數(shù)組和問題的優(yōu)化幾乎同出一轍，我們不需要O(n)的輔助空間去存儲子問題的最優(yōu)解，而只需O(1)的空間就可以了，至此，我們找到了時間復(fù)雜度O(N)，輔助空間為O(1)（一個額外變量與256大小的散列表）的算法，代碼如下：

/* LNRS 動態(tài)規(guī)劃+hash，時間復(fù)雜度O(n) 空間復(fù)雜度O(1)算法*/
void LNRS_dp_hash_ultimate(char * arr, int size)
{
    memset(visit, -1, sizeof visit);
    maxlen = maxindex = 0;
    visit[arr[0]] = 0;
int curlen = 1;
    for(int i = 1; i < size; ++i)
    {
        if(visit[arr[i]] == -1)
        {
            ++curlen;
            visit[arr[i]] = i; /* 記錄字符下標 */
        }
else
        {
            curlen = i - visit[arr[i]];
            visit[arr[i]] = i; /* 更新字符下標 */
        }
        if(curlen > maxlen)
        {
            maxlen = curlen;
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}

七、最長回文子串

給出一個字符串S，找到一個最長的連續(xù)回文串。例如串 babcbabcbaccba 最長回文是:abcbabcba

1）自中心向兩端尋找
回文是一種特殊的字符串， $\color{red}{我們可以以源字符串的每個字符為中心，依次尋找出最長回文子串P0, P1,...,Pn。}$ $\color{red}{這些最長回文子串中的最長串Pi = max(P1, P2,...,Pn)即為所求}$ 。
核心代碼如下：

string find_lps_method1(const string &str)
{
    int center = 0, max_len = 0;
    for(int i = 1; i < str.length()-1; ++i)
    {
        int j = 1;
        //以str[i]為中心，依次向兩邊擴展，尋找最長回文Pi
        while(i+j < str.length() && i-j >= 0 && str[i+j] == str[i-j])
            ++j;
        --j;
        if(j > 1 && j > max_len)
        {
            center = i;
            max_len = j;
        }
    }
    return str.substr(center-max_len, (max_len << 1) + 1);
}

2）利用最長公共字串的方法
這里用到了一個我們觀察出來的結(jié)論： $\color{red}{對于串S, 假設(shè)它反轉(zhuǎn)后得到的串是S'}$ , 那么 $\color{red}{S的最長回文串是S和S'的最長公共字串}$ 。

例如 S = babcbabcbaccba, S' = abccabcbabcbab，S和S'的最長公共字串是 abcbabcba也是S的最長回文字串。

代碼這個地方就不寫了，用首指針++，尾指針--很容易實現(xiàn)串的翻轉(zhuǎn)，再結(jié)合前面寫過的最長公共子串代碼可得到最后結(jié)果。

3）利用棧的性質(zhì)
這是一個不成熟的想法，博主只是覺得比較好的想法需要拿出來分享一下，對于長度為偶數(shù)的最長回文，可以采用這樣一種思路求得：

將字符串中的字符從左至右逐個入棧，
出現(xiàn)情況：
$\color{red}{1）若棧頂字符和要入棧的字符相同，則該字符不入棧且棧pop出棧頂字符，回文長度加一。}$
$\color{red}{2）若棧頂字符與要入棧的字符不相同，直接入棧。則依次入棧出棧，求最長連續(xù)出棧序列即可。}$

因為對于奇數(shù)長度的字符串，博主沒有想到時間復(fù)雜度低的類似處理方法，所以這里就不寫代碼了，大家有好的解法或者思路歡迎留言。

4）著名的Manacher’s Algorithm算法
算法首先將輸入字符串S，轉(zhuǎn)換成一個特殊字符串T，轉(zhuǎn)換的原則就是將S的開頭結(jié)尾以及每兩個相鄰的字符之間加入一個特殊的字符，例如#

例如: S = “abaaba”, T = “#a#b#a#a#b#a#”.

為了找到最長的回文字串，例如我們當前考慮以Ti為回文串中間的元素，如果要找到最長回文字串，我們要從當前的Ti擴展使得 Ti-d … Ti+d 組成最長回文字串. 這里d其實和以Ti為中心的回文串長度是一樣的. 進一步解釋就是說， $\color{red}{因為我們這里插入了 \# 符號，對于一個長度為偶數(shù)的回文串，他應(yīng)該是以\#做為中心的，}$ $\color{red}{然后向兩邊擴，對于長度是奇數(shù)的回文串，它應(yīng)該是以一個普通字符作為中心的。}$ $\color{red}{通過使用\#，我們將無論是奇數(shù)還是偶數(shù)的回文串，都變成了一個以Ti為中心，}$ $\color{red}{d為半徑兩個方向擴展的問題。并且d就是回文串的長度。}$

例如 #a#b#a#, P = 0103010, 對于b而言P的值是3，是最左邊的#，也是延伸的最左邊。這個值和當前的回文串是一致的。

如果我們求出所有的P值，那么顯然我們要的回文串，就是以最大P值為中心的回文串。

T = # a # b # a # a # b # a #

P = 0 1 0 3 0 1 6 1 0 3 0 1 0

例如上面的例子，最長回文是 “abaaba”, P6 = 6.

根據(jù)觀察發(fā)現(xiàn)，如果我們在一個位置例如 abaaba的中間位置，用一個豎線分開，兩側(cè)的P值是對稱的。當然這個性質(zhì)不是在任何時候都會成立，接下來就是分析如何利用這個性質(zhì)，使得我們可以少算很多P的值。

下面的例子 S = “babcbabcbaccba” 存在更多的折疊回文字串。

C表示當前的回文中心，L和R處的線表示以C為中心可以到達的最左和最右位置，如果知道這些，我們?nèi)绾慰梢愿玫挠嬎鉉后面的P[i].

假設(shè)我們當前計算的是 i = 13, 根據(jù)對稱性，我們知道對稱的那個下標 i' = 9.

根據(jù)C對稱的原則，我們很容易得到如下數(shù)據(jù) P[ 12 ] = P[ 10 ] = 0, P[ 13 ] = P[ 9 ] = 1, P[ 14 ] = P[ 8 ] = 0).

當時當i = 15的時候，卻只能得到回文 “a#b#c#b#a”, 長度是5，而對稱 i ' = 7 的長度是7.

上圖所示，如果以 i, i' 為中心，畫出對稱的區(qū)域如圖，其中以i‘ = 7 對稱的區(qū)域是實心綠色 + 虛綠色和左側(cè)，虛綠色表示當前的對稱長度已經(jīng)超過之前的對稱中心C。而之前的P對稱性質(zhì)成立的原因是 i 右側(cè)剩余的長度 R - i 正好比以 i‘ 為中心的回文小。

這個性質(zhì)可以這樣歸納， $\color{red}{對于 i 而言，因為根據(jù)C對稱的最右是R，所以i的右側(cè)有 R - i 個元素是保證是 i' 左側(cè)是對稱的}$ 。 $\color{red}{ 而對于 i' 而言他的P值，也就是回文串的長度，可能會比 R-i 要大}$ 。 $\color{red}{如果大于 R - i, 對于i而言，我們只能暫時的先填寫 P[i] = R - i, 然后依據(jù)回文的屬性來擴充P[i] 的值}$ ； $\color{red}{如果P[i '] 小于R-i，那么說明在對稱區(qū)間C內(nèi)，i的回文串長度和i' 是一樣長的}$ 。例如我們的例子中 i = 15, 因為R = 20，所以i右側(cè) 在對稱區(qū)間剩余的是 R - 15 = 5, 而 i’ = 7 的長度是7. 說明 i' 的回文長度已經(jīng)超出對稱區(qū)間。我們只能使得P[i] 賦值為5，然后嘗試擴充P[i].

if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥R – i. (這里下一步操作是擴充 P[ i ].

擴充P[i] 之后，我們還要做一件事情是更新 R 和 C，如果當前對稱中心的最右延伸大于R，我們就更新C和R。在迭代的過程中，我們試探i的時候，如果P[i'] <= R - i, 那么只要做一件事情。如果不成立我們對當前P[i] 做擴展，因為最大長度是n，擴展最多就做n次，所以最多做2*n。所以最后算法復(fù)雜度是 O(n)

具體實現(xiàn)的代碼如下：

// 轉(zhuǎn)換S 到 T.
// 例如, S = "abba", T = "^#a#b#b#a#$".
// ^ 和 $ 作為哨兵標記加到兩端以避免邊界檢查
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);
 
  ret += "#$";
  return ret;
}
 
string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 1; i < n-1; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
 
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
 
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;
 
    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
 
  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 1; i < n-1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
 
  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

找工作知識儲備(2)---數(shù)組字符串那些經(jīng)典算法：最大子序列和，最長遞增子序列，最長公共子串，最長公共子序列，字符串編輯距離，最長不重復(fù)子串，最長回文子串

找工作知識儲備(2)---數(shù)組字符串那些經(jīng)典算法：最大子序列和，最長遞增子序列，最長公共子串，最長公共子序列，字符串編輯距離，最長不重復(fù)子串，最長回文子串

0、前言

一、最大子序列和

二、最長遞增子序列

三、最長公共子串（LCS）

四、最長公共子序列

五、字符串編輯距離

六、最長不重復(fù)子串

七、最長回文子串

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

找工作知識儲備(2)---數(shù)組字符串那些經(jīng)典算法：最大子序列和，最長遞增子序列，最長公共子串，最長公共子序列，字符串編輯距離，最長不重復(fù)子串，最長回文子串

0、前言

一、最大子序列和

二、最長遞增子序列

三、最長公共子串（LCS）

四、最長公共子序列

五、字符串編輯距離

六、最長不重復(fù)子串

七、最長回文子串

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

找工作知識儲備(2)---數(shù)組字符串那些經(jīng)典算法：最大子序列和，最長遞增子序列，最長公共子串，最長公共子序列，字符串編輯距離，最長不重復(fù)子串，最長回文子串

二、最長遞增子序列

四、最長公共子序列

五、字符串編輯距離

六、最長不重復(fù)子串