首页 > 其他分享 >2612. 最少翻转操作数

2612. 最少翻转操作数

时间:2023-04-09 19:14:30浏览次数:51  
标签:操作数 遍历 下标 2612 int 反转 位置 ban 翻转

题目链接:2612. 最少翻转操作数

方法:BFS + AVLTree

解题思路

先不考虑被 \(ban\) 的位置:

  • 假设当前 \(1\) 的位置在下标 \(i\) 上,那么将其按照包含 \(i\) 且长度为 \(k\) 的数组反转一次所能得到的对应下标的可能结果是一个从 \(i - k + 1\) 起始到 \(i + k - 1\) 结束的公差为 \(2\) 的等差数列。
  • 由于数组下标范围为 \([0, n - 1]\),因此为了防止反转后的下标越界,应该确定反转后的下标最小值和最大值(也就是最左、右端点),观察可以发现:
  • 最左端点的选取:
    • 要么是反转数组 \([0, k - 1]\) \(=>\) 新下标:\(k - i - 1\);
    • 要是是反转数组 \([i - k + 1 ,i]\) \(=>\) 新下标:\(i - k + 1\);
    • 最左端点应该选择两者之间的最大值,防止越界。
  • 最右端点的选取:
    • 要么是反转数组 \([n - k, n - 1]\) \(=>\) 新下标:\(2n - k - i - 1\);
    • 要么是反转数组 \([i, i + k - 1]\) \(=>\) 新下标:\(i + k - 1\);
    • 最右端点应该选择两者之间的最小值,防止越界。
  • 本题要求:最少翻转操作数,考虑 \(BFS\) 求权重为 \(1\) 的"最短路"。从上述可知,反转一次到新的位置之后,再在当前新的位置按照上述规律进行反转,一层层向下一个位置遍历,直到遍历所有位置,同时要考虑被 \(ban\) 的位置不能使用,其中的层数就是最小的反转数,因此可以使用 \(BFS\)。
  • BFS
    • 初始化队列,将 \(1\) 的起始位置 \(p\) 入队,初始化当前层数 \(level = 0\),并将该位置的答案初始化为 \(level\);
    • 当队列不为空时,取出队首元素,然后遍历其下一个能到达的除被 \(ban\) 的且未到过的所有位置,并入队,将该位置的答案置为 \(level + 1\);
    • 重复上述操作直到队列为空;
    • 但这样写法会 TLE,因为这样的时间复杂度为 \(O(nk)\),入队的个数为 \(O(n)\),每个队内的元素遍历其下一个位置为 \(O(k)\),因为访问过的下标一直存在,只要存在就会查看其是否遍历,若将遍历过的下标删除,则没有该冗余。
  • 平衡树优化 \((set)\)
    • 维护下标,删除已经访问过的;
    • 技巧:维护两个平衡树,一个存放奇数下标,一个存放偶数下标,因为序列的公差为 \(2\)。

代码

class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        unordered_set<int> ban{banned.begin(), banned.end()};
        set<int> sets[2];
        for (int i = 0; i < n; i ++ ) {
            if (i != p && !ban.count(i)) {
                sets[i % 2].insert(i);
            }
        }
        sets[0].insert(n); // 哨兵
        sets[1].insert(n);
        vector<int> ans(n, -1);
        queue<int> q;
        q.push(p);
        ans[p] = 0;
        while (!q.empty()) {
            int i = q.front(), level = ans[i];
            q.pop();
            int mn = max(i - k + 1, k - i - 1);
            int mx = min(i + k - 1, 2 * n - k - i - 1);
            auto &s = sets[mn % 2];
            // 找到第一个mn的位置,哨兵防止it为空
            for (auto it = s.lower_bound(mn); *it <= mx; it = s.erase(it)) { 
                ans[*it] = level + 1;
                q.push(*it);
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(nlogn)\);
空间复杂度:\(O(n)\)。

标签:操作数,遍历,下标,2612,int,反转,位置,ban,翻转
From: https://www.cnblogs.com/lxycoding/p/17300819.html

相关文章

  • 链表中的节点每k个一组翻转
    classSolution{publicListNodereverseKGroup(ListNodehead,intk){ListNodedummy=newListNode(0);//定义虚拟节点dummy.next=head;ListNodeprev=dummy;//定义一个前置节点prev,用于保存已经翻转完成的部分的尾部节点......
  • flask_day05:信号 Django信号 flask-script sqlalchemy 创建操作数据表
    目录回顾信号比如:用户表新增一条记录时,就记录一下日志内置信号:flask少一些,Django多一些使用内置信号量的步骤自定义信号Django信号django中使用内置信号flask-script自定制命令sqlalchemy快速使用原生操作的快速使用创建操作数据表鲁棒性链路,链路追踪,上下游,大的单体应用,上游还......
  • [蓝桥杯 2021 国 AB] 翻转括号序列(线段树上二分)
    [蓝桥杯2021国AB]翻转括号序列题目描述给定一个长度为\(n\)的括号序列,要求支持两种操作:将\(\left[L_{i},R_{i}\right]\)区间内(序列中的第\(L_{i}\)个字符到第\(R_{i}\)个字符)的括号全部翻转(左括号变成右括号,右括号变成左括号)。求出以\(L_{i}\)为左端点......
  • canvas实现图片镜像翻转的2种方式
    canvas实现图片镜像翻转的2种方式原文引用:https://www.qetool.com/scripts/view/23387.html1.通过canvas自带的画布方法进行翻转varimg=newImage();//这个就是img标签的dom对象img.src='./sy.png';img.onload=function(){//图片加载完成后,执行此方......
  • ImageView翻转效果
    点击图中的星星开始翻转源码:importandroid.content.Context;importandroid.content.res.TypedArray;importandroid.graphics.Bitmap;importandroid.graphics.Camera;importandroid.graphics.Matrix;importandroid.graphics.drawable.BitmapDrawab......
  • 861. 翻转矩阵后的得分
    题目描述给了一个二维矩阵,矩阵的元素不是0就是1你可以进行任意次操作,让某行或者某列进行翻转元素的得分是每一行二进制的和问怎么操作可以让总得分最大?f1贪心+计算增量基本分析为啥可以贪心?(1)对每行来说,首位肯定是1最好,遮掩某些行需要翻转,某些不翻;(2)对同一列来说,大家的优先......
  • 1658. 将 x 减到 0 的最小操作数
    题目描述给一个整数数组nums和整数x需要从数组的左边或者右边删除元素,然后用x减去删除的元素问如果x刚好成删到0,怎么删最短?f1-反向思考+双指针基本分析反向思考?找一个最长的子数组满足和=sum(nums)-x为啥可以双指针?(1)元素都是整数,序列和是单调的;(2)元素连续代码def......
  • 25. K 个一组翻转链表
    25.K个一组翻转链表给你链表的头节点head,每 k 个节点一组进行翻转,请你返回修改后的链表。k是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。......
  • 226. 翻转二叉树
    给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。classSolution{public:TreeNode*invertTree(TreeNode*root){if(root==nullptr)returnnullptr;else{TreeNode*node=root->left;root->left=root->righ......
  • 华为OD机试 翻转单词顺序
    本期题目:翻转单词顺序题目输入一个英文文章片段翻转指定区间的单词顺序,标点符号和普通字母一样处理例如输入字符串 Iamadeveloper. 区间[0,3]则输出 developer.aamI输入使用换行隔开三个参数第一个参数为英文文章内容即英文字符串第二个参数为反转起始单词下标,下......