写在前面
题目来自于阿里2018编程测验中的算法题,时间是30分钟。其实要在30分钟内做出这道题,还是有一定难度的,由于有整体有几道算法题,这里记录下自己见到的题目。
题目一:物流派送员送快递最短路径问题
题目描述
如下图,某物流派送员p,需要给 a、b、c、d. 4个快递点派送包裹,请问派送员需要选择什么样的路线,才能完成最短路程的派送。假设如图派送员的起点坐标(0,0),派送路线只能沿着图中的方格边行驶,每个小格都是正方形,且边长为1,如p到d的距离就是4。随机输入n个派送点坐标,求输出最短派送路线值(从起点开始完成n个点派送并回到起始点的距离)。

示例
输入
输出
解题思路
这道题按照暴力的解法的话,可以算出送货点路径的全排列,然后再取最小值就可以了。所以这题的关键在于给定一个数组,计算它的全排列。
计算全排列代码在较多地方都能用到,需要掌握。
解题代码
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
| 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; } }
|