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

第一题

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 classMain类的里面必须包含一个名字为'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] 的整数为23456,各自进行质数分解后为:2=>23=>34=>2*25=>56=>2*3。对应的质数个数即为11212。最后统计总数为7
编译器版本: Java 1.8.0_66
请使用标准输入输出(System.in, System.out);已禁用图形、文件、网络、系统相关的操作,如java.lang.Process , javax.swing.JFrame , Runtime.getRuntime;不要自定义包名称,否则会报错,即不要添加package answer之类的语句;您可以写很多个类,但是必须有一个类名为Main,并且为public属性,并且Main为唯一的public classMain类的里面必须包含一个名字为'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);
}
}