Kimi LeetCode LCP 15. 游乐园的迷宫 Python3实现

LCP 15. 游乐园的迷宫 — Python3 实现题目理解平面上有 N 个点需要找到一条访问所有 N 个点的路径使得路径在每个顶点的转角方向满足给定的 direction 字符串L 表示左转R 表示右转。不存在三点共线的情况。核心思路贪心 向量叉积官方题解的贪心策略是每一步选择最极端的点使得剩余所有未访问的点都位于转向要求的那一侧。这样可以保证后续始终有解。具体实现1. 起点选择选横坐标最小的点作为起点保证初始方向可控2. 叉积判断方向对于向量 a→b 和 a→c叉积 cross (b-a) × (c-a)- cross 0c 在 a→b 的左侧逆时针- cross 0c 在 a→b 的右侧顺时针3. 贪心选点- 若 direction[i] L下一步要左转则当前选择最右侧的点叉积最大即其他点都在该点左侧- 若 direction[i] R下一步要右转则当前选择最左侧的点叉积最小即其他点都在该点右侧Python3 代码pythonfrom typing import Listclass Solution:def visitOrder(self, points: List[List[int]], direction: str) - List[int]:n len(points)visited [False] * nans []# 辅助函数计算向量 a-bdef vec(a, b):return [b[0] - a[0], b[1] - a[1]]# 辅助函数计算向量叉积 (a x b)def cross(a, b):return a[0] * b[1] - a[1] * b[0]# 1. 选择横坐标最小的点作为起点保证凸包性质start 0for i in range(n):if points[i][0] points[start][0]:start ians.append(start)visited[start] True# 2. 根据 direction 贪心选择下一个点for d in direction:nxt -1if d L:# 下一步要左转当前选最右侧的点叉积最大for j in range(n):if not visited[j]:if nxt -1 or cross(vec(points[start], points[j]),vec(points[start], points[nxt])) 0:nxt jelse: # d R# 下一步要右转当前选最左侧的点叉积最小for j in range(n):if not visited[j]:if nxt -1 or cross(vec(points[start], points[j]),vec(points[start], points[nxt])) 0:nxt jans.append(nxt)visited[nxt] Truestart nxt# 3. 最后一个未访问的点加入答案for i in range(n):if not visited[i]:ans.append(i)return ans复杂度分析- 时间复杂度O(N^2)每次选择下一个点需要遍历所有未访问点- 空间复杂度O(N)用于访问标记数组和答案数组关键说明- 叉积的符号决定了相对位置cross(vec(start, j), vec(start, nxt)) 0 表示 j 在 start→nxt 的左侧即 nxt 相对更靠右- 由于不存在三点共线叉积不会为 0无需处理共线情况- 起点选最左侧点是为了确保初始步可以构造出满足条件的凸包边界