[LeetCode] 每日一题 2612. 最少翻转操作数

题目链接

https://leetcode.cn/problems/minimum-reverse-operations

题目描述

给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。

同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。

你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。

请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

• 子数组 指的是一个数组里一段连续 非空 的元素序列。

• 对于所有的 i ，ans[i] 相互之间独立计算。

• 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。

示例输入

示例 1

输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。
我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。
通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。

示例 2

输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。
翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。
由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。

示例 3

输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。

提示

• 1 <= n <= 10^5

• 0 <= p <= n - 1

• 0 <= banned.length <= n - 1

• 0 <= banned[i] <= n - 1

• 1 <= k <= n 

• banned[i] != p

• banned 中的值 互不相同 。

解题思路

这道题的核心在于如何高效地计算每个位置的最少翻转次数。由于翻转操作的性质，我们可以发现，每次翻转后 1 只会出现在偶数或奇数索引上，不会混合，因此可以分别维护两个集合，一个存偶数索引，一个存奇数索引，同时避免 banned 位置的影响

我的解题过程：
刚开始，我的第一反应是用 BFS，因为每次翻转相当于在图中做一次跳跃，最短路径问题通常可以用 BFS 解决。但这里的难点是，如何高效找到可以跳跃的目标位置？如果直接遍历，时间复杂度会很高

后来我想到可以用 TreeSet 维护未访问的索引，这样在 BFS 过程中，可以快速找到当前 1 能够到达的合法位置，并逐步更新结果数组 ans。这样不仅能避免重复访问，还能高效跳过不合法的位置，提升计算效率

具体步骤如下：

1. 初始化：

   • 用 ans 数组存储最终答案，初始化为 -1（表示不可达）

   • 用 bannedIndex 集合存储 banned 位置，方便快速查找

   • 用 TreeSet 维护所有未访问的位置，分为偶数索引集合和奇数索引集合，便于按奇偶性进行 BFS 搜索

2. BFS 处理：

   • 从 p 位置出发，开始 BFS

   • 计算当前 1 经过一次 k 翻转后可能到达的位置范围 [mn, mx]，并在 TreeSet 里快速查找符合条件的未访问索引

   • 将新访问到的位置加入队列，并更新 ans，表示从 p 到这个位置的最短翻转次数

3. 返回结果：遍历完所有可能的跳跃路径后，返回 ans

代码实现

class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        ans[p] = 0;
        HashSet<Integer> bannedIndex = new HashSet<>();
        for (int index : banned) {
            bannedIndex.add(index);
        }
        List<TreeSet<Integer>> indices = new ArrayList<>();
        indices.add(new TreeSet<>());
        indices.add(new TreeSet<>());
        for (int i = 0; i < n; i++) {
            if (i != p && !bannedIndex.contains(i)) {
                indices.get(i % 2).add(i);
            }
        }
        Deque<Integer> deque = new LinkedList<>();
        deque.offerLast(p);
        while (!deque.isEmpty()) {
            int i = deque.pollFirst();
            int mn = Math.max(i - k + 1, k - i - 1);
            int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
            TreeSet<Integer> set = indices.get(mn % 2);
            for (Iterator<Integer> it = set.tailSet(mn).iterator(); it.hasNext(); it.remove()) {
                int j = it.next();
                if (j > mx) {
                    break;
                }
                ans[j] = ans[i] + 1;
                deque.offerLast(j);
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n log n)，BFS 过程最多遍历 n 个元素，而 TreeSet 的操作（插入、删除、查找）都是 O(log n) 级别，总体复杂度是 O(n log n)

• 空间复杂度：O(n)，用于存储 ans、bannedIndex 和 TreeSet

总结

这道题一开始让我有些困惑，因为翻转操作让 1 的移动范围变得不那么直观。但通过分析，发现它其实是一个等差数列的跳跃问题，可以利用 BFS + TreeSet 来高效查找下一步能访问的位置，避免暴力搜索的高复杂度

在实现过程中，我踩过一个坑，就是如何快速找到合法的跳跃位置，后来用 TreeSet 解决了这个问题，让搜索更加高效。这次做题让我进一步体会到，有序集合在某些场景下能极大优化搜索效率，以后遇到类似问题可以优先考虑这种数据结构

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。