Lazy, water two sets of rolling to sleep.
Week tournament portal
Check if two strings are nearly equal
Count
Time complexity: O(n)O(n)O(n)
The idea is more intuitive. Count the number of occurrences of each character in word1word1word1, and then count the number of occurrences in word2word2word2, and then check the difference between the two.
class Solution {
public:
bool checkAlmostEquivalent(string word1, string word2) {
// Count arrays
int cnt[26] = {0};
// iterate over word1 and add
for (auto c : word1) {
cnt[c-'a'] + +; }// iterate over word2, subtract
for (auto c : word2) {
cnt[c-'a']--;
}
// Check the difference
for (auto c : cnt) {
if (c < - 3 || c > 3) {
return false; }}return true; }};Copy the code5911. Simulated walking Robot II
Idea: Simulation
Time complexity: O(len∗op)O(len*op)O(len∗op). Opopop indicates the number of operations.
It’s a perfectly normal simulation. It just needs to be optimized.
Given that each move is capped at 1E51E51E5 and the number of operations is capped at 1E41E41E4, direct emulation inevitably imposes a timeout.
Looking at the image above, it’s not hard to see that the robot “only goes in the outer circle.” Therefore, the robot returns to its actual position with every Lenlenlen step, lenlenlen being the perimeter.
So, numnumnum mod Lenlenlen before each move. This ensures that you don’t move more than Lenlenlen per step. So the time complexity of the move operation is reduced to O(len)O(len)O(len).
Note that numnumnum is divisible by Lenlenlen. The position of the robot will not change, but the orientation may change.
class Robot {
public:
/ / w width; H high; Len circumference
int w, h, len;
// (x,y) robot position;
// dir robot orientation:
// 0 - "East"
// 1 - "North"
// 2 - "West"
// 3 - "South"
int x = 0, y = 0, dir = 0;
// dx[dir] and dy[dir] represent the change in x and y as we move a step in the direction of dir
int dx[4] = { 1.0.- 1.0};
int dy[4] = { 0.1.0.- 1};
Robot(int width, int height) : w(width), h(height), len(w*2+h*24 -) {}
void move(int num) {
// Avoid loop
num %= len;
// If num is 0, let the robot run around to avoid orientation problems
if (num == 0) {
num = len;
}
while (num > 0) {
int nx = x + dx[dir], ny = y + dy[dir];
// Try to take a step in the dir direction
if (0 <= nx && nx < w && 0 <= ny && ny < h) {
// Make a successful move.
x = nx, y = ny;
num--;
} else {
// You can't walk, you have to turn around.
dir = (dir+1) &3; }}}vector<int> getPos(a) {
return vector<int>{x, y};
}
string getDir(a) {
const vector<string> name{"East"."North"."West"."South"};
returnname[dir]; }};/** * Your Robot object will be instantiated and called as such: * Robot* obj = new Robot(width, height); * obj->move(num); * vector
param_2 = obj->getPos(); * string param_3 = obj->getDir(); * /
Copy the code5912. Maximum beauty value for each query
Thinking: sort, dichotomy
Time complexity: O(n∗lgn)O(n*\lg n)O(n∗ LGN)
First, sort itemSitemsitems in ascending order by price. Then for each queryQueryQuery, the largest III can be found in two halves, and the price of the first iii itemItemItems is no more than that of the QueryQueryQuery. The maximum beauty value of the three itemitemitems is the answer.
The beauty value of ItemiITEM_iitemi can be modified to the maximum value of the previous three ItemItemItems by preprocessing with time complexity O(n)O(n)O(n). This reduces the time complexity of each query to O(lgn)O(\lg n)O(LGN).
class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
// Sort items in ascending order by price
sort(items.begin(), items.end(), [] (const auto &lhs, const auto &rhs) {
return lhs[0] < rhs[0];
});
// Preprocess the value of items[I] to the maximum value of items[0.. I].
for (int i = 1; i < items.size(a); i++) { items[i][1] = max(items[i- 1] [1], items[i][1]);
}
// Anw is the answer.
vector<int> anw;
// Start processing all queries in order
for (auto q : queries) {
// use upper_boud to find the first item whose price is greater than q and call it.
auto it = upper_bound(items.begin(), items.end(), vector<int>{q, q}, [](const auto &lhs, const auto &rhs) {
return lhs[0] < rhs[0];
});
if (it == items.begin()) {
// When it refers to the first element, there is obviously no item whose price is less than or equal to q
anw.push_back(0);
} else {
// Conversely, the beauty value of the previous item in it is the answer.
anw.push_back((*--it).at(1)); }}returnanw; }};Copy the code5913. Maximum number of tasks you can schedule
Dichotomy, greed
Time complexity: O(n∗lgn∗lgn)O(n*\lg n*\lg n)O(n∗ LGN ∗ LGN)
Imagine that if you store the plan to complete MMM tasks, there must be a plan to select the maximum strength of MMM workers. At the same time, it is not difficult to conclude that there must also be a scheme to complete m−1m −1m tasks.
Conversely, if there is no solution to complete MMM tasks, there must be no solution to complete M +1m+1m+1 tasks.
Therefore, we can try to find the maximum value of MMM by dichotomy.
Then, the question becomes, “Given an M, how can we determine whether the solution exists?”
First, choose MMM workers with maximum force value. Select tasks in order of strength from lowest to highest:
- If there are tasks that can be done, just pick one. Because the strength of subsequent workers is not lower.
- If not, the current worker must take the medicine. If there is no medicine to take, or no task to choose after taking the medicine, the plan is not stored. Because every worker has to complete a task.
If each worker has a task to complete, the plan is stored, otherwise not stored.
The comments are very detailed
class Solution {
public:
bool check(const vector<int> &t, const vector<int> &w, int p, int s, int l) {
// Initializes a multiset for personal selection of tasks
multiset<int> c;
for (auto v : t) { c.insert(v); }
// W has been sorted, select the largest l workers.
for (int i = w.size()-l ; i < w.size(a); i++) {Select * from c[begin,it); select * from c[begin,it);
auto it = c.upper_bound(w[i]);
if(it ! = c.begin()) {
// Choose the smallest one, the code is easy to write.
c.erase(c.begin());
continue;
}
// There is no alternative, take the medicine.
if (p <= 0) {
// If there is no medicine available, the scheme does not exist.
return false;
}
p--;
// Select the first task whose value is greater than w[I]+s. Then c[begin,it] tasks can be selected arbitrarily.
it = c.upper_bound(w[i]+s);
if(it ! = c.begin()) {
/ /!!!!!! Mind you, he's taking his meds, as big as possible. Because subsequent workers may have less strength than he does.
c.erase(--it);
continue;
}
// There is no option after taking the medicine.
return false;
}
return true;
}
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
// Sort by power value in ascending order, easy to use later
sort(workers.begin(), workers.end());
int l = 0, r = workers.size(a);// Start dichotomy
while (l <= r) {
int mid = (l+r)>>1;
// Start checking
if (check(tasks, workers, pills, strength, mid)) {
[mid, r] [mid, r] [mid, r
l = mid+1;
} else {
[l, mid-1] [l, mid-1
r = mid- 1; }}// select * from mid (+1); // Select * from mid (+1);
return l- 1; }};Copy the code