美团2020.4.9部分笔试题

第二题：
代码为：
import java.util.HashMap;
import java.util.Scanner;
public class TestMain {
public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int n =Integer.parseInt(scanner.nextLine()) ;
    String a[] =scanner.nextLine().split(" ");
    String b[] =scanner.nextLine().split(" ");
    HashMap<String,Integer> c=new HashMap<String,Integer>();
    int max=0;
    for(int i = 0; i < a.length; i++){
        c.put(a[i], i);

    }

        for (int j = 0; j < b.length; j++) {

              if(c.get(b[j])<j){
                //求最长非连续公共子串的长度

                  max=  Math.max(j-findLongestCommonSubSequence( b,a,0,j-1,0,c.get(b[j])-1),max);

              }     


        }

    System.out.print(max);
}
public static int findLongestCommonSubSequence(String a[],String b[],int left1,int right1,int left2,int right2)
{
    int dp[][]=new int[right1-left1+2][right2-left2+2];
    int i,j;
    for(i=0; i<right1-left1+1; i++)
        for(j=0; j<right2-left2+1; j++)
            dp[i][j] = 0;

    for(i=1; i<=right1-left1+1; i++)
    {
        for(j=1; j<=right2-left2+1; j++)
        {
            if(a[left1+i-1].equals(b[left2+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[right1-left1+1][right2-left2+1];

}

}
继续优化上面代码
方法二：
对于队伍中的某个队员，只要他比开始排到前面的队员最差那位的排名要好，就会受到奖励。
代码如下：
import java.util.HashMap;
import java.util.Scanner;
public class TestQueue {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();// 读取nextInt后面的enter
String a[] = scanner.nextLine().split(" ");
String b[] = scanner.nextLine().split(" ");
HashMap<String, Integer> c = new HashMap<String, Integer>();
for (int i = 0; i < b.length; i++) {
c.put(b[i], i);

    }
    int count = 0;// 用来标记奖励的人数
    int max = 0;// 用来记录当前的最差名次
    for (int j = 0; j < a.length; j++) {
        if (c.get(a[j]) > max) {
            max = c.get(a[j]);
        } else {
            count++;

        }

    }
    System.out.println(count);
}

}

第一题：时间回溯：题目描述：有一个很经典的问题是，当前时间是aa:bb,请问若干分钟后是什么时间？我们今天的问题是一个相反的问题。
已知现在的时刻是星期X的yy:zz时刻，请问n分钟前是周几，时间是多少。
例如现在是周三，02:10，则200分钟之前，应该是周二，22：:5
输入：总共包含是三行
第一行一个整数X,表示今天是周X.(1<=X<=7)
第二行是一个24小时制的时间表示，时和分均含前导0，例如，1时1分表示为01:01.保证时间格式是合法的。
第三行是一个整数n,表示要求的是n分钟之前的时间。
样例输入：
3
02:10
200
输出
2
22:50