网易雷火8.6 游戏研发工程师 笔试

说明

总共3个小时，题目描述纯属个人回忆，可能用词和原版有所区别。前3道a了，第四道中的4种情况只推导出了2种，过了56%，请参考其他大佬。

1. 队伍匹配

题目描述

有两个人想组队参加匹配2v2游戏，他们的分数分别是q1和q2，组队匹配的规则是两支队伍的各自分数和之间的差距小于等于p；如果参加者是两人，则自动组成队，如果是单人玩家，则可以与另外一名单独玩家临时组队。

输入

第一行输入q1，q2，p，x，其中q1/q2/p的定义如上文所示，x为其他双人组的数目。

接下来x行，每行两个数，分别是这双人组的分数

接着输入y，y为单人组的数目。

解析来y行，每行一个数，是单人玩家的分数。

输出

这两个人能匹配的到的对手的排列组合数。

解析

送分题，计算双人组符合条件的数目a，再O(n2)暴力遍历单人组符合条件的数目，相加就完了。

import java.util.Scanner;

public class Main1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q1 = scanner.nextInt();
        int q2 = scanner.nextInt();
        int p = scanner.nextInt();
        int x = scanner.nextInt();
        int[] a = new int[x];
        int[] b = new int[x];

        int res = 0;
        int q = q1+q2;
        for(int i=0;i<x;i++){
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
            if(Math.abs(a[i]+b[i]-q)<=p)
                res++;
        }

        int y = scanner.nextInt();
        int[] c = new int[y];

        for(int i=0;i<y;i++)
            c[i] = scanner.nextInt();
        for(int i=0;i<y;i++)
            for(int j=i+1;j<y;j++){
                if(Math.abs(c[i]+c[j]-q)<=p)
                    res++;
            }

        System.out.println(res);

    }
}

2. 跑酷

题目描述

一名玩家参加跑酷游戏，赛道均分为一段段高低不等的台阶，玩家从相同高度的台阶前进需要t1，跳到比现有台阶高一级的台阶需要t2，跳到比现有台阶低的台阶需要t3。同时游戏存在另一条平行赛道，平行赛道每个台阶的高度与原对应台阶的高度的和恒为4。玩家也可以切换在对应位置的两条赛道来回切，花费t4。玩家从起点跑到最后一个台阶视为游戏完成。

输入

第一行 n t1 t2 t3 t4
第二行有n个数，分别是第一条赛道的各台阶高度

输出

玩家完成游戏的最短耗时

解析

DFS，在每个位置上要么继续跑，要么切跑道，按两条跑法搜索，若当前时长已经大于最小时长则剪枝。另外用一个hashmap保存已经计算过的结果，由于有两条赛道，所以最多保存2n的位置上到终点的最短时间。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main2 {
    static long minTime;
    static int n;
    static int[] h;
    static int[] h2;
    static int t1,t2,t3,t4;
    static Map<String,Long> map;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        t1 = scanner.nextInt();
        t2 = scanner.nextInt();
        t3 = scanner.nextInt();
        t4 = scanner.nextInt();

        h = new int[n];
        h2 = new int[n];
        minTime = Long.MAX_VALUE;
        map = new HashMap<>();

        for(int i=0;i<n;i++){
            h[i] = scanner.nextInt();
            h2[i] = 4 - h[i];
        }
        fun(0,0,true);
        System.out.println(minTime);

    }

    static void fun(int now,long t,boolean flag){
        if(t>=minTime)
            return;
        if(map.containsKey(now+""+flag)){
            long oldT = map.get(now+""+flag);
            if(t>=oldT)
                return;
        }
        map.put(now+""+flag,t);

        if(flag){
            if(now!=n-1){
                if(h[now+1]==h[now])
                    fun(now+1,t+t1, true);
                else if(h[now+1]<h[now])
                    fun(now+1,t+t3, true);
                else if(h[now+1]-h[now]==1)
                    fun(now+1,t+t2, true);
            }else
                minTime = Math.min(minTime,t);
        }else{
            if(now!=n-1){
                if(h2[now+1]==h2[now])
                    fun(now+1,t+t1, false);
                else if(h2[now+1]<h2[now])
                    fun(now+1,t+t3, false);
                else if(h2[now+1]-h2[now]==1)
                    fun(now+1,t+t2, false);
            }else
                minTime = Math.min(minTime,t);
        }
        fun(now,t+t4,!flag);
    }
}

3. 解析配置文件

题目描述

有一个配置文件，对它进行逐行解析，满足以下条件：

• 需要存在空行，空行指的是仅有空格的行。
• 若该行以“#”开头，则表示该行为注释行，忽略改行
• 每一行只有一个key和value，形式如 key=value,若出现多个等号，则以第一个等号为主，其他等号视为value的值。
• 无论是key和value都要略去前后的空格
• value种可能存在{key}的情况，称为引用value，需要奖{key}替换为key对应的value。若引用的值不存在或循环引用，则解析失败。
• 引用的大括号不匹配也视为匹配失败
• 题目保证key和value自身没有大括号字段，即大括号一定是引用。

输入

第一行一个t，表示有t行数据。
接下来t行，即为文件的内容
最后一行key，表示要查询的key

输出

如果解析失败，输出“ERROR”；
如果解析成功，但不存在该key，输出“NULL”
如果解析成功并存在该key，输出该key的value

解析

按照题目要求逐行解析即可，先把全文空格删了，遇到空行或者注释行直接跳过。
用map表示已经解析出来的键值对，map2表示含有引用等待继续解析的键值对。
逐行解析，如果遇到引用，则加入map2，如果没有引用且格式正确，插入map。
接下来进行循环：
对于map2中的任意value，可以通过大括号得知求出该value中的引用有哪些，如果这些引用在map中存在，则替换它。
若替换后该value不存在引用，则将其从map2移到map1
当该轮循环没有发生替换，则退出循环。
退出循环后，检查map2，如果map2的大小不为0，则表示存在循环引用或引用不存在，直接输出解析失败。
如果map2的大小为0，说明全部解析成功，按题目要求返回map中的value即可。

import java.util.*;

public class Main3 {

    static void fun3(){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        Map<String,String> map = new HashMap<>();
        Map<String,String> map2 = new HashMap<>();
        scanner.nextLine();
        while(t>0){
            String line = scanner.nextLine();
            if(line.replace(" ","").equals("")||line.startsWith("#")){
                t--;
                continue;
            }
            int index = line.indexOf("=");
            String key = line.substring(0,index).trim();
            String value = line.substring(index+1).trim();

            if(key.equals("")||value.equals("")){
                System.out.println("ERROR");
                return;
            }
            if(value.contains("{")&&!check(value)){
                System.out.println("ERROR");
                return;
            }
            if(value.contains("{"))
                map2.put(key,value);
            else
                map.put(key,value);
            t--;
        }
        boolean flag = true;
        while(flag){
            flag = false;
            if(map2.keySet().size()==0)
                continue;
            List<String> temp = new ArrayList<>();
            for(String key:map2.keySet()){
                String value = map2.get(key);
                List<String> childs = getChild(value);
                for(String child:childs){
                    if(map.containsKey(child)){
                        value = value.replace("{"+child+"}",map.get(child));
                        flag = true;
                    }
                }
                if(value.contains("{"))
                    map2.put(key,value);
                else{
                    temp.add(key);
                    map.put(key,value);
                }
            }
            for(String key:temp)
                map2.remove(key);
        }

        String url = scanner.nextLine();
        if(map2.keySet().size()==0)
            System.out.println(map.getOrDefault(url, "NULL"));
        else
            System.out.println("ERROR");
    }

    static boolean check(String s){
        int cnt = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{')
                cnt++;
            else if(s.charAt(i)=='}')
                cnt--;
            if(cnt<0)
                return false;
        }
        return cnt == 0;
    }

    static List<String> getChild(String s){
        List<String> res = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        boolean flag = false;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{')
                flag = true;
            else if(s.charAt(i)=='}'){
                flag = false;
                res.add(temp.toString());
                temp = new StringBuilder();
            }
            else{
                if(flag)
                    temp.append(s.charAt(i));
            }
        }
        return res;
    }
    public static void main(String[] args) {
        fun3();
    }
}

4. 莫比乌斯赛车大逃杀

题目描述

赛车的跑道是一个长为M的纸条，但是将纸条一头旋转180后，接入另一头，形成一个莫比乌斯环。该环上有N量赛车，你控制1号赛车可以做以下行为：

• 攻击你前方或后方距离小于等于L的赛车，使其退赛
• 立刻瞬移到纸带背面，速度和方向不变
  求要歼灭除你自己之外的其他赛车，最短要多久，结果保留两位小数。

  输入：

  第一行 m n L
  第二行 有n个数，分别是1N号赛车的初始位置
  第三行 有n个数，分别是1N号赛车的速度，方向一致向前

  输出：

  使得只有自己留在场上的最短时间

  解析

  莫比乌斯环，由于自己可以瞬移到纸带的正反面，以自己为参考系，速度与方向不变，相当于其他车在抵达终点后，瞬移到起点又开始跑。（实际上其他车是跑到纸带的背面的新一圈，但对你而言没有区别），假设i号车的速度为vi，初始位置为si,只用考虑vi与v1，si与s1之间的大小关系所形成的四种情况追逐关系就能算出1号车歼灭i号车所需要的时间。最后输出最大的那个时间。
  由于时间来不及了，我只推导出两种，过了56%的用例...

import java.util.Scanner;

public class Main4 {

    static int m;
    static int l;
    static int s0;
    static int v0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        int n = scanner.nextInt();
        l = scanner.nextInt();
        int[] s = new int[n];
        int[] v = new int[n];

        for(int i=0;i<n;i++)
            s[i] = scanner.nextInt();
        for(int i=0;i<n;i++)
            v[i] = scanner.nextInt();
        s0 = s[0];
        v0 = v[0];
        double max = 0;
        for(int i=1;i<n;i++)
            max = Math.max(max,fun(s[i],v[i]));
        System.out.printf("%.2f\n",max);
    }

    public static double fun(int s1,int v1){
        if(Math.abs(s1-s0)<=l)
            return 0;
        if(s1>s0&&v1>=v0)
            return (m-s1+s0-l)/(double)(v1-v0);
        if(s1>s0&&v1<v0){


            double t = (m-s1)/(double)v1;
            double t2 = (s1-s0-l)/(double)(v0-v1);
            if(t2<=t)
                return t2;
            else{

                //return 0;
            }


        }
        if(s1<s0&&v1>=v0){
            double t = (m-s0)/(double)v0;
            double t2 = (s0-s1-l)/(double)(v1-v0);
            if(t2<=t)
                return t2;
            else{
                t = (m-s1)/(double)v1;
                double s3 = s0+ t*v0-m;
                return t+s3/(double)(v1-v0);
            }
        }

        if(s1<s0&&v1<v0){
            //return 0;
            return (s1-s0+m-l)/(double)(v0-v1);
        }
        return 0;
    }
}