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

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

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

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

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

给定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

2  //2表示有两个矩形2 2 1 1  //2,2表示第一个矩形宽和高，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。

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

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

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大神提供！