Hello, I’m Liang Tang.
Today is Monday, let’s talk about the 285th game of LeetCode week as usual.
This competition is sponsored by shell, the prize is good or bad, surprisingly only 1-10 can get the shell push code…… Live in Bengbu a little.
So without further ado, let’s look at the problem.
Count the number of peaks and valleys in the array
You are given an array of integers with indices starting at 0, nums. If the nearest unequal neighbor to I on both sides is less than nums[I], then the subscript I is part of a peak in NUMS. Similarly, if the nearest unequal neighbor to I on both sides has a value greater than nums[I], then the subscript I is part of a valley in NUMS. For adjacent subscripts I and j, if nums[I] == nums[j], the two subscripts are considered to belong to the same peak or valley.
Note that for a subindex to be part of a peak or valley, it must have unequal neighbors on both the left and right sides.
Returns the number of peaks and valleys in NUMS.
solution
The data range is very small, 100 numbers at most, so you can basically play with anything.
We directly solve by violence, first traverse each element nums[I], and then find the first and nums[I] elements forward and backward, respectively, and determine whether NUMs [I] can form peaks or valleys.
class Solution {
public:
int countHillValley(vector<int>& nums) {
int ret = 0;
int n = nums.size(a);for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i- 1]) continue;
int l = i - 1;
while (l > - 1 && nums[l] == nums[i]) l--;
int r = i+1;
while (r < n && nums[r] == nums[i]) r++;
if (l < 0 || r >= n) continue;
if (nums[l] < nums[i] && nums[r] < nums[i]) ret++;
if (nums[l] > nums[i] && nums[r] > nums[i]) ret++;
}
returnret; }};Copy the codeCount the number of collisions on the road
There are n cars on an infinite stretch of highway. Cars are numbered from 0 to N-1 from left to right, each in a unique location.
You are given a string of n directions from 0. Directions [I] can be ‘L’, ‘R’, or ‘S’ to indicate that the ith car is going left, right, or staying in the current position, respectively. Each car moves at the same speed.
The number of collisions can be calculated as follows:
- When the two cars move in the directionOn the contraryWhen a car collides, the number of collisions increases
2。 - When a moving car collides with a stationary car, the number of collisions increases
1。
After a collision, the vehicle involved will no longer be able to move and remain in the collision position. In addition, cars cannot change their state or direction of movement.
Returns the total number of collisions that occurred on this road.
solution
At first glance, this problem seems a bit bluffing. First, the scope of the problem is not small, with a maximum of 1E5 cars, so the whole situation will be very complicated.
But if we calm down and analyze the question carefully, we will find it is not so difficult.
We can analyze a general case, for a vehicle with subscript I, there are three possibilities: left to right or stop. Let’s look at left first, if car I is going left, then if there’s a car going right on the left of car I, there’s going to be a collision. But how many collisions? It’s a matter of how many cars you have.
If there are x cars to the left of I moving to the right, then the first one will collide with I, which will cause two collisions. After that, the two cars stop and the remaining X-1 car collides with the stationary vehicle, causing x-1 collision. So we’re going to have x plus 1 collisions.
In the second case, car I stops, which affects both the car to the left of I and the car to the right of I. If there are cars going right to the left of I, then all of those cars in turn will collide with I. Similarly, if there are cars to the right of I that are going to the left, and there are cars to the right of I that are going to be moving towards it, there are going to be several collisions.
In the last case, car I turns to the right. In this case, it is impossible to determine whether there will be a collision. It needs to be determined according to the situation on the right side of car I.
A little generalization shows that we need to maintain two values during the process of judging a collision from left to right. The first value is whether there is a stopped vehicle on the left or a stopped vehicle due to a collision. The second value is how many right-moving cars exist on the left, and we can easily get the answer by maintaining these two data points.
class Solution {
public:
int countCollisions(string dir) {
int ret = 0;
int r = 0;
bool has_stop = false;
int n = dir.size(a);for (int i = 0; i < n; i++) {
if (dir[i] == 'S') {
// All cars to the left and right of I will collide
has_stop = true;
ret += r;
r = 0;
continue;
}
if (dir[i] == 'L') {
// if there are x right-going cars on the left, x+1 collision occurs
if (r) {
ret += r+1;
has_stop = true;
r = 0;
continue;
}
// If there is a stopped car on the left, a collision occurs
if(has_stop) { ret++; }}if (dir[i] == 'R') r++;
}
returnret; }};Copy the codeMaximum score in archery
Alice and Bob are rivals in an archery competition. The rules are as follows:
- Alice first shot
numArrowsAn arrow, and then Bob shootsnumArrowsArrow. - Points are calculated according to the following rules:
- The target has integer scoring areas ranging from
0到11(including0和11). - Each area on the target corresponds to a score
k(the range is0到11), Alice and Bob are scoring, respectivelykArea hitak和bkArrow. ifak >= bk, so Alice has tokPoints. ifak < bk, Bobk分 - if
ak == bk == 0Then no one gets itkPoints.
- The target has integer scoring areas ranging from
- For example, Alice and Bob both score at
11Areas of the shot2An arrow, so Alice has to11Points. If Alice’s score is zero11Areas of the shot0An arrow, but Bob shot at the same area2One arrow, so Bob has to11Points.
You are given the integer numArrows and an array of integers of length 12, aliceArrows, which represents the number of arrows That Alice shoots in each scoring area from 0 to 11. Now, Bob wants to maximize the total score he can get.
Returns the array bobArrows, which represents the number of arrows Bob shot in each scoring area from 0 to 11. And the sum of bobArrows should be equal to numArrows.
If there are more than one way for Bob to get the maximum total score, return any of them.
solution
If you look at the data range, you’ll see that the range in this case is quite large, with numArrows at most 1e5.
Secondly, many students estimate that they will forget the direction of greed as soon as they get it, but it is not difficult to find that greed is easy to appear counter examples. No matter we are greedy according to the price ratio, or simply according to a single step to maximize the return of greed can not solve the problem of counter examples.
Only if the mind is bright, it can be reflected. All problems that cannot be solved by greed are nine out of ten dynamic programming problems, and this is no exception.
Familiar with the backpack problem, will find that this is a naked 01 backpack problem. If Bob makes more shots than Alice, Bob gets the corresponding points. The optimal case, of course, is that Bob shoots exactly one more times than Alice. We can think of region I as a volume Alice [I]+1, a good of value I, and since each region has a maximum of one win, it is equivalent to a maximum of one piece of each good, which translates into the classic 01 backpack problem.
But 01 backpack is only a maximum value, and in this case, the need to restore the backpack construction process.
A simple way to do this is to use a separate array to record the strategy taken for each state transition:
typedef pair<int.int> pii;
class Solution {
public:
vector<int> maximumBobPoints(int num, vector<int>& ali) {
// STG record policy
vector<vector<int>> dp(13, vector<int>(num+2.0)), stg(13, vector<int>(num+2.0));
for (int i = 1; i < 12; i++) {
int v = ali[i]+1;
for (int j = 0; j <= num; j++) {
if (j < v) {
dp[i][j] = dp[i- 1][j];
continue;
}
if (dp[i- 1][j-v] + i > dp[i- 1][j]) {
dp[i][j] = dp[i- 1][j-v] + i;
stg[i][j] = i;
}else dp[i][j] = dp[i- 1][j]; }}vector<int> ret(12);
int tot = num;
for (int i = 11; i > 0; i--) {
// If the policy is greater than 0, restore the related policy
if (stg[i][tot] > 0) {
ret[i] = ali[stg[i][tot]] + 1;
tot -= ret[i];
}
}
ret[0] = tot;
returnret; }};Copy the codeHowever, there is a more subtle way to undo the policy, we do not need to record the policy, but directly from the DP array.
We judge the size relationship between DP [I][j] and DP [i-1][j], where I represents the strategy and J represents the state, namely the volume of the backpack. If dp[I][j] > DP [i-1][j], what does this mean?
It shows that for the same state J, better results are obtained after using strategy I, so it must be because strategy I is adopted, because the difference between dp[I][j] and DP [i-1][j] is only I. So we just have to work backwards from this property, and we can do the same thing.
class Solution {
public:
vector<int> maximumBobPoints(int num, vector<int>& ali) {
vector<vector<int>> dp(13, vector<int>(num+2.0));
for (int i = 1; i < 12; i++) {
int v = ali[i]+1;
for (int j = 0; j <= num; j++) {
if (j < v) {
dp[i][j] = dp[i- 1][j];
continue;
}
dp[i][j] = max(dp[i- 1][j-v] + i, dp[i- 1][j]); }}vector<int> ret(12);
int tot = num;
for (int i = 11; i > 0; i--) {
// Determine whether policy I is adopted
if (dp[i][tot] > dp[i- 1][tot]) {
ret[i] = ali[i]+1;
tot -= (ali[i]+1);
}
}
ret[0] = tot;
returnret; }};Copy the codeI came up with the knapsack solution during the competition, but since I used the compressed writing method instead of using a two-dimensional array, I couldn’t go back to the strategy.
In my desperation, I noticed that the scope of this strategy is very small, only 12, so I can enumerate all the states by force to find the states that satisfy the optimal solution. Furthermore, it was found that since the states had been enumerated by violence, there was no need to use DP any more, and we could directly find the optimal result from violence.
typedef pair<int.int> pii;
class Solution {
public:
vector<int> maximumBobPoints(int num, vector<int>& ali) {
vector<int> ret(12.0);
int maxi = 0;
// Binary enumeration state
for (int s = 0; s < (1 << 12); s++) {
int used = 0, score = 0;
for (int i = 1; i < 12; i++) {
if (s & (1 << i)) {
used += ali[i] + 1;
// If the consumption is greater than num, it is not true
if (used > num) break; score += i; }}// Maintain maximum score
if (score > maxi) {
for (int i = 1; i < 12; i++) {
if (s & (1 << i)) {
ret[i] = ali[i] + 1;
}else ret[i] = 0;
}
maxi = score;
ret[0] = num - used; }}returnret; }};Copy the codeSo there are a couple of ways to write this problem, and obviously the last one is not only the easiest to code but also the most efficient. The quality of this problem is really good, worth repeated mining, it is best to try every solution again, for improving the coding ability is very helpful.
The longest string repeated by a single character
I give you a string s with subscripts starting at 0. QueryCharacters, a string with k length starting at 0 and an integer index array queryIndices with k length starting at 0, both describe k queries.
The i-th query updates the character in S at the queryIndices[I] to queryCharacters[I].
Lengths return an array of k lengths, of which [I] is the length of the farthest single string repeated in s after the i-th search.
solution
This is a tricky one when you look at the data range. First of all, the string is long, 1E5, and it changes a lot, 1E5, and every change is accompanied by a query, and the query is of 1e5 magnitude. Even if we could get the result at O(n)O(n)O(n) for every query, it would still time out.
If you’re at a race and you don’t have a clue, congratulations, you can go to lunch early. Because nine times out of ten, a problem like this requires some kind of algorithm or data structure, and you can’t do it without knowing the algorithm or data structure.
For this problem, we need to be able to quickly update and query the contents of an interval (string) with as little complexity as possible. There are several such data structures, such as line segment tree, tree array, etc., combined with the requirements of this problem, it is not difficult to find that we can use line segment tree to solve.
If you want to understand how line trees work, you can click on the line Tree link
We use the segment tree to maintain three values within an interval, the same consecutive substring length from the left, the same consecutive substring length from the right, and the maximum continuous substring length in the middle. We use FWD (FOward), BKD (Backward) and Meg (Merge) to represent these three values respectively.
If we want the three values of the interval [l, r], we can first split the interval into two parts, [l, m) and [m, r). Here m is the midpoint of L and R.
We can adopt the idea of divide-and-conquer, first solve the left and right parts of FWD, BKD and Meg values, and then we can discuss the case by case. In fact, there are not many cases to be discussed, only one case is that the left and right intervals can be joined together, that is, s[m-1] == s[m], where s is the original string. When this condition is met, it indicates that the left and right ranges can be connected in the middle.
If the conditions are not met, the FWD of the left interval is the FWD of the whole area, the BKD of the right interval is the BKD of the whole area, and the maximum Meg of the left and right interval is the maximum Meg of the whole area.
If the conditions are met, there are still several situations. Firstly, Meg has an additional value: L.BB + R.WD. Since the left and right intervals can be connected, BKD of the left interval and FWD of the right interval can be connected together, and the length after the connection is the sum of the two.
Secondly, if the left interval is exactly the same or the right interval is exactly the same, then FWD of the left interval can be connected to FWD of the right interval, and similarly, if the right interval is exactly the same, then BKD of the right interval can be connected to BKD of the left interval.
In this way, with recursion and divide and conquer, we only need to judge a few cases to get the answer at each query, instead of iterating through the string to get the answer, so the complexity of the query is the complexity of the recursion in the tree: O(logn)O(\log n)O(logn). In this way, AC.
The complete code is as follows:
int n;
// Store FWD, BKD and Meg respectively
struct P {
int fwd, bkd, meg;
P() {}P(int f, int b, int m): fwd(f), bkd(b), meg(m) {}
};
P tree[300050];
void push_up(string &s, int lef, int rig, int l, int r, int m, int k) {
tree[k].fwd = tree[lef].fwd;
tree[k].bkd = tree[rig].bkd;
tree[k].meg = max(tree[lef].meg, tree[rig].meg);
// Check whether the middle can be joined
if (s[m- 1] == s[m]) {
if (tree[rig].bkd >= r - m) tree[k].bkd += tree[lef].bkd;
if (tree[lef].fwd >= m - l) tree[k].fwd += tree[rig].fwd;
tree[k].meg = max(tree[k].meg, tree[lef].bkd + tree[rig].fwd); }}void build(string &s, int l, int r, int k) {
// Create a tree
if (r <= l+1) {
tree[k] = {1.1.1};
return ;
}
int m = (l + r) >> 1;
int lef = k << 1, rig = k << 1 | 1;
// it is recursive
build(s, l, m, lef);
build(s, m, r, rig);
// Find the middle of the left and right interval
push_up(s, lef, rig, l, r, m, k);
}
void update(string &s, int l, int r, int k, int idx, char m) {
if (r - l == 1 && l == idx) {
s[l] = m;
return ;
}
int mid = (l + r) >> 1;
// Determine the left or right side of the update according to the update
if (idx < mid) update(s, l, mid, (k << 1), idx, m);
else update(s, mid, r, (k << 1 | 1), idx, m);
// Update the middle
int lef = k << 1, rig = k << 1 | 1;
push_up(s, lef, rig, l, r, mid, k);
}
class Solution {
public:
vector<int> longestRepeating(string s, string query, vector<int>& queryIdx) {
n = s.length(a);build(s, 0, n, 1);
vector<int> ret;
int m = query.size(a);for (int i = 0; i < m; i++) {
update(s, 0, n, 1, queryIdx[i], query[i]);
ret.push_back(tree[1].meg);
}
returnret; }};Copy the codeAlthough the topic is a simple application of line segment tree, it is still very difficult to make it in the competition. Although I thought of line segment tree, I failed to finish debugging within the time limit because I was too unfamiliar. In addition to acm players, few people can learn line tree and hand through.
After taking a look at the big guy’s problem, I found that there is another clever data structure that can be used in this problem, which I won’t go into here due to space constraints. I’ll write a separate article about it after I understand it.
Ok, that’s all for this contest. Thank you for reading.