首页 > 试题广场 >

两个序列

[编程题]两个序列

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

小强有两个序列 $\mathit a$ 和 $\mathit b$ ，这两个序列都是由相同的无重复数字集合组成的，现在小强想把 $\mathit a$ 序列变成 $\mathit b$ 序列，他只能进行以下的操作：
从序列 $\mathit a$ 中选择第一个或者最后一个数字并把它插入 $\mathit a$ 中的任意位置。
问小强至少需要几次操作可以将序列 $\mathit a$ 变为序列 $\mathit b$ 。

输入描述:

一行一个整数表示序列的长度。
接下来两行每行个整数。
第一行表示序列，第二行表示序列。



保证给出的序列符合题意。

输出描述:

输出一行一个整数表示答案。

示例1

输入

4
4 2 3 1
1 2 3 4

输出

算法知识视频讲解

Java

牛客837169005号

补个 Java 版本的

import java.util.*;
public class Main {
    /*
    更改题目   a=[D,B,C,A]; b=[A,B,C,D]
    对 b 做映射  A->0; B->1; C->2; D->3
    那么对应的 a 可根据映射规则更改为 a'=[3,1,2,0]
    之后对 a' 做最长连续上升子数组即可
    */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i ++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i ++) {
            b[i] = sc.nextInt();
        }
        // 对 A 里面的数进行重新映射
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            map.put(b[i], i);
        }
        // 利用映射规则对 B 进行更新映射
        for (int i = 0; i < n; i ++) {
            a[i] = map.get(a[i]);
        }
        // 对更改之后的 b 做最长连续上升子序列
        int res = 0;
        int cur = 1;
        for (int i = 1; i < n; i ++) {
            if (a[i]>a[i-1]) {
                cur += 1;
                res = Math.max(res, cur);
            } else {
                cur = 1;
            }
        }
        System.out.println(n - res);
    }
}

发表于 2021-08-01 11:39:38 回复(0)