安装栅栏

587. 安装栅栏

在一个二维的花园中，有一些用 (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]]
解释:

即使树都在一条直线上，你也需要先用绳子包围它们。

注意:

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
输入的整数在 0 到 100 之间。
花园至少有一棵树。
所有树的坐标都是不同的。
输入的点没有顺序。输出顺序也没有要求。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> outerTrees(vector<vector<int>>& trees) { } };

golang 解法, 执行用时: 32 ms, 内存消耗: 6.5 MB, 提交时间: 2023-03-09 15:22:16

func cross(p, q, r []int) int {
    return (q[0]-p[0])*(r[1]-q[1]) - (q[1]-p[1])*(r[0]-q[0])
}

func outerTrees(trees [][]int) [][]int {
    n := len(trees)
    if n < 4 {
        return trees
    }

    // 按照 x 从小到大排序，如果 x 相同，则按照 y 从小到大排序
    sort.Slice(trees, func(i, j int) bool { a, b := trees[i], trees[j]; return a[0] < b[0] || a[0] == b[0] && a[1] < b[1] })

    hull := []int{0} // hull[0] 需要入栈两次，不标记
    used := make([]bool, n)
    // 求凸包的下半部分
    for i := 1; i < n; i++ {
        for len(hull) > 1 && cross(trees[hull[len(hull)-2]], trees[hull[len(hull)-1]], trees[i]) < 0 {
            used[hull[len(hull)-1]] = false
            hull = hull[:len(hull)-1]
        }
        used[i] = true
        hull = append(hull, i)
    }
    // 求凸包的上半部分
    m := len(hull)
    for i := n - 2; i >= 0; i-- {
        if !used[i] {
            for len(hull) > m && cross(trees[hull[len(hull)-2]], trees[hull[len(hull)-1]], trees[i]) < 0 {
                used[hull[len(hull)-1]] = false
                hull = hull[:len(hull)-1]
            }
            used[i] = true
            hull = append(hull, i)
        }
    }
    // hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0]
    hull = hull[:len(hull)-1]

    ans := make([][]int, len(hull))
    for i, idx := range hull {
        ans[i] = trees[idx]
    }
    return ans
}

python3 解法, 执行用时: 100 ms, 内存消耗: 15.2 MB, 提交时间: 2023-03-09 15:21:41

'''
andrew 算法
'''
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        n = len(trees)
        if n < 4:
            return trees

        # 按照 x 从小到大排序，如果 x 相同，则按照 y 从小到大排序
        trees.sort()

        hull = [0]  # hull[0] 需要入栈两次，不标记
        used = [False] * n
        # 求凸包的下半部分
        for i in range(1, n):
            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:
                used[hull.pop()] = False
            used[i] = True
            hull.append(i)
        # 求凸包的上半部分
        m = len(hull)
        for i in range(n - 2, -1, -1):
            if not used[i]:
                while len(hull) > m and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:
                    used[hull.pop()] = False
                used[i] = True
                hull.append(i)
        # hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0]
        hull.pop()

        return [trees[i] for i in hull]

python3 解法, 执行用时: 220 ms, 内存消耗: 15.7 MB, 提交时间: 2023-03-09 15:20:51

'''
graham scan
'''
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        def distance(p: List[int], q: List[int]) -> int:
            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])

        n = len(trees)
        if n < 4:
            return trees

        # 找到 y 最小的点 bottom
        bottom = 0
        for i, tree in enumerate(trees):
            if tree[1] < trees[bottom][1]:
                bottom = i
        trees[bottom], trees[0] = trees[0], trees[bottom]

        # 以 bottom 原点，按照极坐标的角度大小进行排序
        def cmp(a: List[int], b: List[int]) -> int:
            diff = - cross(trees[0], a, b)
            return diff if diff else distance(trees[0], a) - distance(trees[0], b)
        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))

        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序
        r = n - 1
        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:
            r -= 1
        l, h = r + 1, n - 1
        while l < h:
            trees[l], trees[h] = trees[h], trees[l]
            l += 1
            h -= 1

        stack = [0, 1]
        for i in range(2, n):
            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素
            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:
                stack.pop()
            stack.append(i)
        return [trees[i] for i in stack]

java 解法, 执行用时: 10 ms, 内存消耗: 43.4 MB, 提交时间: 2023-03-09 15:18:02

class Solution {
    public int[][] outerTrees(int[][] trees) {
        int n = trees.length;
        if (n < 4) {
            return trees;
        }
        int leftMost = 0;
        for (int i = 0; i < n; i++) {
            if (trees[i][0] < trees[leftMost][0] || 
                (trees[i][0] == trees[leftMost][0] && 
                 trees[i][1] < trees[leftMost][1])) {
                leftMost = i;
            }
        }

        List<int[]> res = new ArrayList<int[]>();
        boolean[] visit = new boolean[n];
        int p = leftMost;
        do {
            int q = (p + 1) % n;
            for (int 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 (int i = 0; i < n; i++) {
                if (visit[i] || i == p || i == q) {
                    continue;
                }
                if (cross(trees[p], trees[q], trees[i]) == 0) {
                    res.add(trees[i]);
                    visit[i] = true;
                }
            }
            if  (!visit[q]) {
                res.add(trees[q]);
                visit[q] = true;
            }
            p = q;
        } while (p != leftMost);
        return res.toArray(new int[][]{});
    }

    // 叉积判断, p为原点, pq和qr的向量积， >0, 则pqr逆时针；=0，则pqr三点一线；<0，pqr顺时针
    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]);
    }
}

golang 解法, 执行用时: 28 ms, 内存消耗: 6.5 MB, 提交时间: 2023-03-09 15:11:36

/**
 * 以最左侧的点为原点, 逆时针找
 */
func cross(p, q, r []int) int {
    return (q[0]-p[0])*(r[1]-q[1]) - (q[1]-p[1])*(r[0]-q[0])
}

func outerTrees(trees [][]int) (ans [][]int) {
    n := len(trees)
    if n < 4 {
        return trees
    }

    leftMost := 0
    for i, tree := range trees {
        if tree[0] < trees[leftMost][0] || (tree[0] == trees[leftMost][0] && tree[1] < trees[leftMost][1]) {
            leftMost = i
        }
    }

    vis := make([]bool, n)
    p := leftMost
    for {
        q := (p + 1) % n
        for r, tree := range trees {
            // 如果 r 在 pq 的右侧，则 q = r
            if cross(trees[p], trees[q], tree) < 0 {
                q = r
            }
        }
        // 是否存在点 i, 使得 p q i 在同一条直线上
        for i, b := range vis {
            if !b && i != p && i != q && cross(trees[p], trees[q], trees[i]) == 0 {
                ans = append(ans, trees[i])
                vis[i] = true
            }
        }
        if !vis[q] {
            ans = append(ans, trees[q])
            vis[q] = true
        }
        p = q
        if p == leftMost {
            break
        }
    }
    return
}

python3 解法, 执行用时: 860 ms, 内存消耗: 15.4 MB, 提交时间: 2023-03-09 15:08:59

'''
Jarvis 凸包算法
'''
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        n = len(trees)
        if n < 4:
            return trees

        leftMost = 0
        for i, tree in enumerate(trees):
            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):
                leftMost = i

        ans = []
        vis = [False] * n
        p = leftMost
        while True:
            q = (p + 1) % n
            for r, tree in enumerate(trees):
                # // 如果 r 在 pq 的右侧，则 q = r
                if cross(trees[p], trees[q], tree) < 0:
                    q = r
            # 是否存在点 i, 使得 p q i 在同一条直线上
            for i, b in enumerate(vis):
                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:
                    ans.append(trees[i])
                    vis[i] = True
            if not vis[q]:
                ans.append(trees[q])
                vis[q] = True
            p = q
            if p == leftMost:
                break
        return ans

python3 解法, 执行用时: 112 ms, 内存消耗: 15.7 MB, 提交时间: 2023-03-09 15:00:58

from cmath import phase, pi

def phase_by_ori(o: complex, q: complex, p: complex):
    return (phase(p - q) - phase(q - o) + pi) % (2 * pi) - pi
    
def AndrewHull(hull, r):
    hull.append(r)
    while len(hull) >= 3 and phase_by_ori(*hull[-3:]) < 0: hull.pop(-2)
    return hull
    
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        trees = [complex(*t) for t in sorted(trees)]
        return [[int(t.real), int(t.imag)] for t in set(reduce(AndrewHull, trees, []) + reduce(AndrewHull, reversed(trees), []))]

上一题

下一题

详情