精华内容
下载资源
问答
  • 子序列

    万次阅读 2021-02-28 22:35:29
    求有多少长度为m的小写字母字符串S满足,T是S的一个子序列(不需要连续) 输入描述: 第一行一个字符串T 第二行一个正整数m 输出描述: 输出答案对109+7取模的值 示例1 输入 a 2 输出 51 说明 长度为2的里面有a的串有51...

    给定一个小写字母字符串T

    求有多少长度为m的小写字母字符串S满足,T是S的一个子序列(不需要连续)

    输入描述:
    第一行一个字符串T
    第二行一个正整数m

    输出描述:
    输出答案对109+7取模的值
    示例1
    输入
    a
    2
    输出
    51
    说明
    长度为2的里面有a的串有51种

    备注:
    1<=|T|,m<=105

    #include<stdio.h>
    #include<string.h>
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    const int p=1e9+7;
    char t[110000];
    long long C,ans,inv[110000],p25[110000],p26[110000];
    int main()
    {
    	int m,l;
    	scanf("%s%d",t,&m);
    	l=strlen(t);
    	p25[0]=p26[0]=1;
    	fo(i,1,m)
    	{
    		p25[i]=p25[i-1]*25%p;
    		p26[i]=p26[i-1]*26%p;
    	}
    	inv[0]=inv[1]=1;
    	fo(i,2,m) inv[i]=(p-p/i)*inv[p%i]%p;
    	C=1;
    	fo(i,l,m)
    	{
    		ans+=C*p25[i-l]%p*p26[m-i]%p;
    		C=C*i%p*inv[i+1-l]%p;
    	}
    	ans%=p;
    	printf("%lld\n",ans);
    	return 0;
    }
    
    展开全文
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
     首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后...

    1.基本概念

          首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢?给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下:


           如上图,给定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原有的元素序列所得到的结果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。
           它的字串示例:{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的字串。同理,{a,b,c,d},{g,h}等都是它的字串。

            这个问题说明白后,最长公共子序列(以下都简称LCS)就很好理解了。
    给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。
    s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}

    2.动态规划

           求解LCS问题,不能使用暴力搜索方法。一个长度为n的序列拥有 2的n次方个子序列,它的时间复杂度是指数阶,太恐怖了。解决LCS问题,需要借助动态规划的思想。
           动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

    3.特征分析

           解决LCS问题,需要把原问题分解成若干个子问题,所以需要刻画LCS的特征。

           设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质:
           如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;
           如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0,a1,…,a(m-1)”和“b0,b1,…,bn”的一个最长公共子序列;
           如果am!=bn,则若zk!=bn,蕴涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n-1)”的一个最长公共子序列。

           有些同学,一看性质就容易晕菜,所以我给出一个图来让这些同学理解一下:


           以我在第1小节举的例子(S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}),并结合上图来说:

           假如S1的最后一个元素 与 S2的最后一个元素相等,那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS  再加上 S1和S2相等的最后一个元素。

           假如S1的最后一个元素 与 S2的最后一个元素不等(本例子就是属于这种情况),那么S1和S2的LCS就等于 : {S1减去最后一个元素} 与 S2 的LCS, {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

    4.递归公式

            第3节说了LCS的特征,我们可以发现,假设我需要求 a1 ... am 和 b1 .. b(n-1)的LCS 和 a1 ... a(m-1) 和 b1 .. bn的LCS,一定会递归地并且重复地把如a1... a(m-1) 与 b1 ... b(n-1) 的 LCS 计算几次。所以我们需要一个数据结构来记录中间结果,避免重复计算。

            假设我们用c[i,j]表示Xi 和 Yj 的LCS的长度(直接保存最长公共子序列的中间结果不现实,需要先借助LCS的长度)。其中X = {x1 ... xm},Y ={y1...yn},Xi = {x1 ... xi},Yj={y1... yj}。可得递归公式如下:

             

    5.计算LCS的长度

           这里我不打算贴出相应的代码,只想把这个过程说明白。还是以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。我们借用《算法导论》中的推导图:


             图中的空白格子需要填上相应的数字(这个数字就是c[i,j]的定义,记录的LCS的长度值)。填的规则依据递归公式,简单来说:如果横竖(i,j)对应的两个元素相等,该格子的值 = c[i-1,j-1] + 1。如果不等,取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化该表:

             

              然后,一行一行地从上往下填:

             

              S1的元素3 与 S2的元素3 相等,所以 c[2,1] = c[1,0] + 1。继续填充:

              

                S1的元素3 与 S2的元素5 不等,c[2,2] =max(c[1,2],c[2,1]),图中c[1,2] 和 c[2,1] 背景色为浅黄色。

                继续填充:

                

                

                 

                   中间几行填写规则不变,直接跳到最后一行:

                  

                    至此,该表填完。根据性质,c[8,9] = S1 和 S2 的 LCS的长度,即为5。

    6.构造LCS

           本文S1和S2的最LCS并不是只有1个,本文并不是着重讲输出两个序列的所有LCS,只是介绍如何通过上表,输出其中一个LCS。

           我们根据递归公式构建了上表,我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。

           c[8][9] = 5,且S1[8] != S2[9],所以倒推回去,c[8][9]的值来源于c[8][8]的值(因为c[8][8] > c[7][9])。

           c[8][8] = 5,  且S1[8] = S2[8], 所以倒推回去,c[8][8]的值来源于 c[7][7]。

           以此类推,如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)。

           第一种结果为:

           

              这就是倒推回去的路径,棕色方格为相等元素,即LCS = {3,4,6,7,8},这是其中一个结果。

              如果如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,选择另一个方向,会得到另一个结果。

              

               即LCS ={3,5,7,7,8}。

    7.关于时间复杂度

            构建c[i][j]表需要Θ(mn),输出1个LCS的序列需要Θ(m+n)。


              本文内容参考如下:

            【1】http://baike.baidu.com/link?url=iKrtEZXAQ3LeQLL7Z0HQWpy7EO7BZInUR17C63lAIDFBJ_COm8e3KmKVxQCD6DlOvji2F9W6achz49Z_anZCfa

            【2】《算法导论》第3版 15.4节


            注意:
            如您发现本文档中有明显错误的地方,
            或者您发现本文档中引用了他人的资料而未进行说明时,请联系我进行更正。
            转载或使用本文档时,请作醒目说明。
            必要时请联系作者,否则将追究相应的法律责任。

            note:
            If you find this document with any error ,
            Or if you find any illegal citations , please contact me correct.
            Reprint or use of this document,Please explain for striking. 
            Please contact the author if necessary, or they will pursue the corresponding legal responsibility.



    展开全文
  • 算法 - 求一个数组的最长递减子序列(C++)

    万次阅读 多人点赞 2019-02-27 20:14:07
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... * 题目: 求一个数组的最长递减子序列,比如{8, 14, 6, 2, 8, 14, 3, 2, 7, 4, 7, 2, 8, 101, 23, 6, 1, 2...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    /*
     * 求一个数组的最长递减子序列 - C++ - by Chimomo
     *
     * 题目: 求一个数组的最长递减子序列,比如{8, 14, 6, 2, 8, 14, 3, 2, 7, 4, 7, 2, 8, 101, 23, 6, 1, 2, 1, 1}的最长递减子序列为{14,8,3,2,1}。
     *
     * Answer: Scan from left to right, maintain a decreasing sequence.
     * For each number, binary search in the decreasing sequence to see whether it can be substituted.
     */
    
    #include <iostream>
    #include <cassert>
    #include <stack>
    
    using namespace std;
    
    int BinarySearch(const int *A, int nTarget, int nLen);
    
    /**
     * Find the longest decreasing sequence in array A of length nLen.
     * @param A The array.
     * @param nLen The array length.
     */
    void FindLongestDecreasingSequence(int *A, int nLen) {
        int *index = new int[nLen];
        int *LDS = new int[nLen];
        index[0] = A[0];
        LDS[0] = 1;
        int indexLen = 1;
    
        for (int i = 1; i < nLen; i++) {
            int pos = BinarySearch(index, A[i], indexLen);
            index[pos] = A[i];
            LDS[i] = pos + 1;
            if (pos >= indexLen) {
                indexLen++;
            }
        }
    
        int ResultLen = indexLen;
    
        for (int i = nLen; i >= 0; i--) {
            if (LDS[i] == ResultLen) {
                index[ResultLen - 1] = A[i];
                ResultLen--;
            }
        }
    
        for (int i = 0; i < indexLen; i++) {
            cout << index[i] << " ";
        }
    
        delete[] index;
    }
    
    /**
     * Binary search nTarget in array A of length nLen.
     * @param A The array.
     * @param nTarget The target.
     * @param nLen The array length.
     * @return The position.
     */
    int BinarySearch(const int *A, int nTarget, int nLen) {
        assert(A != nullptr && nLen > 0);
        int start = 0;
        int end = nLen - 1;
    
        while (start <= end) {
            int mid = (start + end) / 2;
    
            if (nTarget > A[mid]) {
                end = mid - 1;
            } else if (nTarget < A[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
    
        return start;
    }
    
    int main() {
        int A[] = {8, 14, 6, 2, 8, 14, 3, 2, 7, 4, 7, 2, 8, 101, 23, 6, 1, 2, 1, 1};
        int nLen = sizeof(A) / sizeof(int);
        FindLongestDecreasingSequence(A, nLen);
        return 0;
    }
    
    // Output:
    /*
    14 8 7 6 2 1
    */
    

     

    展开全文
  • 动态规划解最长公共子序列(LCS)(附详细填表过程)

    万次阅读 多人点赞 2018-11-20 12:51:34
    子序列形式化定义: 公共子序列定义: 最长公共子序列(以下简称LCS): 方法 蛮力法求解最长公共子序列: 动态规划求解最长公共子序列: 分析规律: 做法: 伪代码: 下面演示下c数组的填表过程:(以求...

    目录

    相关概念

    子序列形式化定义:

    公共子序列定义:

    最长公共子序列(以下简称LCS):

    方法

    蛮力法求解最长公共子序列:

    动态规划求解最长公共子序列:

    分析规律:

    做法:

    伪代码:

    下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例):

    时间复杂度:

    代码:

    结果示例:


    相关概念

    子序列形式化定义:

    给定一个序列X=<x1,x2,x3,x4...,xm>,另一个序列Z=<z1,z2,z3,z4...,zk>,若存在一个严格递增的X的下标序列<i1,i2,i3,...,ik>对所有的1,2,3,...,k,都满足x(ik)=zk,则称Z是X的子序列

    比如Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>的子序列

    公共子序列定义:

    如果Z既是X的子序列,又是Y的子序列,则称Z为X和Y的公共子序列

    最长公共子序列(以下简称LCS):

    2个序列的子序列中长度最长的那个

    方法

    蛮力法求解最长公共子序列:

    需要遍历出所有的可能,时间复杂度是O(n³),太慢了

    动态规划求解最长公共子序列:

    分析规律:

    设X=<x1,x2,x3,x4...,xm>,Y=<y1,y2,y3,y4...,yn>为两个序列,Z=<z1,z2,z3,z4...,zk>是他们的任意公共子序列

    经过分析,我们可以知道:

    1、如果xm = yn,则zk = xm = yn 且 Zk-1是Xm-1和Yn-1的一个LCS

    2、如果xm != yn 且 zk != xm,则Z是Xm-1和Y的一个LCS

    3、如果xm != yn 且 zk != yn,则Z是X和Yn-1的一个LCS

    所以如果用一个二维数组c表示字符串X和Y中对应的前i,前j个字符的LCS的长度话,可以得到以下公式:

    文字意思就是:

    p1表示X的前 i-1 个字符和Y的前 j 个字符的LCS的长度

    p2表示X的前 i 个字符和Y的前 j-1 个字符的LCS的长度

    p表示X的前 i-1 个字符和Y的前 j-1 个字符的LCS的长度

    p0表示X的前 i 个字符和Y的前 j 个字符的LCS的长度

    如果X的第 i 个字符和Y的第 j 个字符相等,则p0 = p + 1

    如果X的第 i 个字符和Y的第 j 个字符不相等,则p0 = max(p1,p2)

     

    做法:

    因此,我们只需要从c[0][0]开始填表,填到c[m-1][n-1],所得到的c[m-1][n-1]就是LCS的长度

    但是,我们怎么得到LCS本身而非LCS的长度呢?

    也是用一个二维数组b来表示:

    在对应字符相等的时候,用↖标记

    在p1 >= p2的时候,用↑标记

    在p1 < p2的时候,用←标记

    伪代码:

    若想得到LCS,则再遍历一次b数组就好了,从最后一个位置开始往前遍历:

    如果箭头是↖,则代表这个字符是LCS的一员,存下来后 i-- , j--

    如果箭头是←,则代表这个字符不是LCS的一员,j--

    如果箭头是↑ ,也代表这个字符不是LCS的一员,i--

    如此直到i = 0或者j = 0时停止,最后存下来的字符就是所有的LCS字符

    比如说求ABCBDAB和BDCABA的LCS:

    灰色且带↖箭头的部分即为所有的LCS的字符

     

    下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例):

    以此类推

    最后填出的表为:

    右下角的2即为LCS的长度

     

    时间复杂度:

    由于只需要填一个m行n列的二维数组,其中m代表第一个字符串长度,n代表第二个字符串长度

    所以时间复杂度为O(m*n)

    代码:

    #include <iostream>
    #include <string>
    #include <stack>
    using namespace std;
    void LCS(string s1,string s2)
    {
        int m=s1.length()+1;
        int n=s2.length()+1;
        int **c;
        int **b;
        c=new int* [m];
        b=new int* [m];
        for(int i=0;i<m;i++)
        {
            c[i]=new int [n];
            b[i]=new int [n];
            for(int j=0;j<n;j++)
                b[i][j]=0;
        }
        for(int i=0;i<m;i++)
            c[i][0]=0;
        for(int i=0;i<n;i++)
            c[0][i]=0;
        for(int i=0;i<m-1;i++)
        {
            for(int j=0;j<n-1;j++)
            {
                if(s1[i]==s2[j])
                {
                    c[i+1][j+1]=c[i][j]+1;
                    b[i+1][j+1]=1;          //1表示箭头为  左上
                }
                else if(c[i][j+1]>=c[i+1][j])
                {
                    c[i+1][j+1]=c[i][j+1];
                    b[i+1][j+1]=2;          //2表示箭头向  上
                }
                else
                {
                    c[i+1][j+1]=c[i+1][j];
                    b[i+1][j+1]=3;          //3表示箭头向  左
                }
            }
        }
        for(int i=0;i<m;i++)                //输出c数组
        {
            for(int j=0;j<n;j++)
            {
                cout<<c[i][j]<<' ';
            }
            cout<<endl;
        }
        stack<char> same;                   //存LCS字符
        stack<int> same1,same2;             //存LCS字符在字符串1和字符串2中对应的下标,方便显示出来
        for(int i = m-1,j = n-1;i >= 0 && j >= 0; )
        {
            if(b[i][j] == 1)
            {
                i--;
                j--;
                same.push(s1[i]);
                same1.push(i);
                same2.push(j);
            }
            else if(b[i][j] == 2)
                    i--;
                 else
                    j--;
        }
        cout<<s1<<endl;                     //输出字符串1
        for(int i=0;i<m && !same1.empty();i++)      //输出字符串1的标记
        {
            if(i==same1.top())
            {
                cout<<1;
                same1.pop();
            }
            else
                cout<<' ';
        }
        cout<<endl<<s2<<endl;                //输出字符串2
        for(int i=0;i<n && !same2.empty();i++)      //输出字符串2的标记
        {
            if(i==same2.top())
            {
                cout<<1;
                same2.pop();
            }
            else
                cout<<' ';
        }
        cout<<endl<<"最长公共子序列为:";
        while(!same.empty())
        {
            cout<<same.top();
            same.pop();
        }
        cout<<endl<<"长度为:"<<c[m-1][n-1]<<endl;
        for (int i = 0; i<m; i++)
        {
            delete [] c[i];
            delete [] b[i];
        }
        delete []c;
        delete []b;
    }
    int main()
    {
        string s1="ABCPDSFJGODIHJOFDIUSHGD";
        string s2="OSDIHGKODGHBLKSJBHKAGHI";
        LCS(s1,s2);
        return 0;
    }
    

    结果示例:

    展开全文
  • 1、最长公共子序列: 举个例子,s1=“abcfde”,s2=“fdea”。那么s1与s2的最长公共子序列就是"fde"。该问题是典型的动态规划问题,我们设maxlen(i,j)表示s1左边i个字符与s2左边j个字符的最长公共子序列长度,(i,j...
  • 最长递增子序列(LIS)

    万次阅读 多人点赞 2019-03-12 10:20:54
    ① dp[i] 表示以 i 为结尾的最长子序列长度 ② dp[i] 表示长度为 i 的最长递增子序列末尾的数
  • 最长不升公共子序列问题的动态规划算法,结果求出了子序列的长度以及该子序列是什么,采用的是Java。
  • 面试中除了排序问题,还会经常出现字符串的子序列问题,这里讲解使用动态规划解决三个常见的子序列问题: 1、最长公共子序列问题(LCS,longest-common-subsequence problem) 2、最长连续公共子序列问题 3、最长...
  • 求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
  • 问题描述:给定两个序列,例如 X = “ABCBDAB”、Y = “BDCABA”,求它们的最长公共子序列的长度。 下面是求解时的动态规划表,可以看出 X 和 Y 的最长公共子序列的长度为4: 输出一个最长公共子序列并不难(网上很...
  • 2021-06-28:最接近目标值的子序列和。给你一个整数数组 nums 和一个目标值 goal 。你需要从 nums 中选出一个子序列,使子序列元素总和最接近 goal 。也就是说,如果子序列元素和.pdf
  • 最长公共子序列、最长连续公共子序列
  • 最长公共子序列python实现,最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。 1.找出最优解的性质,并刻划其结构特征 序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么a[:m]和b[:...
  • m子序列的特性研究

    2020-05-27 00:02:15
    针对m序列线性复杂度不高,非线性度为零等问题,采用B-M算法对构造出的第一类m子序列进行了线性复杂度的研究,得出m子序列的线性复杂度和m序列相比大的多,逼近序列长度的一半的结论。利用Walsh频谱技术分析了m子序列的...
  • 对于求最长递增子序列和最长公共子序列的问题,最简单的方法就是动态规划 最长递增子序列 给定义一组数据【-1,2,4,3,5,6,7,5】,最长递增子序列是-1,2,3,5,6,7,结果为6 思路:dp[i]来记录a[i]为结尾的...
  • 字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=(x0,x1,…,xm-1),序列Y=(y0,y1,…,yk-1)是X的子序列,存在X的一个...
  • 子序列 返回int子序列的函数。 最长的递增子序列 最长的递减子序列 最长的公共子序列 公共区域。
  • 最长公共子序列

    2014-09-30 09:44:03
    序列Z=,C,D,B>是序列X=,B,C,B,D,A,B>的子序列,相应的递增下标序列为,3,5,7>。 一般地,给定一个序列X=,x2,…,xm>,则另一个序列Z=,z2,…,zk>是X的子序列,是指存在一个严格递增的下标序列〈i1,i2,…,ik...
  • LCS最长公共子序列

    2016-09-07 18:27:27
    一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=, x2,…, xm>,则另一序列Z=, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 , i2,…, ik>,使得对于所有j=1,2,…,k有:...
  • 最短子序列

    2012-10-20 18:23:32
    使用C++实现最短子序列,对正在学习算法的同学应该挺有帮助的
  • 1.求最长递增子序列长度 方法一:动态规划O(n2) public static int findLongest2(int[] A) { int n = A.length; int[] f = new int[n];// 用于存放f(i)值; f[0] = 1;// 以第a1为末元素的最长递增子序列...
  • 排序子序列

    千次阅读 2017-05-20 14:59:25
    牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段...
  • 最长上升子序列

    千次阅读 2018-09-02 15:38:34
    子序列:一段序列中选取一些位置递增(或递减)的元素作为子序列,如 {1,2,3,4,5,6,7,8,9}这一段序列,可以选取{1,3,5,8,9}作为子序列,也可以选取{1,2,4,7}作为子序列。 最长上升子序列子序列中的所有元素都是...
  • Java实现子序列问题

    万次阅读 多人点赞 2019-07-20 18:05:46
    如果不要求连续,则可称为它的子序列。 比如对串: "abcdefg" 而言,"ab","abd","bdef" 等都是它的子序列。 特别地,一个串本身,以及空串也是它的子序列。 对两个串而言,可以有许多的共同的子序列,我们关心的是...
  • PAGE / NUMPAGES 算法探讨再议经典算法问题求最大子序列和绝对值最大子序列和以及其区间 给定任一数字序列如{-5,4,-20,16,-2,-3}求出其最大子序列和绝对值最大子序列和以及对应的区间在这个例子中人肉计算可知最大...
  • 数组中的子数组、子序列,以及字符串的子串、子序列解释数组子数组子序列字符串子串子序列 数组 子数组 子数组的定义:一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素) 子序列 子序列的定义:...
  • 查找两个字符序列的公共子序列,查找到的是两个字符串的所有公共子序列

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 602,923
精华内容 241,169
关键字:

子序列