阿里Java实习生笔试题2020-03-27场

阿里的笔试题只有两个编程题，让我很意外。。。本以为会有计算机网络，数据库，操作系统等类的基础题。等笔试的时候发现就有两道编程题。

第一题是一个给定一个序列A与一个序列B，每次只能把序列A的一个字符移动到字符尾，问能否通过这种方式把序列A变为序列B，如果能变成，最少需要多少次，输出最少次数N，不能变成输出-1。
这题还是挺简单的。代码我也没有保存。。。所以就不对这个进行解释了，如果有疑问可以在下面留言。有需要我会解释一下。

第二题是给你N个区间，对每个区间（Li，Ri）随机取一个数，得出N个数，取到的数中最小的数的期望是多少，其中1<=N<=2000，1<=Li<=Ri<=2000。要求好像是误差要小于 1e-6。
例子

2
1 1
2 3

这个有{1，2}，{1，3}，{2，2}，{2，3}，{3，2}{3，3}，这个期望是1.8333333

对于这个肯定不能一个一个的列出来，我是使用优先队列，每次把Li最小的拿出来，笔试中我是看它在所占的权重，把所有的相加，除以总的数量算的，由于没有考虑到数的大小问题，出现数太大，超出计算范围，无法计算，导致只是过了35%的数据。这种方法相对来说精度高一些，因为只有最后一个除法是会导致精度误差的，之前的运算都是整数。都不存在精度的问题。在笔试后想到了修改的方法，就是看它在所有中所占的概率，加权后相加，然后就能得出期望结果，这样虽然会产生较大的误差，但是这种方法是可计算的，不会出现数太大，导致无法计算的情况。总体的复杂度只有N^2^logN，这个。以下是我使用概率方法的代码

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static double qw = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node arr[] = new Node[n];
        for(int i = 0;i<n;i++) &#123;
            arr[i] = new Node(sc.nextInt());
        &#125;
        for(int i = 0;i<n;i++) &#123;
            arr[i].b = sc.nextInt();    
        &#125;
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        
        for(int i = 0;i<n;i++) &#123;
            pq.add(arr[i]);
        &#125;
        double test = 1;
        double ans = 0;
        while(!pq.isEmpty()) &#123;
            Node te = pq.poll();
            if(te.b<te.a||test<=0) &#123;
                break;
            &#125;
            ans += test*te.a/(te.b-te.a+1);
            test = test - test/(te.b-te.a+1);
            te.a++;
            pq.add(te);
        &#125;
        System.out.println(ans);
    &#125;

&#125;
class Node implements Comparable<Node>&#123;
    int a;
    int b;
    public Node() &#123;
    &#125;
    public Node(int a) &#123;
        this.a = a;
    &#125;
    @Override
    public int compareTo(Node o) &#123;
        return this.a - o.a;
    &#125;
    @Override
    public String toString() &#123;
        return "Node [a=" + a + ", b=" + b + "]";
    &#125;
&#125;