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

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

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

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

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

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