2017年阿里基础架构实习生笔试在线编程题 题解

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 1.4k 阅读时长 ≈ 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
一年一度的阿里运动会又要开始了，同学们终于有一天可以离开鼠标键盘显示器，全身心的投入到各种体育项目中。UED设计师小红虽然没有参加体育项目，但她的责任重大，因为她是拉拉队的队长，她需要在每个项目中为参赛的同学们加油助威。
因为运动会的项目众多，很多项目在在同一时间会同时进行着。作为拉拉队长，小红需要遵守以下规则：
不能同时给多个体育项目加油助威
给每个体育项目加油的时长必须超过项目时长的一半，每个体育项目只能加油一次
体育项目的开始和结束时间都是整点，如果项目进行到一半想要离开，也只能选择整点离开
不考虑往返于各个体育项目比赛场地中花费的时间
请帮小红设计一个算法，在已知所有体育项目日程的前提下，计算是否能在每个体育项目中为参赛的同学们加油。

说明：
如果体育项目时长为2，超过时长的一半为2;
如果体育项目时长为3，超过时长的一半为2;
如果体育项目时长为4，超过时长的一半为3；

编译器版本: Java 1.8.0_66
请使用标准输入输出(System.in, System.out)；已禁用图形、文件、网络、系统相关的操作，如java.lang.Process , javax.swing.JFrame , Runtime.getRuntime；不要自定义包名称，否则会报错，即不要添加package answer之类的语句；您可以写很多个类，但是必须有一个类名为Main，并且为public属性，并且Main为唯一的public class，Main类的里面必须包含一个名字为'main'的静态方法（函数），这个方法是程序的入口
时间限制: 1S (C/C++以外的语言为: 3 S)   内存限制: 64M (C/C++以外的语言为: 576 M)
输入:
输入包括1+N行 第一行输入一个整数N, 1 <= N <= 10，表示今天要参加多少个讨论会 后续N行，每行输入开始和结束时间，均为整数，用空格分隔，0 <= startTime < endTime <= 24
输出:
输出包括一行 如果小红能够参加全部讨论会，返回1 如果小红不能够参加全部讨论会，返回-1
输入范例:
3
3 10
1 5
4 6
输出范例:
1

代码运行全部通过！ 耗时: 470ms, 内存: 24168K

这道题其实就是一道贪心的题目，用贪心的话复杂度是O（nlogn)，不过因为n很小，所以估计阿里是设计的dfs都能做出来。

我们把所有运动项目按照结束时间排序，因为我们能够想到结束时间越早一定是越优的，然后一个个去判断就好了。

代码如下：

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
45
46
47
48
49
50
51
52
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Meeting {
    int start;
    int end;

    Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Ali1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Meeting> meetings = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Meeting meeting = new Meeting(scanner.nextInt(), scanner.nextInt());
            meetings.add(meeting);
        }
        PriorityQueue<Meeting> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a.end));
        for (Meeting meeting : meetings) {
            priorityQueue.offer(meeting);
        }

        int last = 0;
        boolean flag = true;

        while (!priorityQueue.isEmpty()) {
            Meeting meeting = priorityQueue.poll();
            int t = (meeting.end - meeting.start) / 2 + 1;
            if (last <= meeting.start) {
                last = meeting.start + t;
            } else if (last + t > meeting.end) {
                flag = false;
                break;
            } else {
                last = last + t;
            }
        }
        if (flag) {
            System.out.println(1);
        } else {
            System.out.println(-1);
        }
    }
}

第二题

1
2
3
4
5
6
7
8
9
10
11
12
我们知道每一个大于1的整数都一定是质数或者可以用质数的乘积来表示，如10=2*5。现在请设计一个程序，对于给定的一个(1，N] 之间的正整数（N取值不超过10万），你需要统计(1，N] 之间所有整数的质数分解后，所有质数个数的总个数。举例，输入数据为6，那么满足(1,6] 的整数为2，3，4，5，6，各自进行质数分解后为：2=>2，3=>3，4=>2*2，5=>5，6=>2*3。对应的质数个数即为1，1，2，1，2。最后统计总数为7。
编译器版本: Java 1.8.0_66
请使用标准输入输出(System.in, System.out)；已禁用图形、文件、网络、系统相关的操作，如java.lang.Process , javax.swing.JFrame , Runtime.getRuntime；不要自定义包名称，否则会报错，即不要添加package answer之类的语句；您可以写很多个类，但是必须有一个类名为Main，并且为public属性，并且Main为唯一的public class，Main类的里面必须包含一个名字为'main'的静态方法（函数），这个方法是程序的入口
时间限制: 1S (C/C++以外的语言为: 3 S)   内存限制: 64M (C/C++以外的语言为: 576 M)
输入:
输入数据包含1行，为一个大于1的整数（不超过10万）。
输出:
输出小于该数的所有整数质数分解后的总个数。
输入范例:
6
输出范例:
7

其实就是在打表法上多加了一层。

代码如下：

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
45
46
47
48
49
import java.util.Scanner;

/**
 * Created by daniel on 2017/4/26.
 */
public class Ali2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        long ans = 0;
        boolean[] isNotPrime = new boolean[n + 1];
        int[] nums = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            if (isNotPrime[i]) {
                continue;
            }
            for (int j = 2; i * j <= n; j++) {
                isNotPrime[i * j] = true;
            }
        }

        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) {
                nums[i] = 1;
                ans++;
                continue;
            }
            // will tle
//            for (int j = i - 1; j >= 2; j--) {
//                if (i % j == 0) {
//                    nums[i] = nums[j] + 1;
//                    ans += nums[i];
//                    break;
//                }
//            }
            for (int j = 2; j <= n / 2; j++) {
                if (i % j == 0) {
                    nums[i] = nums[i / j] + 1;
                    ans += nums[i];
                    break;
                }
            }
        }

        System.out.println(ans);
    }
}