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无需处理共线情况- 起点选最左侧点是为了确保初始步可以构造出满足条件的凸包边界

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

相关推荐

从状态机到动态密码：揭秘“知道密码也打不开”的逻辑锁原理与Python实现

模糊综合评价：从模糊数学到精准决策的实战指南

中国终于有人，重新定义了「技术创新」的评判标准｜一套从东方哲学落地的硬核产业坐标系

更多资讯

平谷电工证报名时间官方报名入口怎么找

中级电工证多久能下来通过率揭秘

玉环电工证复审必看！考前押题怎么用，别再交冤枉钱

电工证线上报名流程千万别踩坑证书过期了不知道怎么复审延期

乌海高压电工证有效期多久 2026河南最新政策怎么应对

工地太忙根本没时间复习考试？普洱市电工证怎么报名全攻略

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？