首页 > 试题广场 >

Array

[编程题]Array

热度指数：1045 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小红有两个长度为n的排列A和B。每个排列由[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

输出

说明

最长的C为1,3,4,5

算法知识视频讲解

Python

月亮上的熊猫

python动态规划之抱头痛哭...

上面的图是我的二维dp，超内存。

思路：把b逆序，求a和b的最长公共子序列，转化为经典动规。

下面的图是[小二郎求offer]的一维dp，超时。

思路：tmp存储a和b的关系，即b的元素在a中的位置。

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

牛客2817416号

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)

_sola_

#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)

Java

秋風掃落葉

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)

绵绵sir

# 不会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)

/*思路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)

Java

言笑723

import java.util.*;
class Main {
    // public static int first(int[] a,int[] b){

    //     int[][] dp  =new int[a.length+1][a.length+1];
    //     for(int i=1;i<=a.length;i++){
    //         for(int j=1;j<=a.length;j++){
    //             if(a[i-1]==b[j-1])
    //             dp[i][j]  =dp[i-1][j-1]+1;
    //             else
    //                 dp[i][j] =Math.max(dp[i-1][j],dp[i][j-1]);
    //         }
    //         }
    //         return dp[a.length][a.length];
    //     }



    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int[] arr1  = new int[num];
        int[] arr2  = new int[num];
        int[] map = new int[num + 1];
        int[] need = new int[num];
        for (int i = 0; i < num; i++) {
            arr1[i] = in.nextInt();
            map[arr1[i]] = i;
        }
        for (int i = 0; i < num; i++) {
            arr2[i] = in.nextInt();
            need[i] = map[arr2[i]];
        }
        // System.out.println(Arrays.toString(need));
        List<Integer> dp = new ArrayList<>();

        dp.add(need[0]);
        
        for (int i = 1; i < num; i++) {
            if (need[i] < dp.get(dp.size() - 1))dp.add(need[i]);
            else {
                int bound  = Collections.
                             binarySearch(dp, need[i], (a, b)->b - a);
                //System.out.println(-bound-1);
                int index = -bound - 1;
                dp.set(index,need[i]);
            }

        }









        System.out.println(dp.size());



    }
}

发表于 2023-11-05 15:24:29 回复(0)

Java

_000110hwc

第一次做的时候，我创建dp数组是(n+1)*(n+1)的，通过率是40%，说我有数组越界访问，但我反复琢磨也没发现哪里越界了。

然后我发现，当n比较大时，dp数组占的空间太大了，大概就是这里"越界"了。于是我把dp数组改成2*(n+1)的，每完成一次内循环就进行一次更替。这一改，通过率变成了50%，这次的问题是运行超时了。

但是，复杂度没法降了。

java代码如下：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scn=new Scanner(System.in);
        while(scn.hasNextInt()){
            int n=scn.nextInt();
            int[] a=new int[n];
            int[] b=new int[n];
            for(int i=0;i<n;i++) a[i]=scn.nextInt();
            for(int i=0;i<n;i++) b[n-1-i]=scn.nextInt();
            int[][] dp=new int[2][n+1];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dp[1][j]=a[i-1]==b[j-1]?dp[0][j-1]+1:Math.max(dp[0][j],dp[1][j-1]);
                }
                int[] temp=dp[0];
                dp[0]=dp[1];
                dp[1]=temp;
            }
            System.out.println(dp[0][n]);
            break;
        }
    }
}

发表于 2020-06-30 23:25:25 回复(0)

牛客279810500号

最长递减子序列，时间复杂度O（nlogn）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>m;
    vector<int>b(n);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        m[x]=i;
    }
    for(int i=0;i<n;i++)
    {
        int y;
        cin>>y;
        b[i]=m[y];
    }
    
    vector<int>dp;
    dp.push_back(b[0]);
    for(int i=1;i<n;i++)
    {
        if(b[i]<dp.back())dp.push_back(b[i]);
        else{
            int pos=lower_bound(dp.begin(),dp.end(),b[i],greater<int>())-dp.begin();
            dp[pos]=b[i];
        }
    }
    cout<<dp.size()<<endl;
    return 0;
}

编辑于 2020-06-24 09:45:51 回复(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)