DeepSeek LeetCode LCP 27. 黑盒光线反射 Java实现

这道题的核心是预处理 + 有序集合。

💡 解题思路

• 光线路径的循环性：在黑盒中，从任意小孔沿某方向射入的光线，最终都会回到起点并沿相同方向射出，形成一个闭合的“循环”。在所有小孔都关闭的情况下，光线会在循环中无限反射。
• 状态表示：每一个(小孔编号, 方向)的组合，都代表了光线在循环中的一个“状态”。状态总数是2 * (2*(m+n)) - 4 = 4(m+n)-4。
• 开启小孔的作用：开启一个小孔，相当于在它所属的循环路径上，将该小孔对应的“状态位置”标记为“出口”。
• 查询的本质：open操作就是在当前光线状态所处的循环中，查找该状态位置之后的第一个“出口”。
• 高效数据结构：使用TreeSet维护每个循环上所有已开启小孔的位置，可以高效地完成“查找下一个”和“插入/删除”操作。

☕️ Java 代码实现

importjava.util.*;classBlackBox{privatefinalintn,m;privatefinalinttotalHoles;// 小孔总数: 2 * (m + n)privatefinalinttotalStates;// 状态总数: 4 * (m + n) - 4// cycleId[hole][dirIndex]: 记录状态 (hole, direction) 所属的循环ID// posInCycle[hole][dirIndex]: 记录状态在所属循环中的位置privatefinalint[][]cycleId;privatefinalint[][]posInCycle;// 每个循环对应一个 TreeSet，存储该循环上所有已开启小孔的位置privatefinalList<TreeSet<Integer>>cycles;privateintcycleCount;publicBlackBox(intn,intm){this.n=n;this.m=m;this.totalHoles=2*(m+n);this.totalStates=4*(m+n)-4;this.cycleId=newint[totalHoles][2];this.posInCycle=newint[totalHoles][2];// 初始化：-1 表示该状态尚未被分配循环for(inti=0;i<totalHoles;i++){Arrays.fill(cycleId[i],-1);Arrays.fill(posInCycle[i],-1);}this.cycles=newArrayList<>();this.cycleCount=0;// 在构造函数中预处理所有循环findAllCycles();}// 预处理所有光线的循环路径privatevoidfindAllCycles(){for(intstartHole=0;startHole<totalHoles;startHole++){for(intstartDir:newint[]{1,-1}){// 拐角处的小孔只有一个合法方向if(isCorner(startHole)&&!isValidCornerDirection(startHole,startDir)){continue;}intdirIdx=dirToIndex(startDir);// 如果这个状态已经属于某个循环，则跳过if(cycleId[startHole][dirIdx]!=-1){continue;}// 发现一个新循环TreeSet<Integer>cycleSet=newTreeSet<>();intcurrentCycleId=cycleCount++;cycles.add(cycleSet);intcurHole=startHole;intcurDir=startDir;intpos=0;// 沿着光线路径前进，直到回到起点状态do{// 记录当前状态cycleId[curHole][dirToIndex(curDir)]=currentCycleId;posInCycle[curHole][dirToIndex(curDir)]=pos;// 计算下一个状态: 经过小孔 curHole 后，方向取反intnextDir=-curDir;// 计算从 (curHole, nextDir) 出发到达的下一个小孔编号intnextHole=getNextHole(curHole,nextDir);curHole=nextHole;curDir=nextDir;pos++;}while(!(curHole==startHole&&curDir==startDir));}}}// 判断小孔是否为四个拐角privatebooleanisCorner(inthole){returnhole==0||hole==m||hole==m+n||hole==2*m+n;}// 判断拐角处的方向是否合法privatebooleanisValidCornerDirection(inthole,intdir){if(hole==0)returndir==-1;if(hole==m)returndir==1;if(hole==m+n)returndir==-1;if(hole==2*m+n)returndir==1;returntrue;}// 将方向 (1 或 -1) 映射到数组索引 (0 或 1)privateintdirToIndex(intdir){returndir==1?0:1;}// 核心函数：给定当前小孔和下一步方向，计算到达的下一个小孔编号privateintgetNextHole(inthole,intdir){intnext;if(dir==1){// 沿 y=x 方向// 关于 (m+n) 对称next=2*(m+n)-hole;}else{// dir == -1, 沿 y=-x 方向if(hole<=2*m){next=2*m-hole;}else{next=2*(2*m+n)-hole;}}// 取模运算，确保结果在 [0, totalHoles) 范围内return(next%totalHoles+totalHoles)%totalHoles;}// 开启小孔并射入光线，返回射出的小孔编号publicintopen(intindex,intdirection){// 1. 打开小孔：将小孔在两个方向上的状态位置，都加入到对应的循环中for(intd:newint[]{1,-1}){intcycleIdx=cycleId[index][dirToIndex(d)];if(cycleIdx!=-1){intpos=posInCycle[index][dirToIndex(d)];cycles.get(cycleIdx).add(pos);}}// 2. 执行查询，返回光线射出的小孔returnshoot(index,direction);}// 关闭小孔publicvoidclose(intindex){// 从小孔所属的所有循环中移除其位置记录for(intd:newint[]{1,-1}){intcycleIdx=cycleId[index][dirToIndex(d)];if(cycleIdx!=-1){intpos=posInCycle[index][dirToIndex(d)];cycles.get(cycleIdx).remove(pos);}}}// 内部查询方法：从 (index, direction) 状态出发，寻找下一个开启的小孔privateintshoot(intindex,intdirection){intdirIdx=dirToIndex(direction);intcycleIdx=cycleId[index][dirIdx];intcurPos=posInCycle[index][dirIdx];TreeSet<Integer>cycleSet=cycles.get(cycleIdx);// 在循环中寻找位置大于 curPos 的开启小孔IntegernextPos=cycleSet.higher(curPos);if(nextPos==null){// 如果没有更大的，则取循环中最小的开启小孔（绕一圈）nextPos=cycleSet.first();}// 根据位置找到对应的小孔编号returnfindHoleByPos(cycleIdx,nextPos);}// 根据循环ID和位置找到对应的小孔编号privateintfindHoleByPos(intcycleIdx,intpos){for(inthole=0;hole<totalHoles;hole++){for(intd:newint[]{1,-1}){if(cycleId[hole][dirToIndex(d)]==cycleIdx&&posInCycle[hole][dirToIndex(d)]==pos){returnhole;}}}return-1;// 正常情况下不会发生}}

🔑 关键点说明

• findAllCycles()：这是预处理的核心。它遍历所有可能的起始状态(startHole, startDir)，模拟光路直到回到起点，从而发现一个完整的循环。
• getNextHole()：这个函数是模拟光路的基础。它利用黑盒的几何对称性，通过数学计算直接得出光线经过反射后到达的下一个小孔编号。
• TreeSet：这是实现高效查询的关键。它维护了每个循环上当前所有开启小孔的位置（pos）。
  • add(pos)/remove(pos)：用于open和close操作。
  • higher(curPos)：用于shoot，可以O(log N)地找到当前位置之后的下一个出口。
• 二维数组记录状态：cycleId和posInCycle两个二维数组，以[hole][dirIndex]为索引，记录了每个状态所属的循环和位置，是后续所有操作的基础。

⏱️ 复杂度分析

• 时间复杂度：
  • 预处理 (findAllCycles)：需要遍历所有O(totalStates)个状态，因此时间复杂度为O(n + m)。
  • open/close/shoot：主要操作是TreeSet的add、remove和higher，时间复杂度均为O(log K)，其中 K 是该循环上已开启的小孔数量。
• 空间复杂度：需要存储所有状态的信息和TreeSet，整体空间复杂度为O(n + m)。