顺丰开发、商汤测开、有赞测开笔试 - 20200820

发表于 | 分类于 |

不按照时间先后了，反正都是在一个晚上。

先是顺丰，若干选择，两道编程题。编程题：1.服务器管理（分配）；2.赏金猎人。

一道贪心，一道动规。题目本身不难，据后了解好多同学做题时都是走错了路。我只做了第一道，还没AC……

1. 服务器管理

题目描述

小A有一批服务器要出租，每一个服务器有一个固定的带宽；客户根据自己需要的带宽租用服务器，一台服务器只能租给一个人。

小A现有n个服务器，第 i 台服务器对应的带宽为a_i；现有m个客户需要服务器，第 i 位客户需要的带宽为b_i，预算为c_i（注意：这里 i 的含义不同）。现在求小A的服务器最多能租多少钱？

要求：服务器带宽独立不可叠加，不能成功租出则输出0。输入输出规则和用例如下。

1
2
3
4
5
6
7
8
9
10
Input:
3 4      【n m】
1 2 3    【a1 a2 a3】
2 1      【b1 c1】
3 2	     【b2 c2】
3 3      【b3 c3】
1 1      【b4 c4】

Output:
5

解题思路

因为服务器带宽独立不可叠加，所以优先选择可以满足带宽需求的资金最充裕的客户。采用贪心算法求解，使用带宽最小的服务器来尝试满足客户需求，所以要先进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class MainSF {
    public int rentServer(int n, int m, int[] a, int[][] bc) {
        Arrays.sort(a);
        int result = 0;
        // 为当前服务器a_i选择客户
        for (int i = 0; i < n; i++) {
            int temp = 0;
            int index = -1;
            int need_a = a[i];
            for (int j = 0; j < m; j++) {
                // 客户需求带宽多于供给，跳过
                if (bc[j][0] > need_a) {
                    continue;
                }
                // 保留满足需求且资金最大的客户的预算价格和对应索引
                if (bc[j][1] > temp) {
                    temp = bc[j][1];
                    index = j;
                }
            }
            // 表示已完成分配，需求变为无穷大
            if (index != -1) {
                bc[index][0] = Integer.MAX_VALUE;
            }
            result = result + temp;
        }
        return result;
    }

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();int m = sc.nextInt();
        int[] a = new int[n];int[][] bc = new int[m][2];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int j = 0; j < m; j++) {
            bc[j][0] = sc.nextInt();bc[j][1] = sc.nextInt();
        }
        
        MainSF sf = new MainSF();
        System.out.println(sf.rentServer(n, m, a, bc));
        sc.close();
    }
}

2. 赏金猎人

题目描述

A是一名赏金猎人，最近他获得了一些任务，受时间限制只能完成其中一部分。任务用l, r, w来定义，其中任务开始时间l,任务结束时间r,任务报酬w。A非常贪心，他想知道在自己任务不冲突的情况下最多获得多少金钱。

1
2
3
4
5
6
7
8
Input:
3
1  3  5
2  7  3
5 10  1

Output:
6

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
n=int(input())    # 读数据
renwu=[] 
for i in range(n):
    renwu.append(list(map(int,input().split())))

renwu.sort()      # 任务按开始时间排序
dp=[i[-1] for i in renwu]  # 动态规划数组初始化为每个任务的收益
for i in range(n):         # dp[i]是以当前任务 i 为最后一个任务可以取得的最大收益
    for j in range(i):
        if renwu[j][1]<renwu[i][0]:
            # 这个转移方程真是精华
            dp[i]=max(dp[i],dp[j]+renwu[i][-1])
print(max(dp))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Shunfeng2 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int a =scanner.nextInt();
        long[][] arr=new long[(int) a][3];
        for (int i = 0; i < a; i++) {
            arr[i][0]=scanner.nextLong();
            arr[i][1]=scanner.nextLong();
            arr[i][2]=scanner.nextLong();
        }
        Arrays.sort(arr, new Comparator<long[]>() {
            @Override
            public int compare(long[] o1, long[] o2) {
                return (int) (o1[1]-o2[1]);
            }
        });
        long[] dp = new long[(int) a];
        dp[0] = arr[0][2];
        for (int i = 1; i < a; i++) {
            int begin = 0;
            while (arr[begin][1] < arr[i][0]){
                begin++;
            }
            long tmp = 0;
            if (begin >= 1){
                tmp = dp[begin-1]+arr[i][2];
            }else {
                tmp = arr[i][2];
            }
            dp[i] = Math.max(tmp,dp[i-1]);
        }
        System.out.println(dp[a-1]);
    }
}

商汤应该是有三道题。记不太清了，基本上是LeetCode原题。

1.给定字符串，包含字母数字和空格，问其中的字符能组成多少”Good”。

2.给定一个区间的集合，找到移除区间的最小数量，使剩余区间不重叠。

3.给定一个数字矩阵，找到一条最长的上升路径，只能上下左右移动。

有赞也是三道编程题。

1.计算两个大数的模。我用了BigInteger但还是只过了一部分。

2.统计日志里级别为ERROR的类名及其ERROR的次数，并输出。

3.将文档目录层级转换成二叉树。