精华内容
下载资源
问答
  • 头条一面挂了,除了自己菜,数据结构和基础知识理解深刻外,还有就是面试时紧张得肚子疼到抽搐。...10000)的只有小写字母的字符串,然后找出一个长度为m的最小字典子序列。 如 orange 当m=3时,输出结果age 若borang...

    一个大大的分割线,如果这个傻逼题没有被作为某某复赛的签到题,可能我一会都一直傻逼下去了。
    【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);
        }
    }
    
    展开全文
  • 题目(软考-软件设计师2006上半年上午试题):对于求取两个长度为n字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度O(n2)的正确算法。...
    题目(软考-软件设计师2006上半年上午试题):对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为
     (58) 。 
    (57)A.分治          B.贪心     C.动态规划      D.分支一限界 

    (58)A.3           B.4       C.5          D.6

    一直没有找到自己认为合理的解释,今天看到一种解答方式,觉得有道理,特此引用,感谢解答人。以下为引用内容(引用自:http://bbs.educity.cn/bbs/1695.html  heyunyi 2006-10-31 9:57:16

    题目中说的“子序列”是这样定义的:从给定字符序列中随意地(不一定连续)去掉若干字符(也可以一个都不去掉)后形成的字符序列。可见“最长公共子序列”指的是某两个字符串最长的公共子序列。该题中,删除串<1,0,0,1,0,1,0,1>的第2、7个字符得101011,删除串<0,1,0,1,1,0,1,1>的第1、5个字符得101011,可见101011是两串的最长子序列。

    答案为:57 C,58 D

    展开全文
  • 题目描述 小z玩腻了迷宫游戏,于是他找到了Easy,准备...现在小z想请教Easy老师,M字符串有多少个字符串是大字符串S的子序列? 如果Easy老师答不上来就要请客,现在Easy老师很苦恼,你能帮帮他吗? 子序列可以理...

    题目描述

    小z玩腻了迷宫游戏,于是他找到了Easy,准备和Easy玩这么一个游戏

    小Z准备了一个字符串S (S的长度不超过10000)

    又准备了M个小的字符串(M最大不超过1000000,每个小字符串的长度不超过10)

    现在小z想请教Easy老师,M个小字符串中有多少个小字符串是大字符串S的子序列?

    如果Easy老师答不上来就要请客,现在Easy老师很苦恼,你能帮帮他吗?

    子序列可以理解为不要求连续的子串,若还是不了解请看下面的链接中,最佳答案的回答

    https://zhidao.baidu.com/question/120638124.html

    输入

    只有一组测试数据

    第一行是大字符串S(S的长度不超过10000)

    第二行是一个整数M,表示小字符串的个数(M最大不超过1000000)

    接下来M行每行给出一个小字符串(长度不超过10)

    保证没有空字符串

    输出

    输出只有一个整数,代表M个小字符串中是大字符串S的子序列的个数

    样例输入

    amrocegijgyvkgarnffb
    4
    i
    jsj
    qg
    ac

    样例输出

    2
    #include<set>
    #include<map>
    #include<list>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<bitset>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    #define eps (1e-8)
    #define MAX 0x3f3f3f3f
    #define u_max 1844674407370955161
    #define l_max 9223372036854775807
    #define i_max 2147483647
    #define re register
    #define pushup() tree[rt]=max(tree[rt<<1],tree[rt<<1|1])
    #define nth(k,n) nth_element(a,a+k,a+n);  // 将 第K大的放在k位
    #define ko() for(int i=2;i<=n;i++) s=(s+k)%i // 约瑟夫
    #define ok() v.erase(unique(v.begin(),v.end()),v.end()) // 排序,离散化
    using namespace std;
    
    inline int read(){
        char c = getchar(); int x = 0, f = 1;
        while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
        while(c >= '0' & c <= '9') x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
    
    typedef long long ll;
    const double pi = atan(1.)*4.;
    const int M=1e3+5;
    const int N=1e5+5;
    char s[N],s1[100];
    vector<int>vv[27];
    int a[27];
    int main(){
        scanf(" %s",s);
        int len=strlen(s);
        for(int i=0;i<len;i++)
            vv[s[i]-'a'].push_back(i);
        for(int i=0;i<27;i++)
            vv[i].push_back(len);
    
        int n,ans=0;
        scanf("%d",&n);
        while(n--){
            memset(a,0,sizeof(a));
            scanf(" %s",s1);
            int leap=0;
            int len1=strlen(s1);
            int ss=vv[s1[0]-'a'][0];
            if(ss==len)
                continue ;
            a[s1[0]-'a']=1;
            for(int i=1;i<len1;i++){
                int h=lower_bound(vv[s1[i]-'a'].begin()+a[s1[i]-'a'],
                                  vv[s1[i]-'a'].end(),ss)-vv[s1[i]-'a'].begin();
                a[s1[i]-'a']=h+1;
                ss=vv[s1[i]-'a'][h];
                if(ss==len){
                    leap=1;
                    break;
                }
            }
            if(!leap)
                ans++;
        }
        printf("%d\n",ans);
        return 0;
    }

     

    展开全文
  • 获取一个字符串任意长度子序列

    千次阅读 2013-11-28 10:17:14
    #include #include #include using namespace std; /* str: 带解析字符串 iSubLen: 字串的长度 index: 起始位置 ... 函数功能: 求一个字符串任意长度子序列 */ void GetSubStrEx(const string&
    #include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    /*
    		str:	带解析字符串
    	iSubLen:	字串的长度
    	  index:	起始位置
    	iStrLen:	str的长度
    	 strSub:	子串
    		vec:	存储字串
    
       函数功能:	求一个字符串任意长度的子序列
    */
    void GetSubStrEx(const string& str,int iSubLen,int index,int iStrLen,const string& strSub,vector<string>& vec)
    {
    	if(index + iSubLen > iStrLen || iSubLen<=0)		// 这种情况下需退出递归
    	{
    		if(!strSub.empty())
    		{
    			vec.push_back(strSub);			// 此时,index = iStrLen +1,iSubLen=0
    		}		
    		return ;
    	}
    
    	for(int i=index;i<=iStrLen-iSubLen;i++)
    	{
    		char ch = str.at(i);
    		string strNewSub = strSub;
    		strNewSub.append(1,ch);		//从起始位置获得第一个字符
    		
    		// 下一次递归时,子串长度减1,因为刚刚获得了一个字符,同时,起始位置加1,因为刚刚获得了一个字符
    		// 这个位置在下次递归时不可以再获得
    		GetSubStrEx(str,iSubLen-1,i+1,iStrLen,strNewSub,vec);
    	}	
    }
    void GetSubStr(const string& str,int iSubLen,vector<string>& vec)
    {
    	string strSub = "";
    	GetSubStrEx(str,iSubLen,0,str.length(),strSub,vec);
    
    	int iSize = vec.size();
    	for(int i =0;i<iSize;i++)
    	{
    		cout<<vec[i]<<endl;
    	}
    }


    main.cpp

    	vector<string> vec;
    	string str = "ABCDEF";
    	GetSubStr(str,3,vec);


    展开全文
  • 01. #include 02. #include 03. int   main() 04. { 05. char   a[10000]; 06. int   count[10000]; 07. int   i,j,k,m,len,ch;..."%d\n" ,k); 26. }
  • 一个字符串的最长递增子序列长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入描述: 第一行一个整数0&amp;amp;amp;amp;lt;n&amp;amp;amp;amp;lt;20,表示有n字符串要处理 随后的n行,每行有一...
  • N个字符串理论知识:代码实现:测试样例:题目来源(参考)拓展:N个字符环,求最长公共子序列?代码实现:测试样例:题目补充:题目来源:特别说明:转载请注明出处: N个字符串 理论知识: 二进制模拟串实现暴力...
  • 个字符串的最长公共子序列(max common sequence) 九度OJ链接:http://ac.jobdu.com/problem.php?pid=1042 两个字符串的最长公共子序列是指给定两个字符串,找出这两个字符串中相同的字符的
  • 给定两个字符串str1和str2,输出连个字符串的最长公共子序列。 如过最长公共子序列为空,则输出-1。 输入描述 输出包括两行,第行代表字符串str1,第二行代表str2。 (1≤length(str1),length(str2)≤5000) 输出...
  • 输入描述输入一个长度不超过15的字符串,字符串均由小写字母表示输出描述输出其回文子序列个数样例输入abaa样例输出10注释本例中其所有回文子序列:a,b,a,a,aba,aba,aa,aa,aa,aaa 一个字符串子序列是指在原字符...
  • 相信能搜这算法的,一定是对它有所接触了,最长公共子序列(非连续)问题是求两个字符串中公有的字符组成的最长字符串(当然字符的先后顺序不能变); 以南阳36例: 最长公共子序列 时间限制:3000ms | ...
  • 牛牛拿到了一个藏宝图,顺着藏宝图的指示,牛牛发现了一个藏宝盒,藏宝盒上有一个机关,机关每次会显示两个字符串 s 和 t,根据古老的传说,牛牛需要每次都回答 t 是否是 s 的子序列。注意,子序列不要求在原字符串...
  • 给定两个字符串A,B,长度分别m,n。要求求出他们的最长公共子序列,返回其长度,例如 A = “hello word” B = “loop” 最长公共子序列为“loo” 长度为3 思路 动态规划的子问题res[i][j]截止到字符串A的第i...
  • 找两个字符串的最长公共子序列长度 例如 String str1 = “caaac”; String str2 = "bbdaaaca"; 两者最长公共子序列就是aaac 4 代码实现: package offer; public class ...
  • 求两字符串最长公共子序列

    千次阅读 2013-11-08 14:16:30
    第一行代表n串的第一个字符和m比较, 第二行代表n串的第一和第二个字符都和m比较,以此类推。 4. 如果是相同字符,那么就把[m-1][n-1]+1和[m-1[n]和[m][n-1]比较,填入大数。 5. 如此反复填完表,就可以得到...
  • 求解两个字符串的最长公共子序列

    万次阅读 2018-08-20 18:04:13
    则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA   二,算法求解 这是一个动态规划的题目对于可用动态规划求解的问题,一般两个特征:①最优子结构;②重叠子问题 ①最优子结构 设X =(x1,...
  • 2017年校招全国统一模拟笔试(第二场)编程题集合的一道题,求两个字符串的最长公共连续子序列长度题目地址第题下面是c++代码#include #include #include #include #include #include #include #include ...
  •  一个字符串子序列,是指从该字符串中去掉任意多个字符后剩下的字符在不改变顺序的情况下组成的新字符串。这个子序列是可以不连续的。最长公共子序列,是指多个字符串可具有的长度最大的公共的子序列。举个例子,...
  • n个字符串的最长公共子序列

    千次阅读 2012-10-21 15:32:02
    #include #include #include using std::max; const int MAXF = 1000010; const int MAXN = 110;...int n; int base[MAXN], len[MAXN], pos[MAXN]; char ans; char f[MAXF]; char words[MAXN][MAXN]; void solve()
  • 一个串的子串是指该...对两个而言,可以许多的共同的子序列,我们关心的是:它们所共同拥有的长度最大的子序列是多长。以下代码实现了这个问题的求解。请填写划线部分缺失的代码。 注意:只填写划线部分缺少
  • nyoj37回文字符串 最长公共子序列

    千次阅读 2018-04-08 13:10:13
    回文字符串时间限制:3000 ms | 内存限制:65535 KB难度:4描述所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串...
  • 字符串最小字典序子序列

    千次阅读 2019-04-15 20:47:39
    10000)的只有小写字母的字符串,然后找出一个长度为m的最小字典子序列。 做一个预处理,首先26个vector存储每个字母出现位置的下标,O(n)遍历字符串,push进每个字母出现下标,因为是顺序遍历,所以每个vector都是...
  • 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,...
  • 字符串最长公共子序列--动态规划

    千次阅读 2016-10-15 17:51:04
    这两问题是不同的问题,求最长公共子序列不要求求得的子字符串时连续的,比如说ACB和AB的最长公共子序列就是AB。而最长公共连续子串,要求求得的子串在两个字符串中必须是连续出现的,还是ACB和AB他们的最长公共...
  • 个字符串的最长公共子序列

    千次阅读 2013-11-08 10:52:37
    这个问题是最简单的动态规划问题了,只不过是三个字符串而已...举个简单的例子,三个字符串分别abc、cab、c,前两个的最长公共子序列为ab,ab和c的公共子序列为空,实际上他们都有一个字符c,所以这种做法是错误的。
  • 【问题描述】 读入一个字符串str,求出字符串str中连续最长的数字串的长度。 【输入描述】 ...刚刚我们分析过最长递增子序列,其实这一题就是对那一类问题的一个变种,同样也是求一个最长序列的长度,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 108,579
精华内容 43,431
关键字:

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