Fork me on GitHub

ali的内推笔试算法题目

摘要:阿里内推笔试题


题目大概是这样子滴:
现在你是一个快递员,你正处在坐标系中得原地地方 (0, 0).
等待n个需要投递物品的用户的 坐标,那么需要你求出去这n个地方把快递全部取完,花费的最小路径, 你只能沿着坐标系中的方格线行走。

例如 用户输入 2

(1, 1)
(2, 2)
那么你的最优路线就是 (0,0)-->(0,1)-->(1,1)-->(2,1)-->(2,2)
distance = 4
肯定不会先去 (2,2) 再去 (1,1)这个点 (那样的路径distance = 6),显然不是我们想要的。

基本一眼就可以知道,这是DFS+backtracking的题目。
我们有n个点需要去到达, 那么所有的情况就是 nn-1n-2*…..1 n!种情况了。

Solution1 暴力

求出所有的路径序列,然后把所有的序列的路径长求其最小值,就是我们的答案。
O(n) = n^n

dfs + backtranking

我们可以先goto 任意一个点,计算出到达此点的sum_distance,再以此点位起点,遍历没有没被访问过的点

  1. 所有的点都访问了, return 回溯
  2. 加上该点 sum_distance > 之前的sum_distance 回溯
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
public class Main {
// start point
static final Point START = new Point(0,0);
static int minpath = Integer.MAX_VALUE;
public static int calculate(Point start, Point[] points, int sum, int count){
if (count == points.length){
minpath = Math.min(minpath, sum +start.distance(START));
return minpath;
}
for (int i = 0; i<points.length; i++) {
if (points[i].visited == false) {
sum += points[i].distance(start);
if (sum < minpath) {
points[i].visited = true;
calculate(points[i], points, sum, count+1);
}
sum -= points[i].distance(start);
points[i].visited = false;
}
}
return minpath;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int pnum = Integer.parseInt(input.nextLine().trim());
Point[] points = new Point[pnum];
for (int i = 0; i<pnum; i++){
String[] locations = input.nextLine().trim().split(",");
points[i] = new Point(Integer.parseInt(locations[0]), Integer.parseInt(locations[1]));
}
int min = calculate(START, points, 0, 0);
System.out.println(min);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Point {
int px;
int py;
boolean visited;
public Point(int px, int py) {
this.px = px;
this.py = py;
this.visited = false;
}
public int distance(Point p) {
return Math.abs(px - p.px) + Math.abs(py - p.py);
}
}
坚持原创技术分享,您的支持将鼓励我继续创作!