网易游戏雷火事业群算法笔试编程题(游戏研发工程师)

网易游戏雷火事业群笔试编程题

网易游戏雷火事业群算法笔试编程题(游戏研发工程师)

一般来说,算法题在面试的过程中,首先是要读懂出题人的意思,其次才是算法思想,最后才是编码环节。

如果你在一开始就没有读懂本题考查的是什么,那么你的算法思想就会出错,最后的编码当然也就不能解决实际问题。

因此算法题可以变相的考查应试者的沟通效率。也考查算法思想和编程语言特性的掌握,故很多大厂招聘人才的时候都会有算法题考查。


【编程题一】矩形排序【难度-简单】

网易游戏雷火事业群算法笔试编程题(游戏研发工程师)

给定N个矩形,每个矩形宽W米高H米

请按以下规则将这N个矩形排序,输出排序后的矩形列表
排序规则:
面积小的矩形排在面积大的矩形前面
面积相同的矩形,按照宽高比排序,宽高比大的矩形排在宽高比小的矩形前面
宽高比的定义为 min(W/H, H/W)
面积和宽高比都相同的矩形,按照宽排序,宽度更小的矩形排在宽度更大的矩形前面

题目直白解释:就是根据已知宽和高,先求出每个矩形的面积,然后按照面积从小到大排序,面积如果相同就按照宽和高的比例排序,如果宽高比例相同,则按照宽度最小的由小到大排列。

输入描述:

每组输入两行输入
第一行是一个整数N (0 < N <= 100)
第二行是2*N个整数,分别是每个矩形的宽W和高H,(0 < W,H <= 100)

输出描述:

每组数据输出一行,2*N个整数,分别是排序后的每个矩形的宽W和高H

输入例子1:

2  //2表示有两个矩形
2 2 1 1  //2,2表示第一个矩形宽和高,1,1表示第二哥矩形的宽和高

输出例子1:

1 1 2 2  //排序之后,就是第二个矩形面积小放在前面。面积大的排后面

题目编码详解:

/**
 * 矩形排序/钱老板赶工作
 * 简单
 * 网易题二解
 * @author mfgcs
 */
public class 冲刺算法面试每日一题5_27_网易矩形排序和钱老板赶工作 {

    public static void main(String[] args) {
        solutionOne();
        solutionTwo();
    }

    /**
     * 方法二
     */
    private static void solutionTwo() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] wh = new int[n][2];
        for (int i = 0; i < n; i++) {
            wh[i][0] = sc.nextInt();
            wh[i][1] = sc.nextInt();
        }
        Arrays.sort(wh, (o1, o2) -> {
            int area1 = o1[0] * o1[1];
            int area2 = o2[0] * o2[1];
            if (area1 != area2) {
                return area1 - area2;
            } else {
                double x1 = Math.min(o1[0] * 1.0 / o1[1], o1[1] * 1.0 / o1[0]);
                double x2 = Math.min(o2[0] * 1.0 / o2[1], o2[1] * 1.0 / o2[0]);
                if (x1 == x2) {
                    return o1[0] - o1[1];
                } else if (x1 > x2) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });
        for (int i = 0; i < n; i++) {
            System.out.print(wh[i][0] + " " + wh[i][1] + " ");
        }
    }

    /**
     * 方法一
     */
    private static void solutionOne() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
            nodes[i].w = scanner.nextInt();
            nodes[i].h = scanner.nextInt();
        }
        scanner.close();
        //自定义比较器排序
        Arrays.sort(nodes);
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                System.out.print(" ");
            }
            System.out.print(nodes[i].w + " " + nodes[i].h);
        }
    }
}

/**
 * 实现比较器
 */
class Node implements Comparable<Node> {
    int w;
    int h;

    @Override public int compareTo(Node o) {
        if (w * h != (o.w * o.h)) {
            return Integer.compare(w * h, o.w * o.h);
        }
        float temp1 = Math.min((float)w / h, (float)h / w);
        float temp2 = Math.min((float)o.w / o.h, (float)o.h / o.w);
        if (temp1 != temp2) {
            return -Float.compare(temp1, temp2);
        }
        return Integer.compare(w, o.w);
    }
}
//两种方法思路一致,只是写法不一样,
//大家看看自己熟练使用哪一种吧
网易游戏雷火事业群算法笔试编程题(游戏研发工程师)

矩形排序运行结果

//C++代码。思路都是一样的
#include<algorithm>
#include<iostream>
using namespace std;
struct rect{
    int w;
    int h;
};
int main()
{
    int n=0;
    cin>>n;
    rect array[100];
    for(int i=0;i<n;i++)
    {
        cin>>array[i].w>>array[i].h;
    }
    sort(array,array+n,[](rect a,rect b){
        int sa=a.w*a.h;
        int sb=b.w*b.h;
        if(sa==sb)
        {
            double da=min(a.w*1.0/a.h,a.h*1.0/a.w);
            double db=min(b.w*1.0/b.h,b.h*1.0/b.w);
            if(da==db)
            {
                return a.w<b.w;
            }
            else{
                return da>db;
            }
        }
        else
            return sa<sb;
    });
    for(int i=0;i<n;i++)
    {
        cout<<array[i].w<<" "<<array[i].h<<" ";
    }
    return 0;
}

小结:这道题其实就是简单的数学题,编码排序,数据运算以及数据存储方式选择。在编码过程中注意一下数据类型之间的转换即可


【编程题三】钱老板赶工【难度-中等】

网易游戏雷火事业群算法笔试编程题(游戏研发工程师)

钱老板去国外度了个假,刚回到公司就收到了 n 封催促工作完成的邮件。

每项工作都有完成截止日期 deadline,钱老板做每项工作都会花去cost天,而且不能中断。
请你帮钱老板安排一下完成工作的顺序,以减少总的工作推迟时间。

题目直白解释:根据每一项工作的完成时间和完成这件工作所需时间进行排序,让工作合理的安排,求完成所有工作最小延期多少天。

输入描述:

第一行包含一个正整数 n(1<=n<=20),表示工作数量。

接下来 n 行,每行包含两个整数,分别表示第 i 项工作的 deadline 和 cost。

输出描述:

一个数字,表示钱老板最少需要推迟几天才能完成所有工作。

输入例子1:

3        // 总共三件工作
3 3     // 第一个3表示,度假后的第3天完成,第二个3表示完成需要3天,
8 1     // 第一个8表示,度假后的第8天完成,第二个1表示完成需要1天,
3 2     // 第一个3表示,度假后的第3天完成,第二个2表示完成需要2天,

输出例子1:

2        // 上面的工作,钱老板完成所有工作至少要2推迟两天
          // 因此合理的顺序是 1->3->2 或 3->1->2,均推迟 2 天

题目编码详解:

//C++代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<limits.h>
using namespace std;
static int N,dp[1<<20],sum[1<<20];
int main() {
  cin >> N;
  vector<vector<int>> x(N,vector<int>(2));
  for(int i=0;i<N;i++) {
    cin >> x[i][0] >> x[i][1];
  }
  int res=0;
  queue<int> q;
  q.push(0);
  while(!q.empty()) {
    int cur=q.front();q.pop();
    for(int i=0;i<N;i++) {
      if(!(cur&(1<<i))) {
        int next=cur|(1<<i);
        if(!sum[next]) {
          q.push(next);
          sum[next]=sum[cur]+x[i][1];
          dp[next]=INT_MAX;
        }
        dp[next]=min(dp[next],dp[cur]+max(sum[next]-x[i][0],0));
      }
    }
  }
   
  cout << dp[(1<<N)-1] << endl;
  return 0;
}

总结:求最小值的,一般考虑使用动态规划,我这边Java代码暂时不公布,因为最近网易在用这道题招聘JAVA后端研发。所以暂不透露编码!

给大家提供个思路,题目中要求求最小延迟天数,我们可以使用工作截止时间排序,然后对每一个工作完成的具体时间天数进行处理,找出延迟工作的时间进行累加,最后返回这个时间即可。

其实根据上面C的代码也可以参考。

特别鸣谢C++代码由Cooike大神提供!

声明:本文由会火号官方原创,如若转载,请注明出处:https://www.huihuohao.com/s/2220.html

发表评论

登录后才能评论