阿里2018编程测验算法题

写在前面

题目来自于阿里2018编程测验中的算法题，时间是30分钟。其实要在30分钟内做出这道题，还是有一定难度的，由于有整体有几道算法题，这里记录下自己见到的题目。

题目一:物流派送员送快递最短路径问题

题目描述

如下图，某物流派送员p，需要给 a、b、c、d. 4个快递点派送包裹，请问派送员需要选择什么样的路线，才能完成最短路程的派送。假设如图派送员的起点坐标(0,0)，派送路线只能沿着图中的方格边行驶，每个小格都是正方形，且边长为1，如p到d的距离就是4。随机输入n个派送点坐标，求输出最短派送路线值（从起点开始完成n个点派送并回到起始点的距离）。

示例

输入

4
2,2
2,8
4,4
7,2

输出

30

解题思路

这道题按照暴力的解法的话，可以算出送货点路径的全排列，然后再取最小值就可以了。所以这题的关键在于给定一个数组，计算它的全排列。

计算全排列代码在较多地方都能用到，需要掌握。

解题代码

public class Main {
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int dis(Point p) {
            return Math.abs(x - p.x) + Math.abs(y - p.y);
        }
    }

    static final Point start = new Point(0, 0);
    static int minPath = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            points[i] = new Point(Integer.valueOf(line.split(",")[0]), Integer.valueOf(line.split(",")[1]));
        }
        System.out.println(perumation(points, 0));
    }

    private static int perumation(Point[] points, int idx) {
        if (idx == points.length) {
            int sum = points[0].dis(start);
            for (int i = 1; i < points.length; i++) {
                sum += points[i-1].dis(points[i]);
            }
            sum += points[points.length-1].dis(start);
            minPath = Math.min(minPath, sum);
            return minPath;
        }
        for (int i = idx; i < points.length; i++) {
            swap(points, idx, i);
            perumation(points, idx+1);
            swap(points, idx, i);
        }
        return minPath;
    }

    private static void swap(Point[] points, int i, int j) {
        if (i == j) return;
        Point temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }
}