美团3.25笔试记录-第一题

2023-05-16

第一题：

题目描述：

小美是一个火车迷。最近她在观察家附近火车站的火车驶入和驶出情况，发现火车驶入和驶出的顺序并不一致。经过小美调查发现，原来这个火车站里面有一个类似于栈的结构，如下图所示：例如可能1号火车驶入了火车站中的休息区s，在驶出之前2号火车驶入了。那么在这种情况下，1号火车需要等待2号火车倒车出去后才能出去（显然被后面驶入的2号火车挡住了，这个休息区s只有一个出入口）。出于好奇，小美统计了近些天的火车驶入驶出情况，开始统计和结束统计时休息区s中均是空的。由于中途疏忽，小美觉得自己好像弄错了几个驶入驶出顺序，想请你帮她验证一下。值得注意的是，小美虽然可能弄错了顺序，但对火车的记录是不重不漏的。形式化地来形容休息区s，我们视其为一个容量无限大的空间，假设两列火车 i 和 j 同时处于休息区s中，驶入时刻Tin满足Tin(i)<Tin(j)，则驶出时间Tout必定满足Tout(i)>Tout(j)，即，先进后出。

输入描述

第一行一个整数T表示数据组数。

对每组测试而言：
第一行一个整数n，表示观察到的火车数量。
第二行n个整数x1,x2,…,xn，表示小美记录的火车驶入休息区s的顺序。
第三行n个整数y1,y2,…,yn，表示小美记录的火车驶出休息区s的顺序。
1≤T≤10,1≤n≤50000,1≤xi,yi≤n, 且{xn} 、{yn} 均为{1,2,3,…,n}的一个排列，即1~n这n个数在其中不重不漏恰好出现一次。

输出描述

对每组数据输出一行：如果小美记录的驶入和驶出顺序无法被满足则输出No，否则输出Yes。

样例输入

样例输出

Yes
Yes
No

题解

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * 第一题
 */
public class Test01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();//表示数据组数int
        String[] res = new String[T];
        for(int i = 0; i < T; i++){
            int n = sc.nextInt();//表示观察到的火车数量
            int[] pushed = new int[n];//火车入栈数组
            int[] popped = new int[n];//火车出栈数组
            for(int j = 0; j < n; j++){
                pushed[j] = sc.nextInt();
            }
            for(int k = 0; k < n; k++){
                popped[k] = sc.nextInt();
            }
            res[i] = judge(pushed, popped);
        }
        for(String s: res){
            System.out.println(s);
        }
    }

    public static String judge(int[] pushed,int[] popped){
        Deque<Integer> stack = new ArrayDeque<>();
        int n = pushed.length;
        for(int i = 0,j = 0;i < n;i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty() ? "Yes" : "No";
    }
}

思路

judge()方法是判断小美记录的火车驶出顺序是否满足出栈的顺序，与剑指 Offer 31. 栈的压入、弹出序列题目一致。

注：

1. 那么为什么我们不直接选择Stack，而是用Deque？

有两个主要原因：

从性能上来说应该使用Deque代替Stack。
Stack和Vector都是线程安全的，其实多数情况下并不需要做到线程安全，因此没有必要使用Stack。毕竟保证线程安全需要上锁，有额外的系统开销。
Stack从Vector继承是个历史遗留问题，JDK官方已建议优先使用Deque的实现类来代替Stack。
Stack从Vector继承的一个副作用是，暴露了set/get方法，可以进行随机位置的访问，这与Stack只能从尾巴上进行增减的本意相悖。

此外，Deque在转成ArrayList或者stream的时候保持了“后进先出”的语义，而Stack因为是从Vector继承，没有这个语义。

Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new ArrayDeque<>();

stack.push(1);
stack.push(2);
deque.push(1);
deque.push(2);

System.out.println(new ArrayList<>(stack)); // [1,2]
List<Integer> list1 = stack.stream().collect(Collectors.toList());//[1,2]

// deque转成ArrayList或stream时保留了“后进先出”的语义
System.out.println(new ArrayList<>(deque)); // [2,1]
List<Integer> list2 = deque.stream().collect(Collectors.toList());//[2,1]

2. 那么我们应该使用ArrayDeque还是LinkedList 来new出对象？

ArrayDeque和LinkedList这两者底层，一个采用数组存储，一个采用链表存储；

数组存储，容量不够时需要扩容和数组拷贝，通常容量不会填满，会有空间浪费；
链表存储，每次push都需要new Node节点，并且node节点里面有prev和next成员，也会有额外的空间占用。

总结:
ArrayDeque会略胜一筹，不过差别通常可以忽略。经过性能对比，更倾向于使用ArrayDeque来表达Java中的栈功能。

参考文章：https://blog.csdn.net/qq_37509948/article/details/123022630

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)