Kimi LeetCode LCP 27. 黑盒光线反射 Python3实现

这是 LeetCode LCP 27. 黑盒光线反射 的 Python3 实现。解题思路核心思想是预处理所有光线循环 有序集合维护1. 状态定义每个状态由 (小孔序号, 方向) 组成。方向 1 表示沿 yx-1 表示沿 y-x。2. 预处理循环利用数学公式直接计算光线到达的下一个小孔无需模拟坐标。所有状态恰好被划分成若干个互不相交的循环。3. 有序集合每个循环维护一个有序列表记录该循环中已打开的小孔位置。open 时插入close 时删除。4. 查询光线从某个状态出发沿循环顺序找下一个已打开的小孔严格在循环顺序之后若找不到则循环到该集合的第一个。状态转移公式- 方向 1yx从第 i 个小孔射出 → 到达第 2(mn)-i 个小孔- 方向 -1y-x- 若 i ≤ 2m → 到达第 2m-i 个小孔- 若 i 2m → 到达第 2(2mn)-i 个小孔- 经过非角点小孔后方向翻转经过角点0, m, mn, 2mn方向不变。---Python3 代码pythonimport bisectclass BlackBox:def __init__(self, n: int, m: int):self.n nself.m mself.pt_count 2 * (n m)# groupPos[i] (group_id, location_in_group) 对应方向 1 (yx)# groupNeg[i] (group_id, location_in_group) 对应方向 -1 (y-x)# 角上的小孔只有一个有效方向另一个保持 (-1, -1)self.groupPos [(-1, -1)] * self.pt_countself.groupNeg [(-1, -1)] * self.pt_count# 每个循环对应一个有序列表元素为 (location, index)self.groupStats []for i in range(self.pt_count):# 方向 1跳过角点 0 和 mnif i ! 0 and i ! m n and self.groupPos[i][0] -1:self._create_group(i, 1)# 方向 -1跳过角点 m 和 2mnif i ! m and i ! 2 * m n and self.groupNeg[i][0] -1:self._create_group(i, -1)# 记录物理上已打开的小孔序号self.opened set()def _create_group(self, index: int, direction: int):预处理一个光线循环group_id len(self.groupStats)group_loc 0self.groupStats.append([])while True:if direction 1:self.groupPos[index] (group_id, group_loc)index self.pt_count - indexelse:self.groupNeg[index] (group_id, group_loc)if index 2 * self.m:index 2 * self.m - indexelse:index (2 * self.m self.n) * 2 - indexgroup_loc 1# 非角点则翻转方向角点方向不变if index ! 0 and index ! self.m and index ! self.m self.n and index ! 2 * self.m self.n:direction -direction# 若下一状态已访问过说明循环闭合if direction 1 and self.groupPos[index][0] ! -1:breakif direction -1 and self.groupNeg[index][0] ! -1:breakdef open(self, index: int, direction: int) - int:# 若小孔未打开将其所有对应状态插入到所属循环的有序集合中if index not in self.opened:self.opened.add(index)if self.groupPos[index][0] ! -1:gid, gloc self.groupPos[index]bisect.insort(self.groupStats[gid], (gloc, index))if self.groupNeg[index][0] ! -1:gid, gloc self.groupNeg[index]bisect.insort(self.groupStats[gid], (gloc, index))# 查询从当前状态出发沿循环顺序找下一个已打开的小孔gid, gloc self.groupPos[index] if direction 1 else self.groupNeg[index]arr self.groupStats[gid]# 严格大于当前 location 的最小元素pos bisect.bisect_right(arr, (gloc, float(inf)))if pos len(arr):return arr[pos][1]# 循环到开头return arr[0][1]def close(self, index: int) - None:if index not in self.opened:returnself.opened.remove(index)if self.groupPos[index][0] ! -1:gid, gloc self.groupPos[index]arr self.groupStats[gid]p bisect.bisect_left(arr, (gloc, index))if p len(arr) and arr[p] (gloc, index):arr.pop(p)if self.groupNeg[index][0] ! -1:gid, gloc self.groupNeg[index]arr self.groupStats[gid]p bisect.bisect_left(arr, (gloc, index))if p len(arr) and arr[p] (gloc, index):arr.pop(p)---复杂度分析- 预处理O(m n)每个状态恰好属于一个循环。- 单次 open/closeO(log(mn))bisect 维护有序列表的插入、删除、查询均为对数级列表操作本身为 O(k)其中 k 为循环长度但 k ≤ 2(mn)且操作次数 ≤ 10000完全可接受。- 空间O(m n)。