以下是 LeetCode 2612「最少翻转操作数」的 JavaScript 实现采用 BFS 并查集路径压缩 优化时间复杂度 O(n·α(n))可处理 n ≤ 10⁵ 的数据规模。javascript/*** param {number} n* param {number} p* param {number[]} banned* param {number} k* return {number[]}*/var minReverseOperations function(n, p, banned, k) {const ans new Array(n).fill(-1);ans[p] 0; // 起点翻转次数为 0const banSet new Set(banned); // 禁止位置集合// 并查集parent[parity][i] 表示奇偶性为 parity 的位置 i 的下一个可用位置const parent [new Array(n 2), new Array(n 2)];for (let parity 0; parity 2; parity) {for (let i 0; i n 1; i) {parent[parity][i] i; // 初始指向自身}}// 查找根路径压缩const find (parity, x) {if (parent[parity][x] ! x) {parent[parity][x] find(parity, parent[parity][x]);}return parent[parity][x];};// 标记不可用的位置被禁止或起点for (let i 0; i n; i) {if (i p || banSet.has(i)) {parent[i % 2][i] i 2; // 指向下一个同奇偶的位置}}const queue [p];let head 0;while (head queue.length) {const cur queue[head];// 计算可达区间 [mn, mx]let mn Math.max(k - 1 - cur, cur - k 1);let mx Math.min(cur k - 1, 2 * n - k - cur - 1);if (mn mx) continue;const parity mn % 2; // 区间内所有位置奇偶性相同let pos find(parity, mn); // 区间内第一个可用位置while (pos mx pos n) {ans[pos] ans[cur] 1; // 更新步数queue.push(pos); // 入队继续 BFS// 将当前 pos 标记为已使用指向下一个可用位置parent[parity][pos] find(parity, pos 2);pos find(parity, pos); // 继续寻找下一个可用位置}}return ans;};核心要点1. BFS 层次遍历从起点 p 出发每次翻转操作相当于一步移动BFS 保证首次到达某位置时步数最小。2. 可达区间公式当前 1 在位置 i翻转长度为 k 的子数组后新位置 j 满足mn max(k-1-i, i-k1)mx min(ik-1, 2n-k-i-1)且 j 与 i 的奇偶性相同因为 LR 为定值。因此可达位置是 [mn, mx] 内所有与 i 同奇偶的位置。3. 并查集优化· 用 parent[0] 维护偶数下标中下一个未访问的位置parent[1] 维护奇数下标。· find 函数支持路径压缩快速跳过已访问的位置。· 每个位置只会被处理一次总操作次数 ≈ O(n·α(n))。复杂度分析· 时间复杂度O(n·α(n))其中 α 为阿克曼函数反函数近似常数。每个位置最多被查询和删除一次。· 空间复杂度O(n)用于答案数组、并查集、队列和禁止集合。
