游乐园的迷宫

LCP 15. 游乐园的迷宫

小王来到了游乐园，她玩的第一个项目是模拟推销员。有一个二维平面地图，其中散布着 N 个推销点，编号 0 到 N-1，不存在三点共线的情况。每两点之间有一条直线相连。游戏没有规定起点和终点，但限定了每次转角的方向。首先，小王需要先选择两个点分别作为起点和终点，然后从起点开始访问剩余 N-2 个点恰好一次并回到终点。访问的顺序需要满足一串给定的长度为 N-2 由 L 和 R 组成的字符串 direction，表示从起点出发之后在每个顶点上转角的方向。根据这个提示，小王希望你能够帮她找到一个可行的遍历顺序，输出顺序下标（若有多个方案，输出任意一种）。可以证明这样的遍历顺序一定是存在的。

Screenshot 2020-03-20 at 17.04.58.png

（上图：A->B->C 右转；下图：D->E->F 左转）

示例 1：

输入：points = [[1,1],[1,4],[3,2],[2,1]], direction = "LL"

输入：[0,2,1,3]

解释：[0,2,1,3] 是符合"LL"的方案之一。在 [0,2,1,3] 方案中，0->2->1 是左转方向， 2->1->3 也是左转方向

示例 2：

输入：points = [[1,3],[2,4],[3,3],[2,1]], direction = "LR"

输入：[0,3,1,2]

解释：[0,3,1,2] 是符合"LR"的方案之一。在 [0,3,1,2] 方案中，0->3->1 是左转方向， 3->1->2 是右转方向

限制：

3 <= points.length <= 1000 且 points[i].length == 2
1 <= points[i][0],points[i][1] <= 10000
direction.length == points.length - 2
direction 只包含 "L","R"

原站题解

去查看

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

class Solution { public: vector<int> visitOrder(vector<vector<int>>& points, string direction) { } };

python3 解法, 执行用时: 852 ms, 内存消耗: 16.6 MB, 提交时间: 2023-06-25 14:28:05

# 永远走在包络线上
class Solution:
    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:
        def getNextPoint(pt,dir1): # 包络上寻找下一个逆时针（L）或顺时针（R）点
            res=None
            for pt2 in remainPts:
                if not res: res=pt2
                else:
                    AB,AC=[res[0]-pt[0],res[1]-pt[1]],[pt2[0]-pt[0],pt2[1]-pt[1]]
                    prod=AB[0]*AC[1]-AB[1]*AC[0] #向量积>0表示逆时针
                    if (dir1=='L' and prod<0) or (dir1=='R' and prod>0): res=pt2
            return res
        remainPts={(x,y):i for i,(x,y) in enumerate(points)}
        pt=min(remainPts)
        res=[remainPts[pt]]
        remainPts.pop(pt)
        for dir1 in direction:
            pt=getNextPoint(pt,dir1)
            res.append(remainPts[pt])
            remainPts.pop(pt)
        res.append(remainPts[list(remainPts)[0]]) # last point
        return res

golang 解法, 执行用时: 20 ms, 内存消耗: 3.4 MB, 提交时间: 2023-06-25 14:26:14

// 贪心策略：先找一个最外围的点，再根据下一次方向选择下一个点。
// 如果下次要向左转，就选当前点指向该点的向量顺时针旋转最后的那条向量对应的点；向右类似.
func visitOrder(points [][]int, direction string) []int {
    var res []int
    // 找最外围的一点作为起点，这里找最上边的点
    var cur int
    for i, v := range points {
        if v[1] > points[cur][1] {
            cur = i
        }
    }
    used := make([]bool, len(points))
    used[cur] = true
    res = append(res, cur)
    for _, d := range direction {
        next := -1
        for i, p := range points {
            if used[i] {
                continue
            }
            if next == -1 {
                next = i
                continue
            }
            x := sub(points[cur], points[next])
            y := sub(points[cur], p)
            cs := cross(x, y)
            if d == 'L' && cs < 0 || d == 'R' && cs > 0 {
                next = i
            }
        }
        cur = next
        used[cur] = true
        res = append(res, cur)
    } 
    for i := range points {
        if !used[i] {
            res = append(res, i)
            break
        }
    }
    return res
}

// 点 a 指向点 b 的向量
func sub(a, b []int) []int {
    return []int{b[0]-a[0], b[1]-a[1]}
}

// 向量 a 和向量 b 的叉乘
func cross(a, b []int) int {
    return a[0]*b[1] - a[1]*b[0]
}

java 解法, 执行用时: 3 ms, 内存消耗: 42.7 MB, 提交时间: 2023-06-25 14:23:29

class Solution {
	public int[] visitOrder(int[][] points, String direction) {
		int[] result = new int[points.length];
		Arrays.fill(result, -1);
		boolean[] used = new boolean[points.length];
		int cur = 0;
		int minUnusedIndex = 0; //记录下未访问过的点中最小的索引，不加这部分逻辑也可以运行
		while(true) {
			boolean minIndexUpdate = result[cur] != -1;
			int i = Math.max(result[cur] + 1, minUnusedIndex);
			for(; i < points.length; i++) {
				if(!used[i]) {
					if(!minIndexUpdate) {
						minIndexUpdate = true;
						minUnusedIndex = i;
					}
					if(cur < 2 || direction.charAt(cur - 2) == getDirection(points[result[cur - 2]], points[result[cur - 1]], points[i])) {
						result[cur] = i;
						used[i] = true;
						if(++cur == points.length) return result;
						break;
					}
				}
			}
			if(i == points.length) {
				result[cur--] = -1;
				used[result[cur]] = false;
				minUnusedIndex = Math.min(minUnusedIndex, result[cur]);
			}
		}
	}
	private char getDirection(int[] p0, int[] p1, int[] p2) {
		return(p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]) > 0 ? 'L' : 'R';
	}
}

cpp 解法, 执行用时: 56 ms, 内存消耗: 9.1 MB, 提交时间: 2023-06-25 14:22:02

class Solution {
private:
    pair<int, int> Sub(pair<int, int> a, pair<int, int> b) {
        // 求点 a 到点 b 的向量
        return make_pair(a.first - b.first, a.second - b.second);
    }

    int Cross(pair<int, int> a, pair<int, int> b) {
        // 求向量 a 到向量 b 的向量叉积
        return a.first * b.second - a.second * b.first;
    }
public:
    vector<int> visitOrder(vector< vector<int> >& points, string dir) {
        int n = points.size();
        vector<bool> used(n, false);  // 记录点的遍历情况， False未遍历 / True已遍历
        vector< pair<int, int> > point;
        vector<int> order; // 记录返回结果

        for (int i=0; i<n; ++i) {
            point.push_back( make_pair(points[i][0], points[i][1]) );
        }

        // 查找最左的点作为 起始点
        int start = 0;
        for (int i=1; i<n; ++i) {
            if (point[i] < point[start]) {
                start = i;
            }
        }
        used[start] = true;
        order.push_back(start);

        for (int i=0; i<dir.size(); ++i) {
            int next = -1;
            if (dir[i] == 'L') {
                // 转向方向为 L，选择相对方向最右的点
                for (int j=0; j<n; ++j) {
                    if (!used[j]) {
                        if (next == -1 || Cross(Sub(point[next], point[start]), Sub(point[j], point[start])) < 0) {
                            next = j;
                        }
                    } 
                }
            } else if (dir[i] == 'R') {
                // 转向方向为 R，选择相对方向最左的点
                for (int j=0; j<n; ++j) {
                    if (!used[j]) {
                        if (next == -1 || Cross(Sub(point[next], point[start]), Sub(point[j], point[start])) > 0) {
                            next = j;
                        }
                    } 
                }
            }
            // 返回结果加入选择的点，更新下一次转向的起点
            used[next] = true;
            order.push_back(next);
            start = next;
        }
        // 添加最后一个剩余点
        for (int i=0; i<n; ++i) {
            if (used[i] == false) {
                order.push_back(i);
            }
        }
        return order;
    }
};

python3 解法, 执行用时: 1576 ms, 内存消耗: 16.5 MB, 提交时间: 2023-06-25 14:21:19

class Solution:
    # 求点 a 到点 b 的向量
    def sub(self, a: List[List[int]], b: List[List[int]]) -> List[int]:
        return [a[0]-b[0], a[1]-b[1]]
    
    # 求向量 a 到向量 b 的向量叉积
    def cross(self, a: List[List[int]], b: List[List[int]]) -> int:
        return a[0] * b[1] - a[1] * b[0]
    
    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:
        n = len(points)
        used = [False] * n  # 记录点的遍历情况， False未遍历 / True已遍历
        order = [] # 记录返回结果
        
        # 查找最左的点作为 起始点
        start = 0
        for i in range(0,n):
            if points[i][0] < points[start][0]:
                start = i
        used[start] =True
        order.append(start)
        
        for i in direction:
            nxt = -1
            if i=='L':
                # 转向方向为 L，选择相对方向最右的点
                for j in range(0,n):
                    if not used[j]:
                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) <0 :
                            nxt = j
            else:
                # 转向方向为 R，选择相对方向最左的点
                for j in range(0,n):
                    if not used[j]:
                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) >0 :
                            nxt = j
            # 返回结果加入选择的点，更新下一次转向的起点
            used[nxt] = True
            order.append(nxt)
            start = nxt
        
        # 添加最后一个剩余点
        for i in range(0,n):
            if not used[i]:
                order.append(i)
        return order

上一题

下一题

详情