有赞2020校招——编程题AC代码

第一题，数组归并排序

测试用例

1
1,2,3,4|4,5,6,7,8

答案（在排序的过程中还需要去重）

1
1，2，3，4，5，6，7，8

但是有一点想不明白，总是出现越界错误，只好骚套路AC了

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
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;

/**
 * @author <a href="mailto:liaochunyhm@live.com">liaochuntao</a>
 * @since
 */
public class ExamOne {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = "";
//        String s;
//        s = scanner.nextLine();
        func(s);
    }

    public static void func(String s) {
        String[] ss = s.split("\\|");
        if (ss.length == 0) {
            System.out.println(new ArrayList<>());
            return;
        }
        int[] aList = new int[0];
        try {
            String[] listA = ss[0].split(",");
            if (!"".equals(listA[0])) {
                aList = new int[listA.length];
                for (int i = 0; i < listA.length; i++) {
                    aList[i] = Integer.parseInt(listA[i].trim());
                }
            }
        } catch (Exception e) {
            aList = new int[0];
        }
        int[] bList = new int[0];
        try {
            String[] listB = ss[1].split(",");
            if (!"".equals(listB[0])) {
                bList = new int[listB.length];
                for (int i = 0; i < listB.length; i++) {
                    bList[i] = Integer.parseInt(listB[i].trim());
                }
            }
        } catch (Exception e) {
            bList = new int[0];
        }
        mergeSort(aList, bList);
    }

    public static void mergeSort(int[] aList, int[] bList) {
        int pointA = 0;
        int pointB = 0;
        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        while (pointA < aList.length && pointB < bList.length) {
            if (aList[pointA] <= bList[pointB]) {
                set.add(aList[pointA]);
                pointA++;
                continue;
            }
            if (aList[pointA] > bList[pointB]) {
                set.add(bList[pointB]);
                pointB++;
            }
        }
        while (pointA < aList.length) {
            set.add(aList[pointA]);
            pointA++;
        }
        while (pointB < bList.length) {
            set.add(bList[pointB]);
            pointB++;
        }
        System.out.println(new ArrayList<>(set));
    }

}

第二题，（题目有点忘记了，但好像是百度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
30
31
32
33
34
35
36
37
38
import java.util.Scanner;

/**
 * @author <a href="mailto:liaochunyhm@live.com">liaochuntao</a>
 * @since
 */
public class ExamTwo {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
//        int cnt = Integer.parseInt(scanner.nextLine());
//        String s = scanner.nextLine();
        String s = "1,-1,7,3";
        String[] ss = s.split(",");
        int[] array = new int[ss.length];
        for (int i = 0; i < ss.length; i ++) {
            array[i] = Integer.parseInt(ss[i]);
        }
        func(array);
    }

    public static void func(int[] array) {
        int maxDis = Integer.MIN_VALUE;
        int totalDis = 0;
        // 计算如果不去掉点的实际路程
        for (int i = 1; i < array.length; i ++) {
            totalDis += Math.abs(array[i] - array[i - 1]);
        }
        // 获取一个点，假设有A, B, C三个点，||AB| + |BC| - |AC||，其结果为0 or 正数，
        // 而这个正数就是进过B点所要多走的路程
        for (int i = 1; i + 1 < array.length; i ++) {
            maxDis = Math.max(maxDis, Math.abs(array[i] - array[i - 1]) + Math.abs(array[i + 1] - array[i]) - Math.abs(array[i + 1] - array[i - 1]));
        }
        System.out.println(totalDis - maxDis);
    }

}