厦门优秀网站建设,公司做年审在哪个网站,重庆 网站 建设,做金融的免费发帖的网站有哪些题目
给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p #xff0c;它们表示一个长度为 n 且下标从 0 开始的数组 arr #xff0c;数组中除了下标为 p 处是 1 以外#xff0c;其他所有数都是 0 。 同时给你一个整数数组 banned #xff0c;它包含数组中的一些位置。b…题目
给你一个整数 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 105 0 p n - 1 0 banned.length n - 1 0 banned[i] n - 1 1 k n banned[i] ! p banned 中的值 互不相同 用例分析
不考虑banned。假定1在i出翻转[i,ik)则1到了ik-1处。翻转[j,jk-1],翻转之前i距离子数组的开始i-j那么翻转后1的距离子数组的结束i-j即jk-1-(i-j) k2*j-i-1k-i-12*j j的取值范围为[i-k1,i],同时[0,n-k] n5,k4 n5,k4 10000 00010 k-i-13新位置为303 01000 00100 00001 k-i-12新位置为202 224 00100 01000 00010 k-i-11新位置为101 123 00010 10000 00100 k-i-10新位置为000 022 00001 01000 k-i-1-1新位置为 -121
注意 p已经处理。 核心代码
class Solution { public: vectorint minReverseOperations(int n, int p, vectorint banned, int k) { vectorint vRet(n, -1); vRet[p] 0; queueint que; que.emplace(p); setint set0, set1; for (int i 0; i n; i) { if (i 1) { set1.emplace(i); } else { set0.emplace(i); } } for (const auto b : banned) { set0.erase(b); set1.erase(b); } set0.erase(p); set1.erase(p); while (que.size()) { const auto cur que.front(); que.pop(); const int j0 max(0, cur - k 1); const int j1 min(cur, n - k); const int next0 k - cur - 1 2 * j0; const int next1 k - cur - 1 2 * j1; auto setCur (next0 1) ? set1 : set0; auto it0 setCur.lower_bound(next0); auto it1 setCur.upper_bound(next1 1); for (auto it it0; it ! it1; it) { vRet[*it] vRet[cur] 1; que.emplace(*it); } setCur.erase(it0, it1); } return vRet; } };
时间复杂度
用广度优先实现入队n次。每次出队时间复杂度O(k)总时间复杂度O(kn)。出队的时间复杂度可以优化。每次出队是连续的奇数或偶数我们可以用两个std::set分别纪录未处理的奇数和偶数。未处理分两种情况已经处理被禁止。每次出队只需要查询两次时间复杂度O(logn)。故总时间复杂度为O(nlogn)。
并集查找
如果i是偶数vDo[i]记录需要处理的偶数中大于等于i且最小的数。奇数类似。以n等于8为例只分析偶数奇数类似。初始{0,2,4,6} {0,2,4,6} 处理0{2,2,4,6} 处理2{0,4,4,6} 处理4{0,2,6,6} 处理6{0,2,4,MAX} 2,2,4,6 处理0{2,4,4,6}处理2{2,4,4,6} 处理4{2,2,6,6}处理6{2,2,6MAX} {2,4,4,6} 处理0{4,4,6,6}处理2{2,4,6,6}处理4{2,4,6,6}处理6{2,4,4,MAX} … … 非常类似并集查找由于i一定小于vDo[i]所以不会有环。可以直接使用封装好的有向图的并集查找。
代码
class Solution { public: vectorint minReverseOperations(int n, int p, vectorint banned, int k) { vectorint vRet(n, -1); vRet[p] 0; queueint que; que.emplace(p); vectorint vNext(n); for (int i 0; i n; i) { vNext[i] i; } const int iMax 1000 * 1000; auto HasDo [](int b) { vNext[b] (b 2 n) ? vNext[b 2] : iMax; }; banned.emplace_back(p); for (const auto b : banned) { HasDo(b); } while (que.size()) { const auto cur que.front(); que.pop(); const int j0 max(0, cur - k 1); const int j1 min(cur, n - k); int next0 k - cur - 1 2 * j0; const int next1 k - cur - 1 2 * j1; for (next0 GetNext(vNext, next0, iMax); next0 next1;) { vRet[next0] vRet[cur] 1; HasDo(next0); que.emplace(next0); next0 GetNext(vNext, next0, iMax); } } return vRet; } int GetNext(vectorint vNext,const int b,const int iMax) { if ((iMax b) || (b vNext[b])) { return b; }; return vNext[b] GetNext(vNext, vNext[b],iMax); }; }; 其它
视频课程
如果你觉得复杂想从简单的算法开始可以学习我的视频课程。https://edu.csdn.net/course/detail/38771 我的其它课程https://edu.csdn.net/lecturer/6176 测试环境
win7 VS2019 C17 相关下载
doc版文档**排版好**https://download.csdn.net/download/he_zhidan/88348653
