- 安装栅栏
在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
示例 1:
输入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[4,2],[3,3],[2,4]]
示例 2:
输入: [[1,2],[2,2],[4,2]]
输出: [[1,2],[2,2],[4,2]]
Java代码：
class Solution {
// 要先了解 a x b 叉积的定义 这个和我们高中学的 向量积 是一个意思
// 我们主要是通过 叉积 来求 三叶姐所说的 以 ab 这条边开始
//判断到c点 ac是在ab的顺时针还是逆时针方向
// subtraction(b,a) 求的是 向量 ab subtraction(c,a) 求的是 向量 ac
int[] subtraction(int[] a , int[] b){
return new int[]{a[0] - b[0] , a[1] - b[1]};
}
// 叉乘计算一般是空间中的 xyz 但是 在平面2d 中我们只需要把每个三维坐标中压成平面 使得 z 变为 0
// 那么叉乘公式定义获得到的值 k 就是 k =a.x*b.y-b.x*a.y，我们可以通过这个k值得到很多有用的性质
// 就比如这里的 如果k>0时，那么a正旋转到b的角度为<180°，如果k<0，那么a正旋转到b的角度为>180°,如果k=0 那么a，b向量平行。
double cross(int[] a ,int b[]){
return a[0] * b[1] - a[1] * b[0];
}
// 通过平面两点向量叉乘 判断当前 ac 向量是在顺时针方向还是逆时针方向
double getArea(int[] a, int[] b ,int[] c){
return cross(subtraction(b,a),subtraction(c,b));
}
public int[][] outerTrees(int[][] trees) {
// 先按照 x 排序 再按照 y 排序
Arrays.sort(trees,(a,b)->{
return a[0] == b[0] ? a[1] - b[1] : a[0]-b[0];
});
int n = trees.length;
// 三叶姐姐中的 tp 实际上是用于记录 栈顶位置 也是用来记录当前栈顶元素下一位的下标位置
int top = 0 ;
// 开了一个 n + 10 的 stack 用于记录
int[] stk = new int[n+10];
// 用于记录使用过的点
boolean[]vis = new boolean[n+10];
// 起点不进行标记 及此时 stk[1] = 0; stk[0] 不进行标记
stk[++top] = 0;
for (int i = 1;i<n;i++){
// 判断当前这个 c 点哈 ，三叶姐姐文中的那个 c点
int[] c = trees[i];
// 如果此时栈中的元素大于两个的时候 先说一下 三叶姐姐画的蓝色分割线下面代表的部分
while (top >= 2){
// 这个是 栈顶元素b的下一个元素a 也就是三叶姐姐文中提到的 `栈顶元素的下一位为 a`
int[] a = trees[stk[top-1]];
// 栈顶元素 b
int[] b = trees[stk[top]];
// 如果此时 ab 向量 与 bc 向量叉积小于0 说明 ab正旋转到bc的角度为>180°
// 说白了就是ac在ab的顺时针方向上 ab 在 bc 的逆时针方向上
// 因为 在下面部分当中 ac 如果在ab的顺时针方向 则说明ac 所囊括的数据一定比 ab多
// 所以我们需要删除 ab 保留 ac 作为外边界
// 此时stk[top]是b的下标
// vis[stk[top--]] 代表的是 删除 ab 这条线后 b 点就当做未被访问过得点了
if (getArea(a,b,c) < 0)vis[stk[top--]] = false;
// 反之在其逆时针方向上 直接将这个 c点加入其中 跳出当前循环即可
else break;
}
// 加入当前这个点在栈中位置
stk[++top] = i;
// 标记当前 c 点被访问过了
vis[i] = true;
}
// 栈中元素个数 说明上部分保留的点的个数
int size = top;
// 从右边往左边遍历 说明这是寻找分割线划线后的上面部分也就是说明第二部分
for (int i = n-1;i>=0;i--){
// 当该点已经被访问过了，就直接判断下个点去了
if (vis[i]) continue;
int [] c = trees[i];
// 三叶姐姐说的 逻辑条件变更为 `需要将上述「栈顶元素不少于 2 个」的逻辑替换为「栈顶元素大于 m 个」`
while (top > size){
// 老样子 从栈中取点
int[] a = trees[stk[top-1]];
int[] b = trees[stk[top]];
// 老样子不解释啦
if (getArea(a,b,c) < 0){
// top--;
vis[stk[top--]] = false;
}else break;
}
// 将该点入栈标记这条边是当前符合条件的
stk[++top] = i;
// 老样子标记该点已经被访问过了 其实可以省略 因为后面不会再用到该点了
vis[i] = true;
}
// 栈中所记录的下标就是 符合条件的所有点所围成的凸包的最小周长
int [][] res = new int[top-1][2];
// 从1开始因为 0 之前没有记录哦~
for (int i = 1; i<top;i++){
res[i-1] = trees[stk[i]];
}
// 返回结果
return res;
}
}
Java代码2：
class Solution {
public int[][] outerTrees(int[][] trees) {
int n = trees.length;
if (n < 4) {
return trees;
}
/* 按照 x 大小进行排序，如果 x 相同，则按照 y 的大小进行排序 */
Arrays.sort(trees, (a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
List<Integer> hull = new ArrayList<Integer>();
boolean[] used = new boolean[n];
/* hull[0] 需要入栈两次，不进行标记 */
hull.add(0);
/* 求出凸包的下半部分 */
for (int i = 1; i < n; i++) {
while (hull.size() > 1 && cross(trees[hull.get(hull.size() - 2)], trees[hull.get(hull.size() - 1)], trees[i]) < 0) {
used[hull.get(hull.size() - 1)] = false;
hull.remove(hull.size() - 1);
}
used[i] = true;
hull.add(i);
}
int m = hull.size();
/* 求出凸包的上半部分 */
for (int i = n - 2; i >= 0; i--) {
if (!used[i]) {
while (hull.size() > m && cross(trees[hull.get(hull.size() - 2)], trees[hull.get(hull.size() - 1)], trees[i]) < 0) {
used[hull.get(hull.size() - 1)] = false;
hull.remove(hull.size() - 1);
}
used[i] = true;
hull.add(i);
}
}
/* hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0] */
hull.remove(hull.size() - 1);
int size = hull.size();
int[][] res = new int[size][2];
for (int i = 0; i < size; i++) {
res[i] = trees[hull.get(i)];
}
return res;
}
public int cross(int[] p, int[] q, int[] r) {
return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
}
}
JavaScript代码：
var outerTrees = function(trees) {
const n = trees.length;
if (n < 4) {
return trees;
}
let leftMost = 0;
for (let i = 0; i < n; i++) {
if (trees[i][0] < trees[leftMost][0]) {
leftMost = i;
}
}
const res = [];
const visit = new Array(n).fill(0);
let p = leftMost;
do {
let q = (p + 1) % n;
for (let r = 0; r < n; r++) {
/* 如果 r 在 pq 的右侧，则 q = r */
if (cross(trees[p], trees[q], trees[r]) < 0) {
q = r;
}
}
/* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
for (let i = 0; i < n; i++) {
if (visit[i] || i === p || i === q) {
continue;
}
if (cross(trees[p], trees[q], trees[i]) === 0) {
res.push(trees[i]);
visit[i] = true;
}
}
if (!visit[q]) {
res.push(trees[q]);
visit[q] = true;
}
p = q;
} while (p !== leftMost);
return res;
}
const cross = (p, q, r) => {
return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
};
C代码：
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
struct node {
int x;
int y;
int used;
};
int findTop(struct node *now, struct node *peer, struct node *nodes, int cnt, int right) {
int pos = -1;
float k;
float maxk;
//分割线的k和b (直线方程kx + b)
float basek = (peer->y - now->y) * 1.0 / (peer->x - now->x);
float baseb = now->y - basek * now->x;
for (int i = 0; i < cnt; i++) {
//已使用或垂直，不可取
if (nodes[i].used || now->x == nodes[i].x) {
continue;
}
//计算斜率
k = (nodes[i].y - now->y) * 1.0 / (nodes[i].x - now->x);
// 右移，在基准线以下
if (right && (basek * nodes[i].x + baseb) > nodes[i].y * 1.0) {
continue;
}
//左移，在基准线以上
if (!right && (basek * nodes[i].x + baseb) < nodes[i].y * 1.0) {
continue;
}
//取最大斜率
if (pos == -1 || maxk < k) {
pos = i;
maxk = k;
}
//最大斜率相同时，可能同一线上多个点
if (maxk == k) {
if (right && nodes[pos].x < nodes[i].x) {
//往右，取最大的
pos = i;
} else if(!right && nodes[pos].x > nodes[i].x) {
//往左，取最小的
pos = i;
}
}
}
//标识最大斜率上的点
for (int i = 0; i < cnt && pos != -1; i++) {
if (nodes[i].used) {
continue;
}
k = (nodes[i].y - now->y) * 1.0 / (nodes[i].x - now->x);
if (maxk == k) {
nodes[i].used = 1;
}
}
return pos;
}
int** outerTrees(int** points, int pointsSize, int* pointsColSize, int* returnSize, int** returnColumnSizes){
struct node *nodes = NULL;
// 左边界上下点
int leftTop = -1;
int leftBot = -1;
//右边界上下点
int rightBot = -1;
int rightTop = -1;
int *outColSize = NULL;
int **out = 0;
//左右边界横坐标值
int minx;
int maxx;
int cnt = 0;
if (points == NULL || *points == NULL || pointsColSize == NULL || returnSize == NULL || returnColumnSizes == NULL) {
return NULL;
}
nodes = (struct node *)malloc(sizeof(struct node) * pointsSize);
if (nodes == NULL) {
return NULL;
}
memset(nodes, 0, sizeof(struct node) * pointsSize);
minx = points[0][0];
maxx = minx;
// 查找左右边界横坐标
for (int i = 0; i < pointsSize; i++) {
nodes[i].x = points[i][0];
nodes[i].y = points[i][1];
if (nodes[i].x < minx) {
minx = nodes[i].x;
} else if(nodes[i].x > maxx) {
maxx = nodes[i].x;
}
}
//查找位于左右边界上的极点
for (int i = 0; i < pointsSize; i++) {
if (minx == points[i][0]) {
nodes[i].used = 1;
if (leftTop == -1 || nodes[i].y > nodes[leftTop].y){
leftTop = i;
}
if (leftBot == -1 || nodes[i].y < nodes[leftBot].y){
leftBot = i;
}
}
if (maxx == points[i][0]) {
nodes[i].used = 1;
if (rightBot == -1 || nodes[i].y < nodes[rightBot].y){
rightBot = i;
}
if (rightTop == -1 || nodes[i].y > nodes[rightTop].y){
rightTop = i;
}
}
}
//如果横坐标相同，必定一条线上，全输出
if (minx == maxx) {
for (int i = 0; i < pointsSize; i++) {
nodes[i].used = 1;
}
} else {
//循环处理
for (int i = 0; i < pointsSize && leftTop != -1; i++) {
//左上和右上极点连线后，从左上极点开始找位于线上方且最大斜率的点
leftTop = findTop(nodes + leftTop, nodes + rightTop, nodes, pointsSize, 1);
}
for (int i = 0; i < pointsSize && rightBot != -1; i++) {
//右下和左上极点连线后，从右下极点开始找位于线下方且最大斜率的点
rightBot = findTop(nodes + rightBot, nodes + leftBot, nodes, pointsSize, 0);
}
}
for (int i = 0; i < pointsSize; i++) {
if (nodes[i].used) {
cnt++;
}
}
*returnSize = cnt;
out = malloc(sizeof(int *) * cnt);
memset(out, 0, sizeof(int *) * cnt);
outColSize = malloc(sizeof(int) * cnt);
memset(outColSize, 0, sizeof(int) * cnt);
for(int i = 0; i < cnt; i++) {
outColSize[i] = 2;
}
*returnColumnSizes = outColSize;
for (int i = 0, j = 0; i < pointsSize; i++) {
if (!nodes[i].used) {
continue;
}
out[j] = malloc(sizeof(int) * 2);
out[j][0] = nodes[i].x;
out[j][1] = nodes[i].y;
j++;
}
free(nodes);
return out;
}
python3代码：
class Solution:
def outerTrees(self, points: List[List[int]]) -> List[List[int]]:
def oriented(p, q, r):
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if len(points) < 4:
return points
points.sort() # 按照x值正序排列
hull = [points[0], points[1]]
for i in range(2, len(points)):
r = points[i]
while len(hull) >= 2 and oriented(hull[-2], r, hull[-1]) < 0:
hull.pop()
hull.append(r)
m = set()
for p in hull: # 将已经添加的树储存到集合中
m.add(tuple(p))
points = points[::-1] # 按照x值逆序排列
for i in range(1, len(points)):
r = points[i]
while len(hull) >= 2 and oriented(hull[-2], r, hull[-1]) < 0:
hull.pop()
if tuple(r) not in m:
hull.append(r)
m.add(tuple(r))
return hull
作者：KJ.JK
本文仅用于交流学习，未经作者允许，禁止转载，更勿做其他用途，违者必究。
文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）