美文网首页
【算法题】2612. 最少翻转操作数

【算法题】2612. 最少翻转操作数

作者: 程序员小2 | 来源:发表于2023-08-14 07:51 被阅读0次

题目:

给你一个整数 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 中的值 互不相同 。

java代码:

class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        var ban = new boolean[n];
        ban[p] = true;
        for (int i : banned) ban[i] = true;
        TreeSet<Integer>[] sets = new TreeSet[2];
        sets[0] = new TreeSet<>();
        sets[1] = new TreeSet<>();
        for (int i = 0; i < n; i++)
            if (!ban[i])
                sets[i % 2].add(i);
        sets[0].add(n);
        sets[1].add(n); // 哨兵

        var ans = new int[n];
        Arrays.fill(ans, -1);
        var q = new ArrayList<Integer>();
        q.add(p);
        for (int step = 0; !q.isEmpty(); ++step) {
            var tmp = q;
            q = new ArrayList<>();
            for (int i : tmp) {
                ans[i] = step;
                // 从 mn 到 mx 的所有位置都可以翻转到
                int mn = Math.max(i - k + 1, k - i - 1);
                int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
                var s = sets[mn % 2];
                for (var j = s.ceiling(mn); j <= mx; j = s.ceiling(mn)) {
                    q.add(j);
                    s.remove(j);
                }
            }
        }
        return ans;
    }
}

相关文章

  • ARTS 20201208-1215

    Algorithm: 每周至少做一个 LeetCode 的算法题算法题:1 剑指 offer 24: 翻转链表递归...

  • Freecodecamp 算法题

    Freecodecamp 算法题 1. Reverse a String 翻转字符串 先把字符串转化成数组,再借助...

  • ORID 58 Meeting rooms II

    今天每日一题253. Meeting rooms II 用什么算法? 这道题首先要理解题意,为了用最少的房间来安排...

  • 算法题--单向链表局部翻转

    0. 链接 题目链接 1. 题目 Reverse a linked list from position m to...

  • 从尾到头打印链表

    题目: 题目的理解: 要注意的是值顺序的翻转,不是指列表。 python实现 提交 // END 算法题 刷的有点慢啊

  • 牛客网高频算法题系列-BM3-链表中的节点每k个一组翻转

    牛客网高频算法题系列-BM3-链表中的节点每k个一组翻转 题目描述 将给出的链表中的节点每 k 个一组翻转,返回翻...

  • 关于数据结构和算法的总结

    关于数据结构和算法, 确实有不少公司在面试的时候会考一些这样的题, 甚至一些叼钻的操作数据结构的题, 当这样的问题...

  • 初级脚本算法

    1.翻转字符串算法挑战 实战翻转字符串算法你可以先把字符串转化成数组,再借助数组的reverse方法翻转数组顺序,...

  • LruCache原理和用法与LinkedHashMap

    一.LruCache算法 LruCache算法就是Least Recently Used,也就是最近最少使用算法。...

  • ARTS打卡第八周

    ARTS打卡第八周 Algorithm:每周至少做一个 leetcode 的算法题 1689. 十-二进制数的最少...

网友评论

      本文标题:【算法题】2612. 最少翻转操作数

      本文链接:https://www.haomeiwen.com/subject/hxnqmdtx.html