9月1日拼多多笔试

前言

2020年09月01日晚上拼多多的笔试题,我一共A了1;0.6;0.6;0.5,共计2.7/4,感觉应该能进面试吧

第一题

给定一个边长为n的矩阵,依照中心横线,中心竖线,两个对角线,把矩阵分成八个部分,每部分填入该部分对应的数字,分割线填0,求结果。

11
0 2 2 2 2 0 1 1 1 1 0
3 0 2 2 2 0 1 1 1 0 8
3 3 0 2 2 0 1 1 0 8 8
3 3 3 0 2 0 1 0 8 8 8
3 3 3 3 0 0 0 8 8 8 8
0 0 0 0 0 0 0 0 0 0 0
4 4 4 4 0 0 0 7 7 7 7
4 4 4 0 5 0 6 0 7 7 7
4 4 0 5 5 0 6 6 0 7 7
4 0 5 5 5 0 6 6 6 0 7
0 5 5 5 5 0 6 6 6 6 0

那就老老实实做呗,还能怎么样….

代码不是很优雅:

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
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
if (n <= 3 || n >= 200) {
return;
}


int[][] matrix = new int[n][n];

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = 7;
}
}

for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n / 2; j++) {
matrix[i][j] = 2;
}
}

for (int i = 0; i < n / 2; i++) {
for (int j = n / 2; j < n - i; j++) {
matrix[i][j] = 1;
}
}

for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < i; j++) {
matrix[i][j] = 3;
}
}

for (int i = 0; i < n / 2; i++) {
for (int j = n - 1; j > n - i - 1; j--) {
matrix[i][j] = 8;
}
}

for (int i = n / 2; i < n; i++) {
for (int j = 0; j < n - i; j++) {
matrix[i][j] = 4;
}
}

for (int i = n / 2; i < n; i++) {
for (int j = n / 2; j > n - i - 1 && j >= 0; j--) {
matrix[i][j] = 5;
}
}

for (int i = n / 2; i < n; i++) {
for (int j = n / 2; j < i; j++) {
matrix[i][j] = 6;
}
}

// 对角线0
for (int i = 0; i < n; i++) {
matrix[i][i] = 0;
matrix[i][n - i - 1] = 0;
}

// 奇数的话还需要横着和竖着
if (n % 2 == 1) {
for (int i = 0; i < n; i++) {
matrix[i][n / 2] = 0;
}
for (int j = 0; j < n; j++) {
matrix[n / 2][j] = 0;
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}

第二题

给定一个N x M的矩阵,每个里面有数字0或者1,交换一个0和1的位置,让相连的1的面积最大。

下面的算法只通过了60%,因为我考虑的不是交换,而是直接把一个0给改成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
50
51
52
53
54
55
public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] matrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = scanner.nextInt();
}
}

System.out.println(helper(matrix));
}

public static int helper(int[][] matrix) {
int max = 0;
int row = matrix.length;
int col = matrix[0].length;
boolean flag = false;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[i][j] = 1;
max = Math.max(max, dfs(i, j, matrix, new boolean[row][col]));
if (max == row * col) {
return max;
}
matrix[i][j] = 0;
flag = true;
}
}
}
if (flag) {
return max;
} else {
return row * col;
}
}

private static int dfs(int i, int j, int[][] matrix, boolean[][] visited) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] == 0 || visited[i][j]) {
return 0;
}
visited[i][j] = true;

return 1 +
dfs(i, j + 1, matrix, visited) +
dfs(i, j - 1, matrix, visited) +
dfs(i - 1, j, matrix, visited) +
dfs(i + 1, j, matrix, visited);
}

}

第三题

01背包的变种,可能会出现有负数的商品重量以及负价值的商品,我这里直接用正数的01背包混了过去。

第四题

容斥原理做的。我自己想到了,但是实现起来好像有问题,就靠暴力混了50%。