记两个面试算法题

在面试中遇到的两个题,记录一下。

我比较菜,所以可能都不是bug-free的最优解。

环形数组取最大

题目

给定一个环状数组(长度未知,环状的意思是数组里第一个数和最后一个数相邻),中间包含的数字全是正整数,取出其中的一些数字,但不能取出任何连续两个位置的数字。求取出的数字的和的最大值。

示例:[2, 3, 2, 1]返回4,[2, 2, 3,1] 返回5

要求时间复杂度O(N) 语言任选

分析

其实就是从数组中选出数字,而且还不能相邻。选完一个数字,紧随的数字就自动不能选,不禁让我想到了动态规划。从题目上面的例子中,我先从2,3中选,当然选3啦;之后后面的2自动不能选,最后选个1。选择空间逐渐变小。这是我一开始的想法。

后来一想又不行,比如[1,3,1000,1],这样子的情况会把1000漏掉。于是我把判断的bin设成3,这样判断的时候判断1+1000>3,所以选1和1000。当然,要考虑不同的case,起始也会影响到选择,比如[1,3,1000,9000],所以要把整个过程在从3开始再重复一遍。最后选最大的,就有了下面的代码:

我的解

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
public static void main(String[] args) {
int a[] = {1, 1, 1, 1000, 1, 1, 1, 1};

System.out.println(max2(pickNumber(a, 0, a.length - 1), pickNumber(a, 1, a.length - 1)));

}

public static int max2(int a, int b) {
return a > b ? a : b;
}

public static int max3(int a, int b, int c) {
return ((a > b ? a : b) > c) ? (a > b ? a : b) : c;
}

public static int pickNumber(int[] nums, int start, int end) {
if (end < start) return 0;
if (end == start) return nums[start];
if (end - start == 1)
return nums[start] > nums[end] ? nums[start] : nums[end];
if (end - start == 2) {
if (start == 0) return max3(nums[0], nums[1], nums[2]);
if (nums[start] + nums[end] > nums[start + 1])
return nums[start] + nums[end];
else
return nums[start + 1];
}

if (nums[start] + nums[start + 2] > nums[start + 1]) {
if (start + 4 > end) return (nums[start] + nums[start + 2]);
else {
if (start == 0) return (nums[start] + nums[start + 2]) + pickNumber(nums, start + 4, end - 1);
else return (nums[start] + nums[start + 2]) + pickNumber(nums, start + 4, end);
}
} else {
if (start + 3 > end) return nums[start + 1];
else return nums[start + 1] + pickNumber(nums, start + 3, end);
}
}

两平面三角形最短距离

题目

给出两个二维平面的三角形,每个三角形通过3个点表示,每个点通过2个float表示,求两个三角形之间的最短距离,两个三角形之间的最短距离定义为:在两个三角形内部(包含边界)任取一个点,这两个点之间的最短距离。语言任意,不允许使用计算几何库。

分析

短小精悍的题,但很麻烦,因为不能用库。如果能用解析几何相关的库的话,那么向量的计算就会简单很多。

平面上两个三角形一共有几种情况:相交、相离、包含。其中后两者计算最短距离是相似的,都是只要计算顶点到边的最短距离就行了,再挑一个最短的。相交虽然结果为0,但判断稍微麻烦一些,一种情况是一个三角形有至少一个顶点在另一个三角形内,边必然相交;另一种情况是类似六芒星,即没有顶点在另一个三角形内。

所有的判断基本都需要用到向量的知识,主要是内积和外积。

判断顶点是否在三角形内,用到了向量外积,两向量叉乘,方向右手螺旋,根据符号来判断是否在同一侧,进而可以判断点是否在三角形内。这个我参考了这里

在判断完成之后,如果没有顶点在三角形内,要考虑另一个情况,即边相交,但顶点都不在三角形内的情况。因为之前我们已经把顶点在形内的情况给排除了,这种情况只会是有六个交点,因此只要判断是否有边相交就行了。

判断边相交,我参考了这里的推导结果。其中要考虑平行的情况,平行就是叉乘为0了。

随后计算点到线段的最短距离。有几种不同的情况,可以用解析的方法计算。StackOverflow上有相应解法。

当然,如果自己把向量等计算用类写的话会简便很多,当然,在面试里还是少造轮子。

我的解答

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.*;

public class Main {


public static void main(String[] args) {
// Test case here
// System.out.println();
}

public static double point2seg(double x, double y, double x1, double y1, double x2, double y2) {
// Use vector to calculate the
// distance from a point to a line segment

double v1_x = x - x1;
double v1_y = y - y1;
double v2_x = x2 - x1;
double v2_y = y2 - y1;

double dot = v2_x * v1_x + v2_y * v1_y;
if (dot <= 0) return Math.sqrt(v1_x * v1_x + v1_y * v1_y);

double v2_len = v2_x * v2_x + v2_y * v2_y;
if (dot >= v2_len) return Math.sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2));

double r = dot / v2_len;
double px = x1 + (x2 - x1) * r;
double py = y1 + (y2 - y1) * r;
return Math.sqrt((x - px) * (x - px) + (py - y1) * (py - y1));
}

public static double cross_product(double x1, double y1, double x2, double y2) {
// Cross product of two vectors
return x1 * y2 - x2 * y1;
}

public static boolean sameside(double x1, double y1, double x2, double y2,
double ax, double ay, double bx, double by) {
// Whether two points exist in the
// same side of a segment
double cp1 = cross_product(bx - ax, by - ay, x1 - ax, y1 - ay);
double cp2 = cross_product(bx - ax, by - ay, x2 - ax, y2 - ay);
if (cp1 * cp2 >= 0) return true;
else return false;
}

public static boolean point_in_triangle(double px, double py,
double ax, double ay,
double bx, double by,
double cx, double cy) {
// Whether or not a point lies in a triangle
if (sameside(px, py, ax, ay, bx, by, cx, cy) &&
sameside(px, py, bx, by, ax, ay, cx, cy) &&
sameside(px, py, cx, cy, bx, by, ax, ay)) {
return true;
} else
return false;
}

public static double min3(double a, double b, double c) {
// Minimum of three numbers
return Math.min(Math.min(a, b), c);
}

public static boolean lines_intersect(double x1, double y1, double x2, double y2,
double x3, double y3, double x4, double y4) {
// Whether two line segments intersect or not
double v1_x = x2 - x1;
double v1_y = y2 - y1;
double v2_x = x4 - x3;
double v2_y = y4 - y3;

// if parallel
if (cross_product(v1_x, v1_y, v2_x, v2_y) == 0) {
return false;
}

// Otherwise
double s = (-v1_y * (x1 - x3) + v1_x * (y1 - y3)) / cross_product(v1_x, v1_y, v2_x, v2_y);
double t = (v2_x * (y1 - y3) - v2_y * (x1 - x3)) / cross_product(v1_x, v1_y, v2_x, v2_y);

if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
return true;
else
return false;
}

public static double getShortestDist(double ax, double ay, double bx, double by, double cx, double cy,
double dx, double dy, double ex, double ey, double fx, double fy) {

// If two triangles intersect and not include each other
if ((point_in_triangle(ax, ay, dx, dy, ex, ey, fx, fy) ||
point_in_triangle(bx, by, dx, dy, ex, ey, fx, fy) ||
point_in_triangle(cx, cy, dx, dy, ex, ey, fx, fy)) &&
!(point_in_triangle(ax, ay, dx, dy, ex, ey, fx, fy) &&
point_in_triangle(bx, by, dx, dy, ex, ey, fx, fy) &&
point_in_triangle(cx, cy, dx, dy, ex, ey, fx, fy)))
return 0;

if ((point_in_triangle(dx, dy, ax, ay, bx, by, cx, cy) ||
point_in_triangle(ex, ey, ax, ay, bx, by, cx, cy) ||
point_in_triangle(fx, fy, ax, ay, bx, by, cx, cy)) &&
!(point_in_triangle(dx, dy, ax, ay, bx, by, cx, cy) &&
point_in_triangle(ex, ey, ax, ay, bx, by, cx, cy) &&
point_in_triangle(fx, fy, ax, ay, bx, by, cx, cy)))
return 0;

// Check if two intersect without points in each other
// If so, each edge must intersect with two edges
if (lines_intersect(ax, ay, bx, by, dx, dy, ex, ey) ||
lines_intersect(ax, ay, bx, by, dx, dy, fx, fy) ||
lines_intersect(ax, ay, bx, by, ex, ey, fx, fy))
return 0;


// If not
double A = min3(point2seg(ax, ay, dx, dy, ex, ey),
point2seg(ax, ay, dx, dy, fx, fy),
point2seg(ax, ay, fx, fy, ex, ey));
double B = min3(point2seg(bx, by, dx, dy, ex, ey),
point2seg(bx, by, dx, dy, fx, fy),
point2seg(bx, by, fx, fy, ex, ey));
double C = min3(point2seg(cx, cy, dx, dy, ex, ey),
point2seg(cx, cy, dx, dy, fx, fy),
point2seg(cx, cy, fx, fy, ex, ey));

return min3(A, B, C);
}
}
打赏支持一下~