This problem, I don’t know, it’s hard to write. Especially the third question, the meaning of the question is very vague, can only rely on guess.
Of course, the big guys are still fast, and I’m still too sloppy.
Week tournament portal
5926. The time it takes to buy a ticket
Methods a
Idea: Simulation
Time complexity: O(∑tickets)O(\sum tickets)O(∑tickets)
The intuitive idea is: use a queue to simulate the whole process of buying a ticket until the KKK individual buying a ticket is completed.
class Solution {
public:
int timeRequiredToBuy(vector<int>& tickets, int k) {
// Record the answers
int anw = 0;
// Use the queue to simulate the process of buying tickets
queue<int> q;
// Initialize the queue
for (auto t : tickets) {
q.push(t);
}
while (q.size(a) >0) {
// The person at the head of the queue buys a ticket
q.front()--;
// It takes one second
anw ++;
if (q.front() != 0) {
// If the person at the head of the queue is not finished, go to the end of the queue
q.push(q.front());
q.pop(a); }else {
// If the team leader buys out, he will leave the team.
q.pop(a);// Exit the loop if it is the KTH person.
if (k == 0) {
break; }}// Update the position of the KTH person in the queue.
if (k == 0) {
k = q.size(a)- 1;
} else{ k--; }}returnanw; }};Copy the codeMethod 2
Look for patterns
Time complexity: O(n)O(n)O(n)
When the KKK person buys the ticket:
- For I ∈[0,k) I \in[0,k) I ∈[0,k), min(ticketsi,ticketsk)\min(tickets_i,tickets_k)min(ticketsi,ticketsk) must be bought.
- For I ∈(k,n) I \in(k,n) I ∈(k,n), min(ticketsi, Ticketsk −1)\min(tickets_i, tickets_K-1)min(ticketsi, ticketSK −1) must be bought.
Therefore, the sum of the two parts is the answer. You just have to go through ticketsticketstickets once.
class Solution {
public:
int timeRequiredToBuy(vector<int>& tickets, int k) {
int sum = 0;
for (int i = 0; i <= k; i++) {
sum += min(tickets[i], tickets[k]);
}
for (int i = k+1; i < tickets.size(a); i++) { sum +=min(tickets[i], tickets[k]- 1);
}
returnsum; }};Copy the code5927. Inverts the node of even length group
Array array array array array array array array
Time complexity: O(n)O(n)O(n)
It’s a competition. It’s going to get ugly. Using an array to do the flip is easier, but requires extra O(n)O(n)O(n) storage.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; * /
class Solution {
public:
ListNode* reverseEvenLengthGroups(ListNode* head) {
// Put the nodes into the array
vector<ListNode*> vec;
for (autoh = head; h ! =nullptr; h = h->next) {
vec.push_back(h);
}
for (int i = 1, l = 0, r = 1; l < vec.size(a); i++) {if ((r-l)%2= =0) {
// Array flipping is easy,
reverse(vec.begin()+l, vec.begin()+r);
}
l = r;
r = min(int(vec.size()), l+i+1);
}
// Change the next pointer in sequence.
for (int i = 0; i+1 < vec.size(a); i++) {//cout << i << ", " << vec[i]->val << endl;
vec[i]->next = vec[i+1];
}
vec.back()->next = nullptr;
returnhead; }};Copy the codeDecodes oblique transposition codes
Idea: Simulation
Time complexity: O(n)O(n)O(n)
Simulate the process of decoding, see notes.
class Solution {
public:
string decodeCiphertext(string encodedText, int rows) {
// First compute the rows and columns of the auxiliary matrix
int r = rows;
int c = encodedText.size()/r;
// Define anw to store answers
string anw;
// Only the characters in the oblique position are meaningful.
The oblique position (I,j) in encodedText is (c*j + j+ I).
// encodedText[c*j+j+ I] to anw.
for (int i = 0; i < c; i++) {
for (int j = 0; j < r && j+i < c; j++) { anw += encodedText[c*j + j+i]; }}// Delete all trailing Spaces.
// However, I did not read this requirement in the title, so I was totally wrong in the competition.
while(anw.back() = =' ') {
anw.pop_back(a); }returnanw; }};Copy the code5929. Handle friend requests with restrictions
Look up the set
Time complexity: O(n+req∗res)O(N + Req *res)O(N +req∗ Res), where reqreqreq indicates the number of requests and resresres indicates the limited number
And look up the set template problem. Before each merge, check to see if any restrictions are violated. See the notes.
class Solution {
public:
// Store and look up an array of sets
int fa[1000];
// And find the set (with path compression)
int find (int r) {
int x = r;
while(x ! = fa[x]) { x = fa[x]; }while(r ! = fa[r]) {int t = fa[r];
fa[r] = x;
r = t;
}
return x;
}
vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
// Initialize and look up the set
for (int i = 0; i < n; i++) {
fa[i] = i;
}
// anw is used to store answers
vector<bool> anw;
// Process all requests in order
for (const auto req : requests) {
int u = req[0];
int v = req[1];
// find the set of u and v respectively
int fu = find(u), fv = find(v);
if (fu == fv) {
// If fu == fv, then u and v are in the same set.
anw.push_back(true);
} else {
// Check all res to see if the restriction is violated by combining fu and FV
bool flag = true;
for (const auto &res : restrictions) {
int ru = res[0], rv = res[1];
int fru = find(ru), frv = find(rv);
// ru and rv belong to fu and FV, so can't merge 🙅♀️
if ((fru == fu && frv == fv) || (fru == fv && frv == fu)) {
flag = false;
break;
}
}
anw.push_back(flag);
if (flag) {
// If we can, we canfa[fu] = fv; }}}returnanw; }};Copy the code