精华内容
下载资源
问答
  • 最长不重复子序列

    2021-06-01 14:54:05
    2.首先定义快指针i和慢指针j,用于维护一个区间[i,j]此时区间内为q[i]结尾的最长不重复序列。所以我们仅需遍历一遍数组保留res最大值即可 3.对于每一个i,如何求j的位置:首先我们知道[j,i-1]是上一步的最长不重复...

    在这里插入图片描述

    算法思路

    1.双指针算法在此相当于优化,原来的暴力做法的O(n^2)算法穷举所有状态,在发现某性质后仅需枚举O(n)次
    2.首先定义快指针i和慢指针j,用于维护一个区间[i,j]此时区间内为q[i]结尾的最长不重复序列。所以我们仅需遍历一遍数组保留res最大值即可
    3.对于每一个i,如何求j的位置:首先我们知道[j,i-1]是上一步的最长不重复序列,那么此时j不可能向左移动,否则与上一步矛盾,所以j只能右移动,这也就是j的单调性所在,我们可以用双指针优化的原因。
    4.j向右移动什么时候停下,即满足check的条件:首先我们知道对于上一步[j,i-1]的最长不重复序列,只有q[i]与区间内元素重复时j才需要右移,设置s[q[i]]记录元素出现次数即可。

    #include <iostream>
    
    using namespace std;
    
    int n;
    
    const int N = 100010;
    
    int q[N],s[N];
    
    int main()
    {
        scanf("%d",&n);
        for(int i  = 0; i<n;i++)
            scanf("%d",&q[i]);
            
        int res = 0;
        //定义快慢指针i和j,用于维护最长不重复区间[j,i]
        for(int i=0,j = 0;i<n;i++)
        {
            s[q[i]] ++;//记录元素出现的次数
            
            //区间内出现重复元素s[q[i]]
            while(s[q[i]]>1)
            {
                s[q[j]] --;
                j++;
            }
            
            res = max(res,i-j+1);
        }
        
        cout << res <<endl;
        
        return 0;
    }
    
    展开全文
  • 最长不重复子序列Description: 描述: This question has been featured in interview rounds of Amazon. 这个问题已在亚马逊的采访回合中提到。 Problem statement: 问题陈述: Given string str, find the ...

    最长不重复子序列

    Description:

    描述:

    This question has been featured in interview rounds of Amazon.

    这个问题已在亚马逊的采访回合中提到。

    Problem statement:

    问题陈述:

    Given string str, find the length of the longest repeating subsequence such that the two subsequences don't have the same character in the same position, i.e., any ith character in the two sub-sequences shouldn't have the same index in its original string.

    给定字符串str ,求出最长重复子序列的长度,以使两个子序列在相同位置没有相同的字符,即,两个子序列中的任何 i 字符在其位置均不应具有相同的索引原始字符串。

        Let the string be,
        Str="includehelpisbest"
        
        Output will be:
        Longest repeating sub-sequence length is 3
        The longest repeating sub-sequence is:"ies"
    
    
    Longest Repeating Subsequence

    The output is given above where the repeating sub-sequences are in two different colours. One more repeating subs-sequence can be,

    上面给出了输出,其中重复子序列使用两种不同的颜色。 可以再重复一个子序列,

    Longest Repeating Subsequence

    Solution Approach:

    解决方法:

    The problem can be solved in similar way as longest Common subsequence problem, where input to LCS() would be String str both the case. That is

    可以通过与最长公共子序列问题类似的方法来解决该问题 ,在这两种情况下, LCS()的输入均为String。 那是

        LRS(str) = LCS(str,str) which some constraints
    
    

    Let's discuss the recursive approach first.

    让我们首先讨论递归方法。

    Let,

    让,

        
        l = Length of the  string,str
        f(l,l) = Longest repeating subsequence length for string length l
    
    

    Now,

    现在,

    Think of the following example,

    考虑以下示例,

    Say the string is: x1x2...xl

    假设字符串是: x 1 x 2 ... x l

    Say,

    说,

    xi==xj and i≠j (this is the constraint what we discussed above)

    x i == x ji≠j (这是我们上面讨论的约束)

    Then obviously we need to find LCS for the remaining part of string (x1x2...xi-1, x1x2...xj-1) and then add 1 for this valid character match (repeating character match),

    那么显然我们需要为字符串的其余部分(x 1 x 2 ... x i-1 ,x 1 x 2 ... x j-1 )找到LCS,然后为这个有效的字符匹配添加1(重复字符比赛),

    Else

    其他

    Maximum of two case,

    最多两种情况

    1. LCS of the string leaving character xi,x1x2...xi-1 and string x1x2...xj.

      字符串x i ,x 1 x 2 ... x i-1和字符串x 1 x 2 ... x j的 LCS。

    2. LCS of the string xl1, x1x2...xi and second string leaving character xj,x1x2...xj-1

      字符串x l 1 ,x 1 x 2 ... x i的 LCS和第二个字符串剩下的字符x j ,x 1 x 2 ... x j-1

    Now, we need to recur down to 0. So,

    现在,我们需要递归降至0。因此,

    Longest Repeating Subsequence

    Where base cases are,

    在基本情况下,

        f(0,i)=0 for 0≤i≤l
        f(i,0)=0 for 0≤i≤ l
    
    

    If you generate this recursion tree, it will generate many overlapping sub-problems and thus, we need to reduce the re-computing. That's why we need to convert it into dynamic programming where we will store the output of the sub-problems and we will use it to compute bigger sub-problems.

    如果生成此递归树,它将生成许多重叠的子问题,因此,我们需要减少重新计算。 这就是为什么我们需要将其转换为动态编程,以便在其中存储子问题的输出,并使用它来计算更大的子问题。

    Converting to Dynamic programming:

    转换为动态编程:

        1)  Initialize dp[l+1][l+1]  to 0
        2)  Convert the base case of recursion:
            for i=0 to l
                dp[i][0]=0;
            for i=0 to l
                dp[0][i]=0;
    
        3)  Fill the DP table as per recursion.
            for i=1 to l    //i be the subproblem length for first string of LCS
                for j=1 to l //j be the subproblem length for second string of LCS
                    if(i≠j and str1[i-1]==str2[j-1]) //xi==xj  and i≠j
                        dp[i][j]=dp[i-1][j-1]+1;
                    else
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                end for
            end for  
        4)  The final output will be dp[l][l]
    
    

    C++ Implementation:

    C ++实现:

    #include <bits/stdc++.h>
    using namespace std;
    
    void print(vector<int> a, int n)
    {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    
    int max(int a, int b)
    {
        return (a > b) ? a : b;
    }
    
    int LRS(string str1, string str2)
    {
        int l = str1.length();
        int dp[l + 1][l + 1];
    
        //base case
        for (int i = 0; i <= l; i++)
            dp[i][0] = 0;
    	
        for (int i = 0; i <= l; i++)
            dp[0][i] = 0;
    	
        //fill up
        for (int i = 1; i <= l; i++) {
            for (int j = 1; j <= l; j++) {
                if (i != j && str1[i - 1] == str2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    
        return dp[l][l];
    }
    
    int main()
    {
        string str;
    
        cout << "Enter the string:\n";
        cin >> str;
        cout << "Longest repeating sub-sequence length: " << LRS(str, str) << endl;
    
        return 0;
    }
    
    

    Output

    输出量

    Enter the string:
    includehelpisbest
    Longest repeating sub-sequence length: 3
    
    
    

    翻译自: https://www.includehelp.com/icp/longest-repeating-subsequence.aspx

    最长不重复子序列

    展开全文
  • HDU 2668 Daydream(最长不重复子序列

    千次阅读 2016-05-06 09:23:39
    尺取法,最长不重复子序列

    题目描述:
    Daydream
    Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

    Description
    Welcome to 2009 HDU Girl’s Cup, bless you will happy in it.
    Every girl are beautiful if you use you heart to feel. Every corner in the world will colourful and energetic by several girls standing. If you boy, a normal bay, I believe that you will try to watch when a beautiful girl passing you and you will nervous if a girl watching you just when you are watching her.

    Now give you a surprise that may be never happy in the real time. Millions of PLMM stand in a line and facing you(^_^). They are dress colourful clothings. You should to find out a maximal subline PLMM that their clothing color are all different.

    Input
    The input contains multiple test cases.
    Each case first give a integer n expressing many many girls stand in line.(n<=10000000)
    Next line a string including n character, each character standing one girls’s clothing color.

    Output
    Output one integer the numbers of maximal subline PLMM that their clothing color are all different and the line’s begin and end (based from 0). If their are more answer, print the begin smallest.

    Sample Input

    3
    abc
    5
    aaaba
    8
    hdugirls

    Sample Output

    3 0 2
    2 2 3
    8 0 7

    题目大意:
    就是问你给定的序列中最长的连续的不重复的子序列的长度,以及起始位置,如果有多处,输出最前面的一组

    题目分析:
    首先看数据规模,10^7,至少要搞到o(n)的时间复杂度,先说明一点,题目说的是字符,但是并没有说是小写字母,尽管样例都是小写,所以数组开大点,150或者300都行,接下来说思路,感觉思路就是尺取法,两个指针,一个定在开始,另外一个开始往前扫,把出现的字母的位置存在刚才开的数组里,直到出现重复为止(数组的这个位置已经放过字符)那么这时候就把当前扫描的序列的长度以及起始位置跟原来比较一下,留下长的序列,然后把后面的指针挪到重复的字符的位置的下一个字符。值得注意的一点是,我们并不需要每次在扫描最长的序列之前都对数组进行一次重新赋值,只需要看重复的字符是不是在当前尾指针的右侧(左侧的话跟当前扫描没关系)

    代码:

    #include "cstdio"
    #include "cstring"
    int pos[150];
    int main()
    {
        int n,i,l,r,ltmp,cnt,cnttmp;
        char ch;
        while(scanf("%d",&n)!=EOF)
        {
            getchar();
            ch=getchar();
            cnt=ltmp=0;
            cnttmp=1;
            memset(pos,-1,sizeof(pos));
            pos[ch]=0;
            for(i=1;i<n;i++)
            {
                ch=getchar();
                //出现重复
                if(pos[ch]>=0&&pos[ch]>=ltmp){
                    if(cnttmp>cnt){
                        cnt=cnttmp;
                        l=ltmp;
                        r=i-1;
                    }
                    cnttmp-=pos[ch]-ltmp;
                    ltmp=pos[ch]+1;
                }else{
                    cnttmp++;
                }
                //不管重不重,都把最新出现的位置放过来
            //因为只有新位置才会影响以后,旧位置的话一定在尾指针之前,没用了
                pos[ch]=i;
            }
            if(cnttmp>cnt){
                cnt=cnttmp;
                l=ltmp;
                r=i-1;
            }
            printf("%d %d %d\n",cnt,l,r);
        }
        return 0;
    }
    展开全文
  • 题意:求解最长不重复子序列的长度 #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;string&gt; #include&lt;cstring&gt; #...

    题目链接:http://acm.zzuli.edu.cn/problem.php?id=2472 

    题意:求解最长不重复子序列的长度

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<queue>
    #include<cmath>
    #include<set>
    #include<map>
    #include<stack>
    #include<sstream>
    using namespace std;
    #define ll long long
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    
    const int INF=0x3f3f3f3f,mod=12345;
    const int N=100005;
    int a[N],dp[N];
    int t,n;
    void solve(){
        int last_start=0;//上次最长子串的起始位置
        int maxlen=0;
        dp[0]=1;//dp[i]:=从i位置向0坐标走,最长不重复子序的长度
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=last_start;--j){//遍历到上一个子串的起始位置
                if(a[j]==a[i]){
                    dp[i]=i-j;
                    last_start=j+1;
                    break;
                }
                else if(j==last_start){//无重复
                    dp[i]=dp[i-1]+1;
                }
            }
            if(dp[i]>maxlen){
                maxlen=dp[i];
            }
        }
        if(maxlen==0)maxlen=1;
        printf("%d\n",maxlen);
    }
    
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            memset(dp,0,sizeof(dp));
            for(int i=0;i<n;i++)scanf("%d",&a[i]);
            solve();
        }
    }
    /*
    10
    10
    1 2 3 3 2 4 5 6 7 10
    */

    参考博客:https://dsqiu.iteye.com/blog/1701324

    展开全文
  • 子串与子序列 子串(substring)——在字符串中是连续的 子序列(subsequence)——在字符串中可以连续,也可以连续
  • 给定一个长度为n的整数序列,请找出最长包含重复的数的连续区间,输出它的长度。 输入格式 第一行包含整数n。 第二行包含n个整数(均在0~100000范围内),表示整数序列。 输出格式 共一行,包含一个整数,...
  • 也很简单,但是hash表在此题中的应用可以称得上是十分巧妙,直接从O(n^2)降到O(n),hashtable在记录重复元素、更新重复元素方面作用比较大,以后可以多多注意这方面,不要再用queue或者deque这种高度动脑的表达了...
  • //微软编程一小时 第二题 求解最长重复子序列 #include "iostream" #include "string" using namespace std; #define MAXLEN 10000 char a[MAXLEN],*suff[MAXLEN]; int comlen(char* p,char* q) {...
  • 这题主要就是求最长不重复子序列,最容易想到的方法就是暴力,把所有子序列遍历一遍,找到所有不重复的子序列然后选择最长的那个.但是为了对子序列进行遍历此方法时间复杂度为O(n^2),而需要一个数组来存储字母是否出现,...
  • 从下标0开始,依次查找以当前下标开始的最长不重复子序列。 举例说明: C++代码实现: int GetMaxLength( string & sTemp, int startIndex) { map < char , int > mapChar; int max = 0 ; for...
  • 题目来源:... Given a string, find the length of the longest substring without repeating characters. For example, the longest subs...
  • 寻找最长不重复子序列:一万+长度 思路:碰到一个元素(a[i])后,往回找,有无重复元素: 若有:假设在第 j 位,则起始端更新为 j + 1,从第 j + 1 再开始找 若前面没有相同的元素,则将第 i 位元素纳入子序列中,...
  • 最长重复子序列 https://leetcode-cn.com/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或删除)数组中的元素而...
  • 遍历数组a中的每一个元素a[i], 对于每一个i,找到j使得双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列,长度为i - j + 1, 将这一长度与result的较大者更新给result。 对于每一个i,如何确定j的位置:...
  • 最长重复子序列

    2020-01-06 09:25:40
    给定一个字符串,请你找出其中含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为...
  • 双指针 双指针严格来讲,算不上不一种...最长连续不重复子序列 最长连续不重复子序列 思路 朴素思路——双重循环 存在性质:一个不重复序列的子序列也一定是不重复序列 因此,只需要对数组遍历作为右端点,如出...
  • 最长连续不重复子序列的问题 应用: 1.求最长连续不重复子序列的长度。 2.求最大连续不重复子序列的和。 方法:双指针法。 用一个数组b[]b[]b[]储存每个数出现的次数,如果数据范围较大或者存在负数,则可以用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,129
精华内容 451
关键字:

最长不重复子序列