首页 > 试题广场 > Array
[编程题]Array
  • 热度指数:738 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

小红有两个长度为n的排列AB。每个排列由[1,n]数组成,且里面的数字都是不同的。

现在要找到一个新的序列C,要求这个新序列中任意两个位置(i,j)满足:

如果在A数组中C[i]这个数在C[j]的后面,那么在B数组中需要C[i]这个数在C[j]的前面。

请问C序列的长度最长为多少呢?


输入描述:
第一行一个整数,表示N。

第二行N个整数,表示A序列。

第三行N个整数,表示B序列。

满足:N<=50000


输出描述:
输出最大的长度
示例1

输入

5
1 2 4 3 5
5 2 3 4 1

输出

4

说明

最长的C为1,3,4,5
/*思路1 将B[1,n]翻转,则问题转化O(n^2)的最长公共子序列问题,注意dp数组优化为O(n)复
杂度的,不然会爆内存只有40%通过,优化后也只能通过50%*/
/*思路2:可以看出来O(n^2)的时间复杂度不是出题想要的,可以用Map<值 , 位置>将A数组
中值与位置对应,如
样例中
5
1 2 4 3 5
5 2 3 4 1
A数组可以用Map对应出:[1,0] [2,1] [4,2] [3,3] [5,4];
则B数组中值可以通过Map映射为对应值在A中位置即B数组从[5 2 3 4 1];映射为
B'=[ 4 1 3 2 0 ];
由题目要求C中任意数i,j 存在 如果在A数组中C[i]这个数在C[j]的后面,
那么在B数组中需要C[i]这个数在C[j]的前面的关系,
则问题就转换为了在B'中查找最长递减子序列问题-->时间复杂度下降变为O(nlogn);
*/
//思路1
import java.util.*;

public class Main
{
    public static void main(String []args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        if(n<=0)
        {
            System.out.println( 0 );
            return;
        }
        
        int[] an = new int[n];
        int[] bn = new int[n];
        
        
        for(  int i = 0 ; i < n ; i++  )
        {
            an[i] = sc.nextInt();
        }
        for(  int i = n-1 ; i >-1 ; i--  )
        {
            bn[i] = sc.nextInt();
        }
		
        System.out.println(md( an , bn ,n));
    }
    
    public static int md(  int[] an , int[] bn , int n  )
    {
        if(n==1)return an[0]==bn[0]?1:0;
        
        
        int[] res = new int[n];
        
        for( int i = 0 ; i < n ; i++ )
            for(int j = 0 ; j<n ; j++)
            {
                if( i == 0 )
                {
                    if( j==0 )
                    {
                        res[0] = an[0]==bn[0]?1:0;
                    }else{
                        res[j] = an[i]==bn[j]?1:res[j-1];
                    }
                    
                }else if(j == 0 )
                {
                    res[j] =  res[j]==1?1:( an[i]==bn[j]?1:0  );
                }else{
                    if( an[i] == bn[j] )
                    {
                        res[j] = res[j-1]+1;
                    }else{
                        res[j] = Math.max( res[j] ,res[j-1] );
                    }
                }           
            }
        return res[n-1];
    }
}

//思路2
import java.util.*;

public class Main
{
    public static void main(String []args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] b = new int[n];
        HashMap<Integer , Integer> hs  = new HashMap<>();
        for(int i = 0 ; i < n ; i++)
        {
            hs.put( sc.nextInt() , i   );
        }
        for(int i = 0 ; i < n ; i++)
        {
            b[i] = (Integer) hs.get( sc.nextInt() );  
        }
        System.out.println(  md( b , n )  );
        
    }
    
    public static int md( int[] an , int n)
    {
        if(n<2)return 1;
        if(n==2)return an[0]>an[1]?2:1;
        
        int r = 0 ;
        int[] end = new int[n];
        end[r] = an[r];
        
        for( int i =1 ; i < n ; i++)
        {
            if( an[i] < end[r]  )
            {
                r++;
                end[r] = an[i];
            }else{
                cmp( end , r , an[i]   );
            }
        }
        return r+1;
        
    }
    
    public static void cmp( int[] cmp , int r , int target )
    {
        if( cmp[0]<target )
        {
             cmp[0] = target;
             return;
        }
        if(  r==1 )
        {
            cmp[0] =  ( cmp[0]>target?cmp[0]:target  );
        }
        int l = 0 ;
        int m ;
        while(  r-1 > l  )
        {
            m = (l+r)/2;
            if( cmp[m] > target )
            {
                l = m ;
            }else{
                r = m;
            }
        }
        cmp[r] = target;
        
    }
    

}





发表于 2019-08-28 15:26:57 回复(0)
python动态规划之抱头痛哭...
上面的图是我的二维dp,超内存。
思路:把b逆序,求a和b的最长公共子序列,转化为经典动规。
下面的图是[小二郎求offer]的一维dp,超时。
思路:tmp存储a和b的关系,即b的元素在a中的位置。


编辑于 2019-08-20 16:42:17 回复(0)

Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

tmp = []
for i in range(n):
    tmp.append(a.index(b[i]))
dp = [1] * (n)
for i in range(1,n):
    for j in range(i):
        if tmp[i]<tmp[j]:
            dp[i] = max(dp[j]+1, dp[i])
print(max(dp))


发表于 2019-08-19 10:01:39 回复(8)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

map<int ,int> mp;

struct node{
    int num;
    int rank;
}arr[50007];
int in[50007];

int main() {
    int n, num;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d", &arr[i].num);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        mp[num] = i + 1;
    }
    for (int i = 0; i < n; ++i) arr[i].rank = - mp[arr[i].num];

    in[0] = arr[0].rank;
    int len = 1;
    for (int i = 1; i < n; ++i) {
        int adr = lower_bound(in, in + len, arr[i].rank) - in;
        if (len == adr) in[len ++] = arr[i].rank;
        else in[adr] = arr[i].rank;
    }
    printf("%d\n", len);
    return 0;
}

思路:你仔细看看、想想就会知道其实这是一个最长下降子序列。我已开始就是想着吧最左边的1挪到最右边,那么肯定是满足条件的了,但是这样依赖,挪到右边之后的位置的右边假设还有数,那么这些数就废了,那么问题就是怎么挪哪些数到右边的时候尽量保证废了的数字尽量的少,那么你就按照下面的顺序给上面的数赋值顺序,你就会发现变成了最长下降子序列...

you see you see one day day的

发表于 2019-08-03 01:03:01 回复(3)
import java.util.*;
 
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer,Integer> hs = new HashMap<>();
        int[] index = new int[n];
        for(int i = 0;i < n;i++){
            hs.put(sc.nextInt(),i);
        }
        // 通过序列值映射下标
        for(int i = 0;i < n;i++){
            index[i] = (int)hs.get(sc.nextInt());
        }
        
        System.out.println(getSequence(index, n));
    }
    
    // 查找存储下标的数组最长降序子序列长度
    public static int getSequence(int[] arr, int num){
        // 考虑边界情况
        if(num == 2)
            return arr[0] > arr[1]?2:1;
        else if(num == 1)
            return 1;
        
        // 新建一个数组存储降序子序列
        int r = 0;// 记录des数组的下标位置
        int[] des = new int[num];
        des[r] = arr[r];
        for(int i = 1;i < num;i++){
            if(arr[i] < des[r]){
                des[++r] = arr[i];
            }else{
                // r到达某一位置时,不是降序的
                branching(des, r, arr[i]);
            }
        }
        return r + 1;
    }
    
    // 对子序列进行分支
    public static void branching(int[] des, int r, int curr){
        // 边界条件
        if(des[0] < curr){
            des[0]= curr;
            return;
        }
        if(r == 1){
            des[0] = des[0] > curr ? des[0] : curr;
            //return;// 不需要return
        }
        
        // 分支策略
        int l = 0;
        int m = 0;
        while(r - 1 > l){
            m = (r + l) / 2;
            if(des[m] > curr)
                l = m;
            else
                r = m;
        }
        des[r] = curr;
    }
}

发表于 2019-09-05 10:30:40 回复(0)
# 不会dp的先去看dp思想,不然下面看不懂,了解一下为什么这个题是在求最长递减子序列
dp需要O(n*n)的复杂度,明显这里通不过
需要一个更低的O(n*logn)的复杂度
dp的不足在于每次添加一个新的数,都需要和所有数比较找到最大的
考虑有序数组的二分查找的复杂度可能会是我们需要的
建立一个数组来储存我们当前找到的 “容量是最大的” 最长递减序列

首先来理解一下什么是 “最大的容量”
①考虑两个递减序列 a与b
list = ... ... ... 12  7  6  ...  ... 2 ... ... 4 ... ... 
a =  12  7  6  4 ... ... ...
b =  12  7  6  2 ... ... ...
这两个序列都是长度为4
但是我们发现a的最后一个数比b的最后一个数要大
也就是说a这个序列在将来也许可以容纳下更多的递减值
比如我们后面发现了一个数为3
list = ... ... ... 12  7  6  ...  ... 2 ... ... 4 ... ... 3 ... ...
显然我们就会抛弃b而选择a

在不了解未来的发展下,作为一名先♂知
于是比起储存b我们更偏向于优先去存储a,因为它的容量比较大

②考虑另外一种情况:
list = ... ... ... 12  7  6  ... ... 4 ... ...  11(new number) ... ...
a = 12  7  6  4

我们发现了一个 11 它比我们的a的最后一个值要大

假如往后list 的发展是这样的:
list = ... ... ... 12  7  6  ... ... 4 ... ...  11(new) ... ... 10  9  8 ...  ...
我们发现 (12  11  10  9  8) 这个序列的长度比我们的a更大
所以当我们发现 11 的时候,必须要考虑把它给存起来

我们把原来 a 中放7的位置腾出来,送给11,于是 a = 12  11  6  4   -> 保证a还是有序的
我们遇见11的时候最长子序列的长度 (12  7  6  4) 仍然是4,而a的长度也是4,它们相等的

类推:当我们遇见10的时候,10大于4,把6让给10:  a = 12  11  10  4   ->a有序
此时list中最长子序列 (12  7  6  4)   与a长度相等

遇见9:a = 12  11  10  9
最长子序列此时有两个(12  7  6  4) 与 (12  11  10  9)

当我们遇见8的时候:8小于a的最后一个数,于是把8加入a,a的长度突破了4
此时list最长子序列应该更新为a =  (12  11  10  9  8) 达到了我们的目的
再回头考虑一下我们 第①中情况:
list = ... ... ... 12  7  6  ...  ... 2 ... ... 4 ... ... 
在遇见 4 之前,我们之前存储的最长子序列一直就是  (12  7  6  2)没错
但当我们遇见了4的时候,4比2的值要大,所以我们就把这个子序列从
(12  7  6   2) 更新成为了(12  7  6  4)
目的就是保持我们的 “最大容量” 的原则

这个更新排序序列的过程,由于是有序的,我们可以用到二分法,降低复杂度
最后附上我的Python3代码

import sys
import bisect
n = int(sys.stdin.readline().strip())
dic = {}
for index, num in enumerate(list(map(int, sys.stdin.readline().split()))):
    dic[num] = index

my_list = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    my_list[i] = dic[my_list[i]]

if __name__ == '__main__':
    tmp = [my_list[0]]
    res = 1
    for i in range(1, n):
        if my_list[i] < tmp[0]:
            tmp.insert(0, my_list[i])
            res += 1
        else:
            tmp[bisect.bisect(tmp, my_list[i])-1] = my_list[i]
    print(res)

感谢你能看到最后
发表于 2019-08-31 21:01:21 回复(0)
java代码思路:将数组A翻转然后动态规划,求A和B的最长公共子序列  不过AC只有40%难道这题不能用二维数组啊?.....难受.jpg
import java.util.*;

public class Main {
//   动态规划,最长公共子序列
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N+1];
		int[] B = new int[N+1];
		int[][] dp = new int[N+1][N+1];
//		读取数据
		for(int i=N;i>0;i--) {
			A[i]= sc.nextInt(); 
		}
		for(int i=1;i<=N;i++) {
			B[i]= sc.nextInt(); 
		}
//		格式化二维数组
		for(int i=0;i<=N;i++) {
			for(int j=0;j<=N;j++) {
				dp[i][j]=0;
			}
		}
//		判断最长的公共子序列
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(A[i]==B[j]) {
					dp[i][j]= Math.max(dp[i-1][j], dp[i][j-1])+1; 
				}else {
					dp[i][j]= Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		
////		输出dp看看---调试用
//		for(int i=0;i<=N;i++) {
//			for(int j=0;j<=N;j++) {
//				System.out.print(dp[i][j]+"  ");
//			}
//			System.out.println();
//		}
		System.out.println(dp[N][N]);
	}

}


发表于 2019-08-24 17:39:36 回复(0)
N = int(input())
list1 = list(map(int,input().split()))
list2 = list(map(int,input().split()))
 
list3 = [list1.index(i) for i in list2]
#list3.reverse()
dp = [0 for i in range(N)]
size = 0
for x in list3:
    i,j = 0,size
    while i != j:
        m = (i+j)//2
        if dp[m] > x:
            i = m + 1
        else:
            j = m
    dp[i] = x
    size = max(size,i+1)
print(size)
python貌似最多通过百分之50,时间复杂度nlogn。就是最长递减子序列问题
发表于 2019-08-15 13:57:35 回复(1)
这题妙啊、
发表于 2019-08-12 20:44:11 回复(1)