精华内容
下载资源
问答
  • 一个长度为n的字符串有多少子序列
    千次阅读 热门讨论
    2018-12-18 12:53:20

    一个大大的分割线,如果这个傻逼题没有被作为某某复赛的签到题,可能我一会都一直傻逼下去了。
    【2019计蒜之道复赛——星云系统】
    题目是,给出一个长度为n(1<n<5e6)的只有小写字母的字符串,然后找出一个长度为m的最小字典子序列
    更新: 这是一道简单得要死掉的单调栈裸题,为什么没想到呢,因为思路是,利用单调栈尽量求取结果字符串的最优值,也就说结果字符串在理想情况下是递增的,但是非理想情况是什么呢?因为有必须限定k个字母存在,因此被删掉的字母数量为len-k个字符,当被单调栈弹出的字符数量达到n-k个时,剩余的字符【即单调栈中的递增字符以及未遍历到的剩余字符】就组成了最小字典序ans。

    散了散了。。。时间复杂度是线性扫描的O(n)
    想想也是,题面都这个数量级了,还要啥常数。线性就完了。

    #include<bits/stdc++.h>
    #define M(a,b) memset(a,b,sizeof a)
    #define LL long long
    using namespace std;
    const int maxn=5000007;
    char a[maxn];
    stack<char>q;
    int n,m;
    int main()
    {
        while(!q.empty())q.pop();
        scanf("%s %d",a,&m);
        n=strlen(a);
        int cnt=0;
        int flag=n;
        for(int i=0; i<n; i++)
        {
            if(q.empty())q.push(a[i]);
            else
            {
                if(a[i]>q.top())q.push(a[i]);
                else
                {
                    while(!q.empty()&&q.top()>a[i])
                    {
                        q.pop();
                        cnt++;
                        if(cnt>=n-m)
                        {
                            flag=i;
                            break;
                        }
                    }
                    q.push(a[i]);
                }
            }
            if(cnt>=n-m)break;
        }
        string ans="";
        for(int i=n-1;i>flag;i--)ans+=a[i];
        while(!q.empty())ans+=q.top(),q.pop();
        reverse(ans.begin(),ans.end());
        ans=ans.substr(0,m);
        cout<<ans<<"\n";
    }
    

    头条一面挂了,除了自己菜,数据结构和基础知识理解不够深刻外,还有就是面试时紧张得肚子疼到抽搐。。。可能是绝症了

    言归正传,面试官本来想随便出个签到题玩一下开个场,结果被我紧张的崩了。
    结束面试之后冷静下来认真想了下并不难

    题目是,给出一个长度为n(1<n<10000)的只有小写字母的字符串,然后找出一个长度为m的最小字典子序列
    如 orange
    当m=3时,输出结果age

    若borange,且长度为3时,同样输出age

    面试的时候脑子一团浆糊,想到了标号和排序,直接被反例否定了。

    如果用最暴力的思想,找到n个字符里字典序最小且位序小于等于m的字母,然后砍去这个字母之前的字母,在剩余的字母中又找一个字典序最小的字母,这样一直找m个就好了。
    唯一要考虑的条件就是,这样不断贪心取最小的要求是,要保证取了某个字母后,剩余待选串中的字符个数要大于等于m。

    于是想到一个 复杂度为O(n*m) 的做法,每次遍历n字符串,查找符合条件的字符,再从头扫一遍找下一个字符。从头扫的原因是,当找到了一个字符,比如b,无法判断是否后面的字符是否存在一个字典序小于b的字符,所以仍要遍历完整个串才能得到一个最小值。这样是不可取的,必须进行优化。

    那么做一个预处理,首先26个vector存储每个字母出现位置的下标,O(n)遍历字符串,push进每个字母出现下标,因为是顺序遍历,所以每个vector都是有序的。
    然后遍历m次这26个vector,找出第一个字母的出现位置,满足<=n-(m-i)+1,说明存在一个较小的字母符合筛选条件,并且不用关心该位置剩余字符串是否存在比其更小的字母,如果存在,在字典序遍历其他vector就应该找到了。在ans中填入这个字母,然后从a字母开始继续查找下标大于上一个填入ans中字母下标的符合条件的字母。这个在有序vector中查找位置直接用二分即可。
    最后时间复杂度O(26*m),空间复杂度O(n)
    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    char a[10080];
    vector<int>pos[26];
    int main()
    {
        int n,m;
        char ans[10080];
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0;i<=26;i++)pos[i].clear();
            scanf("%d",&m);
            scanf("%s",a);
            for(int i=0; i<n; i++) pos[a[i]-'a'].push_back(i+1);
            memset(ans,0,sizeof ans);
            int tmp=0;
            for(int i=0; i<m; i++)
            {
                for(int j=0; j<26; j++)
                {
                    if(pos[j].size()!=0)
                    {
                        int num=pos[j][upper_bound(pos[j].begin(),pos[j].end(),tmp)-pos[j].begin()];
                        if(num>tmp&&num<=n-m+i+1)
                        {
                            tmp=num;
                            ans[i]='a'+j;
                            break;
                        }
                    }
                }
            }
            printf("%s\n",ans);
        }
    }
    
    更多相关内容
  • 字典序最大的子序列是这样构造的:给定一个字符串 a0a1…an−1a_{0}a_{1}…a_{n-1}a0​a1​…an−1​ ,首先在字符串中找到值最大的字符 aia_{i}ai​,然后在剩余的字符串 ai+1ai+2…ana_{i+1}a_{i+2}…a_{n}ai+1​ai+2...
  • 例如:输入两个字符串BDCABA和 ABCBDAB,字符串 BCBA和BDAB 都是是它们的最长公共子序列,则输出它们的长度4,并打印任意个子序列. (Note: 不要求连续)判断字符串相似度的方法之 - 最长公共子序列越长,越相似。...

    一. 最长公共子序列

    定义:

    一个数列S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

    例如:输入两个字符串BDCABA和 ABCBDAB,字符串 BCBA和BDAB 都是是它们的最长公共子序列,则输出它们的长度4,并打印任意一个子序列. (Note: 不要求连续)

    判断字符串相似度的方法之一 - 最长公共子序列越长,越相似。

    思路:

    穷举方法:

    穷举法是解决最长公共子序列问题最容易想到的方法,即对S的每一个子序列,检查是否为T的子序列,从而确定它是否为S和T的公共子序列,并且选出最长的公共子序列。

    S和T的所有子序列都检查过后即可求出S和T的最长公共子序列。S的一个子序列相应于下标序列1,2,...,n的一个子序列。因此,S共有2^n个子序列。当然,T也有2^m个子序列。

    因此,蛮力法的时间复杂度为O(2^n * 2^m),这是指数级别。

    动态规划方法:

    最优子结构性质:

    设序列 X= 和 Y= 的一个最长公共子序列 Z=,则:

    若 xm = yn,则 zk = xm = yn 则 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列;

    4b5d7deef7fe?from=singlemessage

    image.png

    若 xm ≠ yn, 要么Z是 Xm-1 和 Y 的最长公共子序列,要么 Z 是X和 Yn-1 的最长公共子序列。

    若 xm ≠ yn 且 zk≠xm ,则 Z是 Xm-1 和 Y 的最长公共子序列;

    若 xm ≠ yn 且 zk ≠yn ,则 Z 是X和 Yn-1 的最长公共子序列。

    综合一下:就是求二者的大者

    4b5d7deef7fe?from=singlemessage

    image.png

    递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算 X 和Y 的最长公共子序列时,可能要计算出 X 和 Yn-1 及 Xm-1 和 Y 的最长公共子序列。而这两个子问题都包含一个公共子问题,即计算 Xm-1 和 Yn-1 的最长公共子序列。

    4b5d7deef7fe?from=singlemessage

    image.png

    计算最优值:

    子问题空间中,总共只有O(m*n)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。

    长度表C 和 方向变量B:

    4b5d7deef7fe?from=singlemessage

    image.png

    实现代码:

    /**

    找出 两个 字符串 的公共 子序列(动态规划)

    @param str1 字符串1

    @param str2 字符串2

    */

    void maxPublicSubSequence(char *str1, char *str2) {

    assert(str1 != NULL && str2 != NULL);

    // 字符串 1 长度

    int str1Length = strlen(str1);

    // 字符串 2 长度

    int str2Length = strlen(str2);

    // 开辟 二维 存储 数组 (并初始化 值为:0)

    int **postionArray = (int **)malloc(sizeof(int *) * (str1Length + 1));

    for (int i = 0; i <= str1Length; i ++) {

    postionArray[i] = (int *)malloc(sizeof(int) * (str2Length + 1));

    }

    for (int i = 0; i <= str1Length; i++) {

    for (int j = 0; j <= str2Length; j++) {

    postionArray[i][j] = 0;

    }

    }

    // 循环 遍历

    for(int i = 1; i <= str1Length; i++) {

    for(int j = 1; j <= str2Length; j ++) {

    // 如果 两个字符 相同

    if (str1[i - 1] == str2[j - 1]) {

    postionArray[i][j] = postionArray[i - 1][j - 1] + 1;

    }

    // 如果 两个 字符 不同

    else {

    postionArray[i][j] = (postionArray[i - 1][j] > postionArray[i][j - 1]) ? postionArray[i - 1][j] : postionArray[i][j - 1];

    }

    }

    }

    for (int i = 0; i < str1Length; i++) {

    for (int j = 0; j < str2Length; j++) {

    printf("%d ", postionArray[i][j]);

    }

    printf("\n");

    }

    int i, j ;

    for (i = str1Length, j = str2Length; i >= 1 && j >= 1;) {

    if (str1[i - 1] == str2[j - 1]) {

    printf("%c ", str1[i - 1]);

    i --;

    j --;

    }

    else {

    if (postionArray[i][j - 1] > postionArray[i - 1][j]) {

    j--;

    }

    else {

    i --;

    }

    }

    }

    // 释放开辟数组

    for (int i = 0; i < str1Length; i++) {

    free(postionArray[i]);

    }

    free(postionArray);

    }

    int main(int argc, const char * argv[]) {

    @autoreleasepool {

    maxPublicSubSequenceTwo("ABCBDAB" , "BDCABA");

    }

    return 0;

    }

    二: 最长公共子串

    题目:

    给定两个字符串,求出它们之间最长的相同子字符串的长度。

    思路:

    穷举法:

    给定两个字符串A和B,我们可以通过从A的第一个字符开始与B对应的每一个字符进行对比的方式找到最长的公共字串。如果此时没有找到匹的字母,则移动到A的第二个字符处,然后从B的第一个字符处进行对比,以此类推。

    实现代码:

    #import

    /**

    找出 两个 字符串 的 最长 公共 子串 (穷举法)

    @param str1 字符串1

    @param str2 字符串2

    */

    void maxPublicSubStringOne(char *str1, char *str2) {

    assert(str1 != NULL && str2 != NULL);

    // 起始 位置

    int startPosition = 0;

    // 公共 子串 长度

    int maxStringLength = 0;

    // 循环 遍历 所有 子字符串

    for (int i = 0; i < strlen(str1); i ++) {

    for (int j = 0; j < strlen(str2); j++) {

    // 如果 两个 字符 相等

    if(str1[i] == str2[j]) {

    // 继续 比较 后面的字符

    int k = 1;

    while (str1[i + k] == str2[j + k] && str1[i + k] != '\0' && str2[j + k] != '\0') {

    k ++;

    }

    // 如果 k 大于 最长 字符串

    if (k > maxStringLength) {

    // 公共 子串 长度

    maxStringLength = k;

    // 起始位置

    startPosition = i;

    }

    }

    }

    }

    if(maxStringLength > 0) {

    for (int i = startPosition; i <= maxStringLength; i++) {

    printf("%c ", str1[i]);

    }

    }

    }

    动态规划-空间换时间

    采用一个二维矩阵来记录中间结果,矩阵的横坐标为字符串1的各个字符,矩阵的纵坐标为字符串2的各个字符。

    举例说明:假设两个字符串分别为"bab"和"caba" (当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

    b  a  b

    c  0  0  0

    a  0  1  0

    b  1  0  1

    a  0  1  0

    可以看出,矩阵的斜对角线最长的那个就对应着两个字符串的最长公共子串。

    不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,可以用下面的方法改进:当要在矩阵是填1时让它等于其左上角元素加1。

    b  a  b

    c  0  0  0

    a  0  1  0

    b  1  0  2

    a  0  2  0

    这样矩阵中的最大元素就是最长公共子串的长度。另外,在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。

    实现代码:

    /**

    找出 两个 字符串 的公共 子串(动态规划)

    @param str1 字符串1

    @param str2 字符串2

    */

    void maxPublicSubStringTwo(char *str1, char *str2) {

    assert(str1 != NULL && str2 != NULL);

    // 起始 位置

    int startPosition = 0;

    // 公共 子串 长度

    int maxStringLength = 0;

    // 字符串 1 长度

    int str1Length = strlen(str1);

    // 字符串 2 长度

    int str2Length = strlen(str2);

    // 开辟 二维 存储 数组 (并初始化 值为:0)

    int **postionArray = (int **)malloc(sizeof(int *) * str1Length);

    for (int i = 0; i < str1Length; i ++) {

    postionArray[i] = (int *)malloc(sizeof(int) * str2Length);

    }

    for (int i = 0; i < str1Length; i++) {

    for (int j = 0; j < str2Length; j++) {

    postionArray[i][j] = 0;

    }

    }

    // 循环 遍历

    for(int i = 0; i < str1Length; i++) {

    for(int j = 0; j < str2Length; j ++) {

    // 如果 两个字符 相同

    if (str1[i] == str2[j]) {

    // 判断 释放 是 边界 情况

    if (i == 0 || j == 0) {

    // 边界 情况

    postionArray[i][j] = 1;

    }

    // 非边界 情况

    else {

    postionArray[i][j] = postionArray[i - 1][j - 1] + 1;

    }

    if (postionArray[i][j] > maxStringLength) {

    maxStringLength = postionArray[i][j];

    startPosition = i - postionArray[i][j] + 1;

    }

    }

    }

    }

    // 打印 字符串

    if(maxStringLength > 0) {

    for (int i = 0; i <= maxStringLength; i++) {

    printf("%c ", str1[startPosition + i]);

    }

    }

    // 释放开辟数组

    for (int i = 0; i < str1Length; i++) {

    free(postionArray[i]);

    }

    free(postionArray);

    }

    展开全文
  • N个字符串理论知识:代码实现:测试样例:题目来源(参考)拓展:N个字符环,求最长公共子序列?代码实现:测试样例:题目补充:题目来源:特别说明:转载请注明出处: N个字符串 理论知识: 二进制模拟串实现暴力...

    N个字符串


    理论知识:

    二进制模拟串实现暴力破解——暴力枚举出(最长)公共子序列

    代码实现:

    #include <iostream>
    #include <string>
    #include <ctime>
    #include <algorithm>
    #include <set>
    #include <vector>
    using namespace std;
    
    // 判断字符串subSeq中的每一个字符在字符串str中的出现顺序是否为递增
    bool isSubsequence(const string& str, const string& subSeq) {
    	int index = -1; //设为-1而不是0,因为后边还要 +1;
    	for (char ch : subSeq) {
    		index = str.find_first_of(ch, index + 1); // 起始位置得是下一位,故需要 +1;
    		if (index == str.npos) {
    			return false;
    		}
    	}
    	return true;
    }
    // 多串的公共子序列判断;
    bool isComSeq(const vector<string>& vs, const string& subseq) {
    	for (string str : vs) {
    		if (!isSubsequence(str, subseq)) {
    			return false;
    		}
    	}
    	return true;
    }
    
    // 2 ^ 64 是上限,故 只能处理母串长度 <64 的情况;
    int main() {
    
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(0);
    
    	int n; // 带输入的字符串个数;
    	vector<string> vs; // 待输入的字符串;
    	string s; // 临时存储输入的字符串;
    	string s_little; // s输入的最短的字符串;
    	while (cin >> n) {
    		while (n--) {
    			cin >> s;
    			vs.push_back(s); // 存入字符串;
    			if (s_little.length() < s.length()) {
    				s_little = s;
    			}
    		}
    		clock_t startTime = clock();
    		// 确保遍历的是短字符串的所有子序列,并且是采用剔除元素的方式、自长到短遍历
    		
    		int len = s_little.length();
    		int cont = 1 << len;
    		string subSeq; // 临时存储子序列;
    		set<string> ss; // 存储所有公共子序列;
    		int longest = 0; // 最长公共子序列长度;
    		bool flag = false; // 公共子序列是否存在;
    		// i 将会直接影响到选择子集元素个数的多少(二进制表示);
    		for (int i = cont - 1; i >= 0; --i) {
    			for (int j = 0; j < len; ++j) {
    				if (i & (1 << j)) {
    					//cout << s1[j];
    					subSeq += s_little[j];
    				}
    			}
    			//cout << "subSeq = " << subSeq << endl;
    			// 接着判断 s_little 的子序列 subSeq 是否也同时是 其他字符串 的子序列;
    			
    			if (isComSeq(vs,subSeq)) {
    				if (longest <= subSeq.size()) { // 是公共子序列不行,还得是最长公共子序列才进行存储;
    					ss.insert(subSeq);
    					longest = subSeq.size();
    					flag = true; // 不放在 if 语句外边实为减少不必要的赋值次数;
    				}
    			}
    			subSeq.clear(); // 记得重置为空;
    			
    		}
    		// 不存在公共序列则输出空串;
    		//if (ss.empty()) {// 此判别条件存在漏洞,因为两个任意字符串至少存在  空串 作为公共子序列,故需要立flag;
    		if (!flag) {
    			cout << endl;
    		}
    		else {
    			for (auto item : ss) {
    				/*cout << item << endl;*/ // 输出所有公共子序列;
    				if (item.length() == longest) {
    					cout << item << endl;
    					//break; // 只需要输出ACSLL最小的最长公共子序列时,break;
    				}
    			}
    		}
    		// 重置容器为空;
    		s_little.clear();
    		vs.clear();
    		// ss.clear(); // ss 是局部声明,清空没有必要; 
    		// longgest = 0; 同理;
    		cout << "总共耗时:" << double(clock() - startTime) / CLOCKS_PER_SEC << "s" << endl;
    	}
    	return 0;
    }
    
    

    测试样例:

    鼠标置于此处可预览图片(Chrome)


    拓展:N个字符环,求最长公共子序列?


    代码实现:

    #include <iostream>
    #include <string>
    #include <ctime>
    #include <algorithm>
    #include <set>
    #include <vector>
    #include <cassert>
    using namespace std;
    
    // 判断字符串subSeq中的每一个字符在字符串str中的出现顺序是否为递增
    bool isSubsequence(const string& str, const string& subSeq) {
    	int index = -1; //设为-1而不是0,因为后边还要 +1;
    	for (char ch : subSeq) {
    		index = str.find_first_of(ch, index + 1); // 起始位置得是下一位,故需要 +1;
    		if (index == str.npos) {
    			return false;
    		}
    	}
    	return true;
    }
    
    // 字符串转字符环;
    vector<string> stringToRing(const string& str) {
    	vector<string> vs;
    	for (int i = 1; i <= str.size(); ++i) {
    		string str_right(&str[i], str.size() - i);
    		// string s_right(str, i, str.size() - i); // 等效写法 1 ;
    		// string s_right = str.substr(i, str.size() - i); // 等效写法 2 ;
    		string str_left(str, 0, i);
    		string s = str_right + str_left;
    		// cout << s << endl;
    		vs.push_back(s);
    	}
    	// 一个字符环 包含 n个与源字符串等长的字符串(n为源字符串的元素个数,即长度);
    	assert(vs.size() == str.length());
    	return vs;
    }
    
    // 多个字符环的公共子序列判断;
    bool isComSeq(const vector<string>& vs, const string& subseq) {
    	
    	for (string str : vs) {
    		// 在当前字符环中是否存在该子序列,存在一次即可满足条件;
    		bool flag = false; 
    		for (string item : stringToRing(str)) {
    			if (isSubsequence(item, subseq)) {
    				flag = true; // 存在一次即可;
    				break;
    			}
    		}
    		// 当前环找不着该序列;
    		if (!flag) {
    			return false;
    		}
    	}
    	return true;
    }
    
    // 2 ^ 64 是上限,故 只能处理母串长度 <64 的情况;
    int main() {
    
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(0);
    
    	int n; // 带输入的字符串个数;
    	vector<string> vs; // 待输入的字符串(源字符串);
    	string s; // 临时存储输入的字符串;
    	string s_little; // s输入的最短的字符串;
    	while (cin >> n) {
    		while (n--) {
    			cin >> s;
    			vs.push_back(s);  // 存入字符环;
    			if (s_little.length() < s.length()) {
    				s_little = s;
    			}
    		}
    		clock_t startTime = clock();
    
    		string subSeq; // 临时存储子序列;
    		set<string> ss; // 存储所有公共子序列;
    		int longest = 0; // 最长公共子序列长度;
    		bool flag = false; // 公共子序列是否存在;
    
    		for (string item : stringToRing(s_little)) {
    
    			// 确保遍历的是短字符串的所有子序列,并且是采用剔除元素的方式、自长到短遍历
    			int len = item.length();
    			int cont = 1 << len;
    
    			// i 将会直接影响到选择子集元素个数的多少(二进制表示);
    			for (int i = cont - 1; i >= 0; --i) {
    				for (int j = 0; j < len; ++j) {
    					if (i & (1 << j)) {
    						//cout << s1[j];
    						subSeq += item[j];
    					}
    				}
    				//cout << "subSeq = " << subSeq << endl;
    				// 接着判断 s_little 的子序列 subSeq 是否也同时是 其他字符串 的子序列;
    
    				if (isComSeq(vs, subSeq)) {
    					if (longest <= subSeq.size()) { // 是公共子序列不行,还得是最长公共子序列才进行存储;
    						ss.insert(subSeq);
    						longest = subSeq.size();
    						flag = true; // 不放在 if 语句外边实为减少不必要的赋值次数;
    					}
    				}
    				subSeq.clear(); // 记得重置为空;
    
    			}
    		}
    		// 不存在公共序列则输出空串;
    		//if (ss.empty()) {// 此判别条件存在漏洞,因为两个任意字符串至少存在  空串 作为公共子序列,故需要立flag;
    		if (!flag) {
    			cout << endl;
    		}
    		else {
    			for (auto item : ss) {
    				/*cout << item << endl;*/ // 输出所有公共子序列;
    				if (item.length() == longest) {
    					cout << item << endl;
    					//break; // 只需要输出ACSLL最小的最长公共子序列时,break;
    				}
    			}
    		}
    		// 重置容器为空;
    		s_little.clear();
    		vs.clear();
    		ss.clear(); // ss 是局部声明,清空没有必要; 
    		longest = 0; // 同理;
    		cout << "总共耗时:" << double(clock() - startTime) / CLOCKS_PER_SEC << "s" << endl;
    	}
    	return 0;
    }
    
    

    测试样例:

    鼠标置于此处预览(Chrome)

    题目补充:


    题目来源:
    ACM-ICPC 2018 北京赛区网络预赛 Tomb Raider
    

    特别说明:
    该考题的输出仅仅是一个ACSLL码最小的最长公共子序列串,
    自己的测试是左右公共子序列。
    
    有上述 从N个字符串找最长公共子序列,到N个字符环找最长公共子序列的过程可以发现:环的公共子序列的结果数量明细增多。
    
    并且值得注意的是:
    代码证容易被遗漏的地方是, s_little也需要先生成对应的字符环(多个字符串),再各自去生成各自的所有子序列,然后拿来校验。
    而不是仅仅针对 s_little 的源字符串生成所有子序列。
    
    

    其他说明:


    博客补充以强化理解:

    助你深刻理解——最长公共子串、最长公共子序列(应该是全网数一数二的比较全面的总结了)

    转载请注明出处:
    https://blog.csdn.net/I_love_you_dandan/article/details/103227017
    
    以上代码皆为本人亲自码字、亲自测试,如有问题需要咨询或者指正,可以直接在评论区留言或者发送私信进行友好交流。
    
    联系方式:2636105163@qq.com
    2019/11/24  20:43
    
    展开全文
  • 一个字符串的最长递增子序列长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入描述: 第一行一个整数0<n<20,表示有n字符串要处理 随后的n行,每行有一个字符串,该字符串长度不会超过10000 输出...

    题目

    求一个字符串的最长递增子序列的长度
    如:dabdbf最长递增子序列就是abdf,长度为4
    输入描述:
    第一行一个整数0<n<20,表示有n个字符串要处理
    随后的n行,每行有一个字符串,该字符串的长度不会超过10000
    输出描述:
    输出字符串的最长递增子序列的长度
    样例输入:
    复制
    3
    aaa
    ababc
    abklmncdefg
    样例输出:
    1
    3
    7

    分析:

    求字符串的最长递增子序列,可将问题分解为一个个小问题,先计算字符串长度为1的最长递增,再计算长度为2,以此类推,直到计算为n

    思路:(1.以下j表示数组下标 2.括号中为举例说明 如:dabdbf)

    1. 计算长度为前j个字符串子串的最长递增子序列(如:babd)
    2. 将第j个字符与前j-1个字符一一比较(如,d与bab进行比较)
    3. 若第j个大于前j-1个中任意一个字符k,取dp[j]与dp[k]+1最大值
    4. dp[k]+1是因为前k个字符的最大递增序列加上第j个字符,最大递增子序列为dp[k]+1

    代码如下:

    /*
    求一个字符串的最长递增子序列的长度
    如:dabdbf最长递增子序列就是abdf,长度为4
    输入描述:
    第一行一个整数0<n<20,表示有n个字符串要处理
    随后的n行,每行有一个字符串,该字符串的长度不会超过10000
    输出描述:
    输出字符串的最长递增子序列的长度
    样例输入:
    复制
    3
    aaa
    ababc
    abklmncdefg
    样例输出:
    1
    3
    7
    */
    #include<stdio.h>
    #include<string.h>
    int main(void){
    	int n;
    	int i,j,k;
    	scanf("%d",&n);
    	char array[n][10000]; //存储字符数组
    	int flag[n]; 
    	for(i=0;i<n;i++){
    		scanf("%s",&array[i]);
    	}
    	//计算递增序列 
    	for(i=0;i<n;i++){
    		int length = strlen(array[i]);
    		int dp[length]; //利用动态规划计算每一步的最长子序列 
    		for(j=0;j<length;j++){
    			dp[j]=1;
    		}
    		for(j=0;j<length;j++){
    			for(k=0;k<j;k++){
    				if(array[i][j] > array[i][k]){  //如果str[k] < str[j] 取最大值 
    					dp[j]=max(dp[k]+1,dp[j]); 
    				}
    			}
    		}
    		flag[i]=dp[length-1]; 
    	} 
    	
    	for(i=0;i<n;i++){
    		printf("%d\n",flag[i]);
    	}
    	return 0;
    }
    
    /*
    	比较num1和num2的最大值 并返回最大值 
    */
    int max(int num1,int num2){
    	if(num1>num2){
    		return num1;
    	}else if(num1<num2){
    		return num2;
    	}else{//等于 
    		return num1;
    	}
    } 
    

    在这里插入图片描述

    展开全文
  • 给定两个字符串str1和str2,输出连个字符串的最长公共子序列。 如过最长公共子序列为空,则输出-1。 输入描述 输出包括两行,第行代表字符串str1,第二行代表str2。 (1≤length(str1),length(str2)≤5000) 输出...
  • 一个字符串的最长递增子序列长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入描述: 第一行一个整数0&amp;amp;amp;amp;lt;n&amp;amp;amp;amp;lt;20,表示有n字符串要处理 随后的n行,每行有一...
  • 求解两个字符串的最长公共子序列

    千次阅读 2020-06-16 09:38:22
    则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二,算法求解 这是一个动态规划的题目。对于可用动态规划求解的问题,一般两个特征:①最优子结构;②重叠子问题 ①最优子结构 设 X=(x1,x2,....
  • 题目描述 小z玩腻了迷宫游戏,于是他找到了Easy,准备...现在小z想请教Easy老师,M字符串有多少个字符串是大字符串S的子序列? 如果Easy老师答不上来就要请客,现在Easy老师很苦恼,你能帮帮他吗? 子序列可以理...
  • 字符串 - 判断子序列

    千次阅读 2020-07-27 11:27:11
    定义 假如字符串 s 是 t 的子序列,那么可以...时间复杂度:O(N + M),N和M个字符串长度。 #include <iostream> #include <vector> #include <cstdio> #include <string> #include <
  • 给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。 样例 给出"ABCD" 和 "EDCA",这LCS是 "A" (或 D或C),返回1 给出 "ABCD" 和 "EACB",这LCS是"AC"返回 2 说明 最长公共子序列的定义: 最长公共...
  • d p [ i ] [ j ] dp[i][j] dp[i][j]表示在第一个字符串的 i i i位以前和第二个字符串的 j j j位以前最长公共子序列长度。我们思考方式呢就是看最后一位是否相同。如果相同,那么直接用前一个状态加一就可以了。...
  • 数组中的子数组、子序列,以及字符串的子串、子序列解释数组子数组子序列字符串子串子序列 数组 子数组 子数组的定义:一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素) 子序列 子序列的定义:...
  • 题目从长度为N字符串中随机选出M字符(不打破原有顺序)并输出。思路此选择问题可分解: 1. 选择当前字符,并在剩余字符中选择M-1... * 输出长度为N字符串的所有长度为M的子序列 * */ public class RandomStr
  • 问题描述:求两个字符串的最长...如果xm == yn, 则这个字符就是子序列中的一个字符, LCS就是序列{x0, x1, x2,......, xm-1}和{y0, y1, y2,......, yn-1}的LCS加上xm(或yn)。 如果xm != yn, 则求序列{x0, x1, x2,...
  • 给定字符串 s 和 t ,判断 s 是否 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是字符串长度 <=100)。 字符串个子序列是原始字符串删除...
  • 公共子序列是在整个字符串中只要按照顺序可以不用连续的,但是公共子串是指必须连续的字符串,举个例子: ABCBDAB BDCABA 最长公共子序列是 : BCBA 最长公共字串是 : AB 递归思路 先将两个字符串的第一个字符进行...
  • 给定两个字符串A,B,长度分别m,n。要求求出他们的最长公共子序列,返回其长度,例如 A = “hello word” B = “loop” 最长公共子序列为“loo” 长度为3 思路 动态规划的子问题res[i][j]截止到字符串A的第i...
  • 字符串最小字典序子序列

    千次阅读 2019-04-15 20:47:39
    10000)的只有小写字母的字符串,然后找出一个长度为m的最小字典子序列。 做一个预处理,首先26个vector存储每个字母出现位置的下标,O(n)遍历字符串,push进每个字母出现下标,因为是顺序遍历,所以每个vector都是...
  • 【算法】字符串中的子串与子序列

    千次阅读 2020-09-02 16:49:43
    假设字符串长度为n,其非空子串的数目n(n+1)/2。例如字符串“abc“的连续子串 a,ab,abc,b,bc,c 代码:(实现求s字符串的所有不重复子串) //s待求字符串,res集合为子串集合 void gets(string s, set<...
  • 使用一个二维数组arr[n+1][m+1]来记录每种情况下最长公共子序列长度。 初始状态:字符串a空元素,字符串b空元素。这样的情况就填0.也就是二维数组首行首列全为0. 假设: a{a,b,c,d} b{b,c,a,d} 行 i 是字符...
  • (1)子序列的含义:一个序列S,任意删除若干个(可0个)字符后得到的序列C,则C称为S的子序列 (2)最长公共子序列定义两个序列的公共子序列中最长的一个或若干个。 (3)任意两个序列X和Y,至少存在一个公共...
  • N个字符串的最长公共子串,N字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长公共子串“local...
  • 字符串子序列

    2022-02-18 10:42:10
    字符串
  • 字符串中最长无重复子序列

    万次阅读 2020-08-16 17:32:10
    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 129,961
精华内容 51,984
热门标签
关键字:

一个长度为n的字符串有多少子序列

友情链接: pwm.rar