Array

[编程题]Array

热度指数：1064 时间限制：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

算法知识视频讲解

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)

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)