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

这篇具有很好参考价值的文章主要介绍了【算法题】2612. 最少翻转操作数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

给你一个整数 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 中的值 互不相同 。文章来源地址https://www.toymoban.com/news/detail-649693.html

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;
    }
}

到了这里,关于【算法题】2612. 最少翻转操作数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 记一次基于FPGA的VGA显示四操作数计算器工程的开发流程——(1)从顶层设计说起

    首先值得说明的是,在这个项目几乎完成之际,笔者才愈发体会到了硬件思维和软件思维的云泥之别。不幸的是,在此项目的实现过程中,绝大部分代码的思维仍然是软件思维,因此该项目主要模块的设计部分可能并不能体现硬件操作的独到之处,不符合硬件工程师的基本设

    2024年02月04日
    浏览(39)
  • 【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数

    1. 长度最小的子数组 - 力扣(LeetCode) (1)方法一:暴力列举出所有的子数组的和 时间复杂度:O(n**2):枚举所有子数组O(n**2) (2)方法二: 利用 单调性(两个指针都不回退) ,使用\\\" 同向双指针 \\\"(其实就是 滑动窗口 )来优化 那么 滑动窗口过程 是怎么样的? 1le

    2024年03月22日
    浏览(53)
  • 【算法与数据结构】226、LeetCode翻转二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题的思路很简单,本质上就是遍历每一个节点,然后交换左右节点。我们可以用前中后遍历或者是层次遍历法来做,参考这两篇文章,【算法与数据结构】144、94、145LeetCode二

    2024年02月16日
    浏览(40)
  • C++二分算法:得到子序列的最少操作次数

    二分查找算法合集 给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arr ,arr 可能 包含重复元素。 每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2] ,那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后

    2024年02月05日
    浏览(45)
  • 【算法题】2602. 使数组元素全部相等的最少操作次数

    给你一个正整数数组 nums 。 同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中,你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次: 将数组里一个元素 增大 或者 减小 1 。 请你返回一个长度为 m 的数组 answer ,其中 answer[i]是将 nums 中所有元素变成

    2023年04月24日
    浏览(34)
  • 【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy

    给你一个正整数数组 nums 。每一次操作中,你可以从 nums 中选择 任意 一个数并将它 减小 到 恰好 一半 。(注意,在后续操作中你可以对减半过的数继续执行操作) 请你返回将 nums 数组和 至少 减少一半 的 最少 操作数。 1 = n u m s . l e n g t h = 1 0 5 1 = n u m s [ i ] = 1 0 7 1 = num

    2024年02月15日
    浏览(44)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月24日
    浏览(43)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月21日
    浏览(55)
  • 【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)

      目录 一,单值二叉树 题目详情: 解法:父子比较法 解题思路: 思路实现: 源代码: 二,相同的树 题目详情: 解法:比较法 解题思路: 思路实现: 源代码: 三,翻转二叉树 解法:替换法 解题思路: 思路实现: 源代码: 题目详情: 如果 二叉树 每个节点都具有 相

    2024年02月07日
    浏览(54)
  • leetcode 1806. 还原排列的最少操作步数

    题目链接:leetcode 1806 给你一个偶数 n​​​​​​ ,已知存在一个长度为 n 的排列 perm ,其中 perm[i] == i​(下标 从 0 开始 计数)。 一步操作中,你将创建一个新数组 arr ,对于每个 i : 如果 i % 2 == 0 ,那么 arr[i] = perm[i / 2] 如果 i % 2 == 1 ,那么 arr[i] = perm[n / 2 + (i - 1) / 2]

    2024年02月20日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包