英文网站怎么做外贸推广,华北建设招标网官方网站,网站的总体方案,俄罗斯乌克兰局势最新消息绪论
最近发现Leetcode每周的周赛难度挺适合我的#xff0c;而且时间也比较友好#xff08;不像Codeforces每次都是半夜#xff09;。所以连续参加了三周的周赛。这次才想起来应该记录一下自己的参赛历程。一方面是总结经验#xff0c;另一方面有了记录就更有动力去提升而且时间也比较友好不像Codeforces每次都是半夜。所以连续参加了三周的周赛。这次才想起来应该记录一下自己的参赛历程。一方面是总结经验另一方面有了记录就更有动力去提升去参加下一次比赛。
题目分析
题目链接https://leetcode-cn.com/contest/weekly-contest-284/ 还是往常一样四道题难度依次提升。
A找出数组中的所有 K 近邻下标
简单模拟对于每一个key其附近的2k1个元素都是合法的需要注意处理重复。为此我们用一个last变量进行记录上一次记录的最后一个元素的位置。
namespace A {class Solution {public:vectorint findKDistantIndices(vectorint nums, int key, int k) {vectorint ret;int n nums.size();int last -1;auto add [](int l, int r) {r min(r, n - 1);l max(l, last 1);for (; l r; l) ret.push_back(l);last r;};for (int i 0; i n; i) {if (nums[i] key) {add(i - k, i k);}}return ret;}};
}
B统计可以提取的工件
也是简单模拟因为数据量比较小所以无脑做就可以。如果数据量比较大可能是一道比较有意思的题。
namespace B {class Solution {public:int digArtifacts(int n, vectorvectorint artifacts, vectorvectorint dig) {vectorvectorbool vis(n, vectorbool(n));for (auto pr : dig) {vis[pr[0]][pr[1]] true;}int x0, x1, y0, y1;int ans 0;auto check [](auto tool) - bool {x0 tool[0]; y0 tool[1]; x1 tool[2]; y1 tool[3];for (int i x0; i x1; i) {for (int j y0; j y1; j) {if (!vis[i][j]) return false;}}return true;};for (auto tool : artifacts) {if (check(tool)) ans;}return ans;}};
}
CK 次操作后最大化顶端元素
这个题如果还是想要通过模拟去做那么就会毫无头绪。因为观察到最后要求的是栈顶的元素最大。而我们如何进行这k次操作的情况是非常多的我们应该观察哪些元素可以通过k次操作放到栈顶。 假如对栈中的元素从1开始编号。如果我们直接出栈k次那么是可以得到第k1个元素的这个也是我们能够看到的最后一个值。 对1到k-1个元素我们都可以通过将他们的在最后一步入栈从而让他们放到栈顶。 需要进行讨论的就是我们能够让第k个元素放到栈顶答案是不行可以通过简单模拟验证一下。下面我们简单证明一下。 为了让第k个元素放到栈顶我们必须弹出前k-1个操作这样我们就只能再操作一下而一下无论是弹出还是插入都不能让第k个元素放到栈顶。
经过上面的讨论我们发现其实题目的意思就是让我们去找前k1个元素除去第k个元素的最大值。
但是还需要注意的一点是当n为1的情况有时间我再证明一下当时没怎么想清楚在这里还wa了一发
namespace C {/** 前k - 1的最大值肯定可以取到* 第k个元素取不到* 第k 1个元素可以取到*/class Solution {public:int maximumTop(vectorint nums, int k) {int n nums.size();if (n 1 (k % 2 1)) return -1;int ans -1;int kk min(k - 1, n);for (int i 0; i kk; i) {ans max(ans, nums[i]);}if (k n) {ans max(ans, nums[k]);}return ans;}};
}
D得到要求路径的最小带权子图
这个题差一点点就做出来了思路是正确的但是编码有一个小失误忘记了优先队列元素的含义
刚开始的思路是求src1和src2到dest的最短路的和如果两个的最短路有重复就减去重复的。后来发现的例外主要是因为减去的那个重复不一定是最大的存在不是最短路的两个路径但是重复的成分很高整体的和反而更小。
后来再思考了一下那我不知道那个是重复路径的起点不如我遍历一下让每一个都当做起点。这样子的路径和就是dis[src1][k]dis[src2][k]dis[k][dest] 想到这里我觉得我找到了正确的思路想要用一下Floyed去求最短路。一看节点个数1e5然后就意识到肯定会超时。因为Floyed的复杂度是O(n^3) 那么只能进行优化考虑正向建图求src1和src2到每个节点的距离再反向建图求每个节点到dest的距离。因为数据量很大所以要求不能使用简单的Dijkstra要使用最小堆优化的Dijkstra这样每次Djikstra的复杂度是O(nlogn)最后遍历一下的复杂度是O(n)。
但是在写Dijkstra的时候我是抄的板子没有去理解优先队列节点的含义最终导致出错了也算是咎由自取吧。
吃了个饭回来又过了泪目。
namespace D {/** 假如src1在src2到dest的路径上或者返过来则是平凡的情况*/class Solution {using ll long long;struct HeapNode {ll d;int u;HeapNode(ll d_, int u_):d(d_), u(u_){}bool operator (const HeapNoderhs) const {return d rhs.d;}};public:long long minimumWeight(int n, vectorvectorint edges, int src1, int src2, int dest) {vectorvectorpairint, int graph(n), reverse_graph(n);//建图int u, v, w;for (auto edge : edges) {u edge[0]; v edge[1]; w edge[2];graph[u].emplace_back(v, w);reverse_graph[v].emplace_back(u, w);}vectorll dis1(n), dis2(n), dis3(n);vectorbool vis(n);auto dijkstra [n, vis](auto graph, auto dis, int s) {priority_queueHeapNode q;for (int i 0; i n; i) {dis[i] LONG_LONG_MAX;}dis[s] 0;for (int i 0; i n; i) vis[i] false;q.emplace(0, s);while (!q.empty()) {HeapNode x q.top(); q.pop();int u x.u;if (vis[u]) continue;vis[u] true;//print(u);auto edges graph[u];for (auto pr : edges) {int v pr.first;int w pr.second;//print(\t, u ,v ,w);if (dis[v] dis[u] w) {dis[v] dis[u] w;q.emplace(dis[v], v);}}}};dijkstra(graph, dis1, src1);dijkstra(graph, dis2, src2);dijkstra(reverse_graph, dis3, dest);ll ans LONG_LONG_MAX;for (int k 0; k n; k) {if (dis1[k] LONG_LONG_MAX || dis2[k] LONG_LONG_MAX || dis3[k] LONG_LONG_MAX) {continue;}ans min(ans, dis1[k] dis2[k] dis3[k]);}if (ans LONG_LONG_MAX) return -1;else return ans;}};
}
经验总结
重复的边对Dijkstra算法是没有影响的Dijkstra算法需要的是最小堆而默认的小于号得到的是最大堆因此应该在重载小于号的时候让含义反过来。之所以会出现这样子是和堆的实际生成有关系上游下游什么的已经忘记了有时间复习一下为了避免初始化为正无穷的时候两个正无穷相加溢出我们可以在相加前进行判断。需要注意Dijkstra对节点标记为已处理是在弹出堆顶元素进行的而不是在入堆的时候进行的。这一点和一般的BFS不同。Dijkstra算法正确性主要是距离源节点最近的节点的最短路径已经确认。可以放心大胆地用emplace虽然不知道为什么有一次在emplace的时候报错了当时心态很崩。
