Hello, I’m Liang Tang.
Let’s take a look back at last weekend’s LeetCode contest, which was launched on the official account: Coder Liang
This week’s competition is sponsored by Ideal Car, and the grand prize is only given to the surrounding of ideal car, which is a little stingy compared with the iWatch given by a luxury company before…
The difficulty of the title of the game is not low, the game gave me the whole break several times, and even the fourth question is made after the game……
From the topic quality is still very high, very test thinking, is worth doing.
All right, without further ado, let’s get to the problem.
Find all K nearest neighbor subscripts in the array
Difficulty: do things
You are given an array of integers with indices starting at 0 nums and two integers key and k. K neighbor is one of the nums subscript subscript I, and there are at least a subscript j make | I – j | < = K and nums = = [j] key.
Returns all K nearest neighbor subscripts in ascending order as a list.
Answer key
Find all the subscripts I such that their k nearest neighbors are equal to key.
Since the data range is small, only one thousand, we can either enumerate each index first to determine whether there is a k-nearest neighbor equal to key, or conversely enumerate all positions equal to key to find the k-nearest neighbor of all these positions.
Both approaches are ok, but the first is simpler from a code point of view.
class Solution {
public:
vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
int n = nums.size(a); vector<int> res;
for (int i = 0; i < n; i++) {
for (int j = i-k; j <= i+k; j++) {
if (j < 0 || j >= n) continue;
if (nums[j] == key) {
res.push_back(i);
break; }}}returnres; }};Copy the codeStatistics can be extracted from artifacts
Difficulty: being fostered
There is an N x N size grid with subscripts starting at 0, and some artifacts are buried in the grid. Artifacts [I] = [r1i, C1i, r2i, c2i] indicates the placement of the ith artifact in the subgrid: artifacts[I] = [r1i, C1i, R2i, c2i]
(r1i, c1i)Is the firstiA workpieceUpper leftThe coordinates of the cell, and(r2i, c2i)Is the firstiA workpieceThe lower rightThe coordinates of the cell.
You will dig up some cells in the grid and clear them of landfill. If a part of an artifact is buried in a cell, that part of the artifact will be exposed. If all parts of an artifact are exposed, you can extract it.
Give you a two-dimensional integer array dig with subscripts starting at 0, where dig[I] = [ri, ci] indicates that you will be mining cells (ri, ci), returning the number of artifacts you can extract.
Generated test cases meet the following requirements:
- Two artifacts that do not overlap.
- Each artifact is covered at most
4Four cells. digDifferent elements in.
Answer key
The tip gives you the crucial information that each artifact covers a maximum of four cells and that there is no overlap between the artifacts. This one with or without this tip is on two different levels of difficulty.
What’s the use of having this hint? Since there are only 1E5 artifacts at most, even if each artifact has an area of 4, the respective order of magnitude of the whole would still be 1E5. So we can maintain whether all the cells have been excavated, and maintain the area of each cell that has not been excavated. When the unexplored area of a workpiece is 0, it means that the grid can be extracted.
As long as you pay attention to the last hint, it’s not hard to imagine that the code will be a little more complicated.
class Solution {
public:
int digArtifacts(int n, vector<vector<int>>& art, vector<vector<int>>& dig) {
// Map grid and artifact sequence number
map<pair<int.int>, int> mp;
// Store the unexplored area of each workpiece
map<int.int> area;
for (int i = 0; i < art.size(a); i++) {auto & a = art[i];
auto x1 = a[0], y1 = a[1], x2 = a[2], y2 = a[3];
int squ = (x2-x1+1) * (y2-y1+1);
area[i] = squ;
// Map each grid corresponding to artifact I to I
for (int _i = x1; _i <= x2; _i++) {
for (int _j = y1; _j <= y2; _j++) {
auto pnt = make_pair(_i, _j); mp[pnt] = i; }}}int ret = 0;
for (auto& vt: dig) {
int x = vt[0], y = vt[1];
auto p = make_pair(x, y);
if (mp.count(p) == 0) continue;
// tool mp[p] unexcavated area -1, when the area is 0 can be extracted
area[mp[p]]--;
if (area[mp[p]] == 0) ret++;
}
returnret; }};Copy the codeMaximize the top element after K operations
Difficulty: being is being fostered
You are given an array of integers with subscripts starting at 0, nums, which represents a stack where nums[0] is the element at the top of the stack.
In each operation, you can do one of the following:
- If the stack is not empty, remove the element at the top of the stack.
- If there are one or more removed elements, you can select any of them and add them back to the top of the stack, which becomes the new top of the stack element.
You’re also given an integer k, which represents the total number of operations you need to perform.
Return the maximum number of elements at the top of the stack after exactly k operations. If the stack must be empty after k operations, return -1.
Answer key
During the game, I made a mistake in reading the topic and gave it to me. I made many mistakes before I finally passed. Further, it is important to read and calm down during the competition.
If we look at the range of data, we will find the difficulty of this problem. The array length and k are both very large. In particular, k has a range of 1e9. Heads are no good, we have to start with tails, and since it’s too expensive to simulate every step of the way, can we do it the other way around, enumerating how likely each element is to be the answer?
We maintain whether each element is the last value on the top of the stack, and then pick the largest of all of these possible scenarios, and that’s the answer.
What are the conditions for the ith element to be the last element to appear at the top of the stack?
The first thing I need to do is look at everything that goes off the stack before I, so that takes I minus 1 steps. After these operations, if there is anything left, several situations can occur. If the number of remaining steps is even, then it’s easy, we just do the insert and delete over and over again, and I is guaranteed to be at the top of the stack.
What if it’s odd?
If I have an odd number of steps left, and I have to do some sorting, if I have 1, then obviously I can’t be the answer anyway. What if the number of steps is greater than one? Assuming the number of remaining steps is 3, we can either insert an element, delete it and I, and then insert I, or we can delete I and I +1, and then insert back into I, and that will keep I at the top of the stack. But there’s a condition that there’s at least one element that’s been deleted or there’s at least one element after I. It’s like limiting the range of I, which has to be between (1, n-1).
The code is as follows:
class Solution {
public:
int maximumTop(vector<int>& nums, int k) {
int n = nums.size(a);int ret = - 1;
int maxi = - 1;
for (int i = 0; i < n; i++) {
if (k == 0) {
ret = max(ret, nums[i]);
break;
}
int u = nums[i];
ret = max(ret, maxi);
// If the number of remaining steps is even, then u can be the answer
if (k % 2= =0) ret = max(ret, u);
else {
// Otherwise, k > 1 and I in the middle of (1, n-1) are required
if (k > 1 && (i > 0 || i < n- 1)) ret = max(ret, u);
}
maxi = max(maxi, u);
k--;
}
returnret; }};Copy the codeFurther thinking and induction, we can make new discoveries.
When k > n, the maximum value of nums must be reached. What if k is equal to n? No matter what we do, we can’t make the last value the answer, because deleting the previous n-1 element takes n-1 step, so the answer is Max (nums[:n-1]).
What if k is less than n? We can either delete the first K elements so that k+1 is at the top of the stack, or we can choose the largest of the first K -1 elements as the answer.
At the same time, if we consider extreme cases such as n=1, k=0, etc., the whole code becomes simpler, so we use Python for demonstration purposes.
class Solution:
def maximumTop(self, nums: List[int], k: int) - >int:
n = len(nums)
if n == 1:
return -1 if k % 2= =1 else nums[0]
if k <= 1:
return nums[k]
if k > n:
return max(nums)
if k == n:
return max(nums[0: n - 1])
# 1 < k < n
return max(max(nums[0: k - 1]), nums[k])
Copy the codeThe minimum weighted subgraph of the required path is obtained
Difficulty: being fostered fostered fostered fostered
You are given an integer n, which represents the number of nodes in a weighted directed graph, numbered from 0 to n-1.
B. edges[I] = [fromi, toi, weighti]; b. edges[I] = [fromi, toi, weighti]
Finally, you are given three distinct integers srC1, SRC2, and dest, representing three distinct points in the graph.
Please select an edge weight and the smallest subgraph from the graph, so that starting from SRC1 and SRc2, in this subgraph, can reach dest. If such a subgraph does not exist, return -1.
The points and edges in the subgraph should all be part of the original graph. The sum of the edge weights of a subgraph is defined as the sum of the weights of all the edges it contains.
Answer key
Obviously, this is a graph problem, which is pretty rare in LeetCode, and although it’s not that hard in graph theory, it’s definitely top level for those of you who rarely do graph theory problems.
The difficulty of this problem is that we need to find two subgraphs that are formed by starting from two different points, and we need to find two subgraphs that are optimal, which is obviously very troublesome and almost impossible to do. So here, we can come to the conclusion that this is another problem that needs to be constructed in reverse, frontal assault is not good.
So how do you reverse that? My idea during the competition was to reverse the graph, so that the process of finding DEST from two starting points S1 and S2 became the process of finding S1 and S2 from dest. Starting from Dest, it is much easier to find paths s1 and S2 respectively, but this still fails to reach the premise of optimal subgraph formed at the same time. So I just got stuck. I couldn’t figure it out.
We can enumerate node X and calculate the shortest path from S1, S2 and dest to X at the same time. The sum of these three paths is the answer.
We need to reverse the graph when calculating the shortest path from dest, because it is essentially from X to DEST, but dest is certain, so it is easier for us to calculate the shortest path from DEST.
In the shortest path algorithm of graph theory, we can quickly solve the shortest path from one vertex S to all other points. In fact, there are many algorithms, such as the famous Dijkstra and SPFA, I personally prefer to use SPFA, because it is easier to implement, almost similar to wide search.
Therefore, we only need to establish forward and reverse graphs at the same time, and then use SPFA for three times respectively to calculate the shortest circuit from SRC1, SRC2 and Dest points to other points, enumerate X, and find the optimal solution.
The code is as follows:
typedef pair<int.int> pii;
class Solution {
public:
vector<vector<pii>> g, rg;
Push_back ({v, w}); push_back({v, w})
void add_edge(vector<vector<pii>>& g, int u, int v, int w) {
g[u].push_back({v, w});
}
void spfa(vector<vector<pii>> &g, vector<long long>& dis, int s) {
// SpFA shortest path algorithm
dis[s] = 0;
queue<int> que;
que.push(s);
// Whether the maintenance point is in the queue. If it is already in the queue, avoid adding it repeatedly
vector<int> st(dis.size(), 0);
st[s] = 1;
while(! que.empty()) {
int u = que.front(a); que.pop(a); st[u] =0;
for (auto& x: g[u]) {
int v = x.first, w = x.second;
if (dis[v] > dis[u] + (long long)w) {
dis[v] = dis[u] + (long long)w;
if (st[v] == 0) {
que.push(v);
st[v] = 1;
}
}
}
}
}
long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
g.resize(n); rg.resize(n);
for (auto & e: edges) {
int u = e[0], v = e[1], w = e[2];
add_edge(g, u, v, w);
add_edge(rg, v, u, w);
}
vector<long long> d1(n, 1e11).d2(n, 1e11).d3(n, 1e11);
Src1, src2, dest is the shortest path of the source. Note that dest uses the reverse graph
spfa(g, d1, src1);
spfa(g, d2, src2);
spfa(rg, d3, dest);
long long res = 0x3f3f3f3f3f3f3f3f;
// enumerate intermediate points
for (int i = 0; i < n; i++) {
res = min(res, d1[i] + d2[i] + d3[i]);
}
return res >= 1e11 ? - 1: res; }};Copy the codeThe difficulty of this problem is not small, in addition to the ingenious thinking is difficult to think of, the requirements for coding is not low, want to complete the realization of the shortest circuit algorithm in the competition for non-competition players is obviously more difficult. But the quality is pretty good, and I personally think it’s even as good as the professional competition questions.
Although it is a pity that the performance of this week’s competition is not good, but the quality of the questions is still good, it is worth a try.
Ok, that’s all for this question. Thank you for reading.