写在前面
这次网易算法题总的来说难度还行，除了3个编程题外，还有选择题和简答题，共两个小时，时间还是比较紧的。这儿只写下我做的算法题的解，其他题目记不住，且岗位不同题目不同。我做的算法题是高数课，苹果和aazz这3道题，下面就主要写一下这3道题的解题过程，笔试中我AC了前两道，第3道题过了20%。欢迎大家在评论区讨论交流。
题目一
题目描述
小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望老师讲到有趣的地方的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。
输入描述
第一行n，k, (1 <= n, k <= $10^5$)，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。
第二行 n个数，$a{1},a{2},…, a{n} (1<= a{i} <= 10^4)$，表示小易对每分钟知识点的感兴趣评分。
第三行 n个数，$t{1}, t{2}, …, t_{n}$，表示每分钟小易是否清醒，1表示清醒。
输出描述
小易这堂课听到的知识点的最大兴趣值。
示例
输入1
2
36 3
1 3 5 2 5 4
1 1 0 1 0 0
输出1
16
解题思路1
首先对示例进行分析，输出16是在第3分钟将小易唤醒。所以小易的分值为1+3+5+2+5 = 16。
其次我们可以考虑一种比较暴力的解法，即我们先把醒着的分值和sum计算出来，然后我们再遍历每分钟是否醒着，如果为0，那么我们就遍历接下来k个值，把这k个值未醒着的分值加到前面的sum上，然后再去与最大值进行比较更新，直到遍历结束。不过这样由于超时只能过90%的测试用例。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
36public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] scores = new int[n];
for (int i = 0; i < n; i++) {
scores[i] = sc.nextInt();
}
int[] sleep = new int[n];
for (int i = 0; i < n; i++) {
sleep[i] = sc.nextInt();
}
int sum = 0;
int max = -1;
for (int i = 0; i < n; i++) {
if (sleep[i] == 1) {
sum += scores[i];
}
}
for (int i = 0; i < n; i++) {
if (sleep[i] == 0) {
int temp = sum;
for (int j = i; j < Math.min(i + k, n); j++) {
if (sleep[j] == 0) {
temp += scores[j];
}
}
if (temp > max) {
max = temp;
}
}
}
System.out.println(max);
}
}
解题思路2
我们可以考虑在遍历每分钟是否醒着时，不去遍历后面的k个值，而采取利用下标进行计算的方式。这个时候我们就需要利用到累加和的思想了。
我们首先定义3个数组，长度都为n。
leftScore: 表示从左到右醒着的分值的累加和。
rightScore: 表示从右到左醒着的分值的累加和。
total: 表示从左到右分数的累加和。
然后当我们遍历到为未醒着的位置i时，那么这时的总体分数为3部分之和：leftScore[i-1] + rightScore[i+k] + (total[i+k-1] - total[i-1])。
当然还要加上一些边界处理。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
50public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] scores = new int[n];
for (int i = 0; i < n; i++) {
scores[i] = sc.nextInt();
}
int[] sleep = new int[n];
for (int i = 0; i < n; i++) {
sleep[i] = sc.nextInt();
}
int sum = 0;
int[] leftscore = new int[n];
for (int i = 0; i < n; i++) {
if (sleep[i] == 1) {
sum += scores[i];
}
leftscore[i] = sum;
}
int[] rightscore = new int[n];
sum = 0;
for (int i = n-1; i > -1; i--) {
if (sleep[i] == 1) {
sum += scores[i];
}
rightscore[i] = sum;
}
int[] total = new int[n];
sum = 0;
for (int i = 0; i < n; i++) {
sum += scores[i];
total[i] = sum;
}
int max = -1;
for (int i = 0; i < n; i++) {
if (sleep[i] == 0) {
int temp = 0;
temp += (i - 1) < 0 ? 0 : leftscore[i-1];
temp += (i + k) >= n ? 0 : rightscore[i+k];
temp += total[Math.min(i+k-1, n-1)] - (i - 1 < 0 ? 0 : total[i-1]);
if (temp > max) {
max = temp;
}
}
}
System.out.println(max);
}
}
题目二
题目描述
又到了丰收的季节，恰好小易去牛牛的果园里游玩。 牛牛常说他多整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。 在果园里有N堆苹果，每堆苹果的数量为ai,小易希望知道从左往右数第x个苹果是属于哪一堆的。 牛牛觉得问题太简单了，所以希望你来替他回答。
输入描述
第一行 一个数 n (1<= n <= $10^5$)
第二行 n个数 $a{i}$ (1<=$a{i}$<=1000),表示从左往右数第i堆有多少苹果
第三行 一个数m (1<= m <= $10^5$),表示有m次询问
第四行 m个数$q{i}$, 表示小易希望知道第$q{i}$个苹果属于哪一堆。
输出描述
m行，第i行输出第$q_{i}$个苹果属于哪一堆。
示例
输入1
2
3
45
2 7 3 4 9
3
1 25 11
输出1
2
31
5
3
解题思路
这个题目题意比较好理解，思路也比较简单。首先对苹果数进行累加和。然后再对查询进行二分查找。
解题代码
1 | public class Main { |
题目三
题目描述
给你n个a,m个z组成所有可能的字符串，并将字符串按字典序从小到大排列，输出第k个字符串。
若不存在，输出-1。
输入描述
第一行为三个数，分别为a的个数n,z的个数m,第k个字符串。
输出描述
第k个字符串
示例
输入1
2 2 6
输出1
zzaa
解题思路
这个题我在笔试的时候是采用全排列的方式做的，时间复杂度很高，只过20%，没有利用只有a,z，且很多重复的这些信息。
下面的思路是自己后来想的以及结合一些网上的思路。
现在我们来算给定n和m后，总共有多少中情况：我们很容易得到是$C{m+n}^m = \frac{(m+n)!}{m!n!}$，如果k大于这个数，即可返回-1。
接下来我们用动态规划来做这个题目，假设dp[i][j]表示i个a和j个z的方案数，根据上面这个公式列表计算我们可以发现：d[i][j] = dp[i-1][j] + dp[i][j-1]；
这样我们就可以求出方案数。然后我们来求输出字符串。
假设我们现在考虑输出字符串的第i个字符，如果当前选了a字符，假设后面剩余字符a和z的个数是$m{1},n{1}$，那么后面所能组成的字符串总数为$dp[m{1}][n{1}]$。如果k小于$dp[m{1}][n{1}]$，那么我们就能选a，因为后面组成的数目大于k，我们要选字符a来缩小这个组合数。
否则，就选z，这时k -= $dp[m{1}][n_{1}]$，这是因为要减去a形成的方案数。
解题代码
1 | public class Main { |
