9月6日字节教育笔试

前言

2020年9月6日上午10点-12点的笔试。

第一题

跳楼梯问题,不能连续跳两级。

如果只是跳楼梯那是很简单的,这里加了一个限制条件,不能连续跳2级的。

那么假设目前要跳7级的有多少种,那么所有跳6级的肯定可以,因为6级跳到7级只需要跳一级,必然是满足的。而5级不能直接加上去,因为5级跳到7级的是直接跳2级的,所以我们要多想一步,就是直接选4级的。

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
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
if (n == 0) {
System.out.println(0);
return;
}
if (n == 1) {
System.out.println(1);
return;
}
if(n == 2){
System.out.println(2);
return;
}
long[] dp = new long[n+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i < n+1; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
System.out.println(dp[n]);
}
}

这里注意dp要用Long数组,否则会溢出。

第二题

给定一个数组,对于其中的每个数字,找到这个数字左边的比它大,且离他最近的一个数;同样找到一个在它右边,且比它大的数字,如果不存在则为0,求出这两个数字相乘,最大的那个。

最简单的就是暴力,对于每个数字,我都从该数字开始往两边找,但是这样时间复杂度是O(N2)。

然后稍微想想就知道可以利用单调栈来完成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int[] findMaxRight(int[] array) {
if (array == null) {
return array;
}
int size = array.length;
int[] result = new int[size];
Stack<Integer> stack = new Stack<>();
stack.push(0);
int index = 1;
while (index < size) {
if (!stack.isEmpty() && array[index] > array[stack.peek()]) {
result[stack.pop()] = index + 1;
} else {
stack.push(index);
index++;
}
}
if (!stack.isEmpty()) {
result[stack.pop()] = 0;
}
return result;
}

但是这题我用了单调栈,理论上时间已经是O(n)了,不知道为什么还是只过了63%,迷。

第三题

给定一个长度为N的数组,和一个重复的数字M,意味着这个数组重复了M次,那么求出这个大数组中最大的子序列和。

最大子序列和很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static long maxSubSequence(long[] array) {
long length = array.length;
long res = 0;
long temp = 0;
for (long i = 0; i < length; i++) {
temp += array[(int) i];
if (temp > res) {
res = temp;
} else if (temp < 0) {
temp = 0;
}
}
return res;
}

要让数组重复M次也简单,但是显然这题如果你真这么做了,肯定只能通过一些数据。

其实只需要考虑三种情况,就可以推导出所有的情况了。

第一种,只有数组本身,那很简单,直接撸就完事了。

第二种,数组重复了一次,那么可能因为拼接的那部分,而导致结果发生变化。

第三种,数组重复了两次,此时我们已经可以能够得到每拼接一次数组,会让答案变大还是变小,根据这个就可以计算了。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
long[] array = new long[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextInt();
}
sc.close();

// 特殊情况判断,如果数组中每个数字都是负数,那么选择这些负数中最大的那个
long minus = 0;
long bigest = array[0];
for (int i = 0; i < N; i++) {
if (array[i] < 0) {
minus++;
}
bigest = Math.max(bigest, array[i]);
}
if (minus == N) {
System.out.println(bigest);
return;
}

long oneSum = maxSubSequence(array);

if (M == 1) {
System.out.println(oneSum);
return;
}

// 计算出两个的最大
long[] array2 = new long[2 * N];
for (int i = 0; i < N; i++) {
array2[i] = array[i];
array2[i + N] = array[i];
}
long twoMax = maxSubSequence(array2);

// 计算出三个的最大
long[] array3 = new long[3 * N];
for (int i = 0; i < N; i++) {
array3[i] = array[i];
array3[i + N] = array[i];
array3[i + N + N] = array[i];
}
long threeMax = maxSubSequence(array3);

if (M == 2) {
System.out.println(twoMax);
return;
}
if (M == 3) {
System.out.println(threeMax);
return;
}
if (M > 3) {
long sub = threeMax - twoMax;
if (sub > 0) {
System.out.println(twoMax + (M - 2) * sub);
} else {
long max = Math.max(oneSum, twoMax);
max = Math.max(max, threeMax);
System.out.println(max);
}
}
}

public static long maxSubSequence(long[] array) {

long length = array.length;
long res = 0;
long temp = 0;
for (long i = 0; i < length; i++) {
temp += array[(int) i];
if (temp > res) {
res = temp;
} else if (temp < 0) {
temp = 0;
}
}
return res;
}
}

第四题

完全不会做。