京东秋招后端笔试第五场（答得不好）

选择题

记得考了：

操作系统中单处理器、多处理器互斥

数据库的共享锁和互斥锁

哈希采用线性探测时平均搜索长度

HTTP2 和 HTTP3的区别，基于什么协议，HTTP2是不是二进制的

编程题

第一题

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();//有这么多个卡 编号是1到n
        int m=in.nextInt();//有这么多个门 每个门对应一个区间
//本质上 是要确认有没有哪个数 落在所有区间内
        int left=Integer.MIN_VALUE,right=Integer.MAX_VALUE;
        int ans=0;
        for(int i=0;i<m;i++){
            int li=in.nextInt();
            int ri=in.nextInt();
            left=Math.max(left,li);
            right=Math.min(right,ri);
            if(left>right)
                break;
        }
        if(left<=right)
            ans=right-left+1;
        System.out.println(ans);

    }
}

第二题只通过了37.5%的用例，时间超时

调了快一小时，用例通过数都没变懵逼中希望有大佬能发下解答

题目

我写的代码思路就是用回溯法找到所有情况

把问题转换成了找到walk个不用跳的格子

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static Set<Long> set;
    static long L;static long b;
    static Map<Long[],Boolean> quicktest;
    private static boolean test(long walk,long cur){//试探 返回true或者false
        Boolean ans=quicktest.getOrDefault(new Long[]{walk,cur},null);
        if(ans!=null)
            return ans;
        if(walk==0) {
            quicktest.put(new Long[]{walk,cur},cur <= L);
            return cur <= L;
        }
        if(walk<0)
        { quicktest.put(new Long[]{walk,cur},false);
            return false;}
        if(cur>=L)
        { quicktest.put(new Long[]{walk,cur},false);
            return false;}
        //如果跳
        cur+=b;
        boolean tmp=test(walk,cur),tmp2=false;
        if(tmp)
            return true;
        cur-=b;//撤回这个跳
        //判断这里能不能走
        if(set.contains(cur)==false){//没有障碍物 能走
            walk--;cur++;
            tmp2=test(walk,cur);
        }
        quicktest.put(new Long[]{walk,cur},tmp2);
        return tmp2;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T= in.nextInt();//一共T组数据
        for(int i=0;i<T;i++){
            int n= in.nextInt();//一共有n个障碍
            L= in.nextLong();//起点是0 终点是L
            long m= in.nextLong();//必须恰好完成m次
            b= in.nextLong();//每次只跳这个长度
            set=new HashSet<>();
            //接下来输入n个整数
            for(int j=0;j<n;j++){
                long a=in.nextLong();//可以得到每个障碍物的位置
                set.add(a);
            }
            quicktest=new HashMap();
            //总结一下约束条件：最后恰好到达L。跳的次数恰好是m。如果从i起跳，那么会到达i+b
            //思路：一次递归 只要能恰好找到walk个 用走的格子就行
            long walk=L-m*b;
            if(walk<0){
                System.out.println("No");
                continue;
            }else if(walk==0){
                System.out.println("Yes");
                continue;
            }
            boolean ans=test(walk,0);
            //最后输出yes或者no
            if(ans){
                System.out.println("Yes");
            }else
                System.out.println("No");

        }

    }
}