DeepSeek LeetCode 2612. 最少翻转操作数 Java实现

解题思路LeetCode 2612「最少翻转操作数」是一个图论 BFS 最短路径问题把数组每个位置看作图中的一个节点每次翻转操作相当于在当前节点到下一节点之间连一条权重为 1 的边。由于所有边的权重相等BFS 是求解最短路径的标准算法。---Step 1推导翻转后的位置公式设当前 1 在位置 i翻转一个长度为 k 的子数组 [L, R]R - L 1 k。根据对称变换公式i 翻转后的位置是 j L R - i。结合 i 和子数组的边界条件L ∈ [max(0, i-k1), min(i, n-k)]代入后得到可达位置集合实际上是一个等差数列公差为 2。这意味着· 从奇/偶性相同的节点出发只能跳到同样奇偶性的节点· 可达位置的区间为 [minJ, maxJ]区间内所有与当前节点奇偶性相同的位置均可一步到达---Step 2BFS 有序集合优化直接实现 BFS 的时间复杂度为 O(n·k)当 n 10⁵、k 10⁵ 时会超时。优化的关键在于每个节点被访问后无需再次考虑。维护两个 TreeSet一个存偶数下标一个存奇数下标存储未访问且未被禁止的位置。BFS 执行过程中1. 从当前 i 计算可达区间 [mn, mx]2. 根据 mn 的奇偶性选择对应的 TreeSet3. 获取集合中落在 [mn, mx] 范围内的所有元素批量处理并原地删除由于 TreeSet 的 ceiling 和 erase 操作均为 O(log n)总复杂度降至 O(n log n)。---Java 代码实现javaclass Solution {public int[] minReverseOperations(int n, int p, int[] banned, int k) {// 初始化答案数组填充 -1int[] ans new int[n];Arrays.fill(ans, -1);ans[p] 0;// 禁止位置集合SetInteger banSet new HashSet();for (int b : banned) banSet.add(b);// 维护两个 TreeSet分别存储未访问的奇数下标和偶数下标TreeSetInteger[] sets new TreeSet[2];sets[0] new TreeSet(); // 偶数sets[1] new TreeSet(); // 奇数for (int i 0; i n; i) {if (i ! p !banSet.contains(i)) {sets[i % 2].add(i);}}// BFS 队列QueueInteger queue new ArrayDeque();queue.offer(p);while (!queue.isEmpty()) {int cur queue.poll();// 计算可达区间 [mn, mx]// mn max(k - 1 - cur, cur - k 1)// mx min(cur k - 1, 2 * n - k - cur - 1)int mn Math.max(k - 1 - cur, cur - k 1);int mx Math.min(cur k - 1, 2 * n - k - cur - 1);// 根据奇偶性选择对应的集合TreeSetInteger set sets[mn % 2];// 遍历并删除区间内的所有元素Integer next set.ceiling(mn);while (next ! null next mx) {ans[next] ans[cur] 1;queue.offer(next);set.remove(next);next set.ceiling(next);}}return ans;}}代码要点说明· TreeSet 提供 O(log n) 的 ceiling() 查找和 remove() 删除· mn 的奇偶性决定使用哪个 TreeSet因为最终位置与起点奇偶性相同· 区间边界 mn 和 mx 的推导需考虑数组两端越界的情况· 使用 TreeSet 批量取值的思路大幅减少循环次数---复杂度分析· 时间复杂度O(n log n)。每个位置最多被加入和删除一次TreeSet 操作均为 O(log n)总体约 2n 次操作。· 空间复杂度O(n)。答案数组和两个 TreeSet 各存储最多 O(n) 个元素。