第一部分

选择题：线性代数，排列组合，概率题，代码题判断题，Java语言基础题

第二部分

算法题三道，ACM模式，可用IDE

第一题

给N个杯子倒扣在桌面上，在第X个杯子中有一个球，移动杯子里面的球会跟着移动，经过K次移动，求最后那个球在第几个杯子中？

输入：

3 2
3
1 3
3 2 
1 2

输出

3

（输入的意思是有3个杯子，球在第2个杯子中，经过三次移动，第一次移动为第一个与第三个杯子交换位置，第二次移动为第三个杯子与第二个杯子交换，第三次移动为第一个杯子与第二个杯子交换。最终输出3，意思为球最终在第三个杯子中）

我的代码：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int K = sc.nextInt();
        int[] cups = new int[N + 1];
        cups[X] = 1;
        for (int i = 0; i < K; i++) {
            int cup1 = sc.nextInt();
            int cup2 = sc.nextInt();
            swap(cups,cup1,cup2);
        }
        for (int i = 1; i <= cups.length; i++) {
            if (cups[i] == 1) {
                System.out.println(i);
                return;
            }
        }
    }

    private static void swap(int[] cups, int i, int j) {
        int tmp = cups[i];
        cups[i] = cups[j];
        cups[j] = tmp;
    }

第二题

有n个基站，我们还可以多设置k个基站，问我们怎么设置基站能够使噪音最小，返回最小噪音。

输入：

3 1
1 4 5

意思为已经有三个基站，我们还可以再设置一个基站。那么目前噪音为max{4-1，5-4} = 3

那么我们在1和4之间建立基站2，那么噪音为max{2-1，4-2，5-4} = 2，那么最终返回2

输出

2

我的想法是将这些基站位置放到int数组中，循环k次设置多出来的基站，每次我们寻找基站之间的距离最远的在其中间设置一个基站。这样k次之后得到噪音就是所求。

之前我一直纠结怎么存放数据，是不是要放到TreeMap中，之后想到用数组，然后排序一下就行了。

没时间提交了，也不知道对不对

    static int n;
    static int k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        int[] zhan = new int[n + k];
        for (int i = 0; i < n; i++) {
            zhan[i] = sc.nextInt();
        }
        int max = 0;
        for (int i = 0; i <= k; i++) {
            max = maxZao(zhan);
        }
        System.out.println(max);
    }

    private static int maxZao(int[] zhan) {
        Arrays.sort(zhan);
        int max = 0;
        int index=0;
        for (int i = 1; i < zhan.length; i++) {
            if (zhan[i] - zhan[i - 1] > max) {
                max = zhan[i] - zhan[i - 1];
                index = i;
            }
        }
        k--;
        zhan[n++] = (zhan[index] - zhan[index - 1])/2;
        return max;
    }

第三题

给一个n*m的迷宫，'.'表示道路，'#'表示障碍，我们要从左上角走到右下角，走的过程中我们可以上下左右都能走（当然不能超出范围），我们可以将障碍变成道路，我们只能在道路上走，问我们最少需要将多少障碍变成道路才能从左上走到右下呢？

输入

3 3
.##
#..
.#.

输出

1

我们将第二行第一列的障碍变成道路，就行了

输入

3 3
.##
#.#
.#.

输出

2

可以将第二行第一列和第三列变成道路

我不会做。。。因为它可以上下左右都能走，不是只能向下和向右，不会做，求大佬代码~

我的代码栈溢出了。。。。。:cry:

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] mi = new char[n][m];
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < s.length(); j++) {
                mi[i][j] = s.charAt(j);
            }
        }
        walk(mi, 0, 0, 0);
    }


    static int res = Integer.MAX_VALUE;
    static int[][] dd = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    public static void walk(char[][] mi, int i, int j, int barrier) {
        if (i < 0 || j >= mi[0].length|| i >= mi.length || j < 0) {
            return;
        }
        if (mi[i][j] == '#') {
            barrier++;
        }
        if (i == mi.length && j == mi[0].length) {
            res = Math.min(res, barrier);
        }
        for (int k = 0; k < dd.length; k++) {
            int newX = i + dd[k][0];
            int newY = j + dd[k][1];
            walk(mi, newX, newY, barrier);
        }
    }