当前位置：首页 > news >正文

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

news 2026/5/25 0:33:55

以下是 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; // 起点翻转次数为 0

const 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-k+1)，mx = min(i+k-1, 2n-k-i-1)
且 j 与 i 的奇偶性相同（因为 L+R 为定值）。
因此可达位置是 [mn, mx] 内所有与 i 同奇偶的位置。
3. 并查集优化
· 用 parent[0] 维护偶数下标中下一个未访问的位置，parent[1] 维护奇数下标。
· find 函数支持路径压缩，快速跳过已访问的位置。
· 每个位置只会被处理一次，总操作次数 ≈ O(n·α(n))。

复杂度分析

· 时间复杂度：O(n·α(n))，其中 α 为阿克曼函数反函数，近似常数。每个位置最多被查询和删除一次。
· 空间复杂度：O(n)，用于答案数组、并查集、队列和禁止集合。

查看全文

http://www.jsqmd.com/news/880368/