陈浪平的博客
0%

9月1日拼多多笔试

发表于 更新于 分类于 Disqus：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

前言

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%。