directory
- Longest turbulence subarray
- The title
- Thinking analysis and code
- 1052. An angry bookstore owner
- The title
- Think analysis and preliminary code
- Optimize your thinking and code
- 1208. Make strings as equal as possible
- The title
- Think analysis and code
Longest turbulence subarray
The title
When A subarray A[I], A[I +1],… A[j] is called turbulent subarray when the following conditions are met:
If I <= k < j, A[k] > A[k+1] when K is odd, and A[k] < A[k+1] when k is even; Or if I <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd. That is, a subarray is turbulent if the comparison symbol flips between each pair of adjacent elements in it.
Returns the length of the maximum turbulence subarray of A.
Example 1:
Input:,4,2,10,7,8,8,1,9 [9] output: 5 explanation: (A [1] > [2] A < A [3] > [4] A < A [5])
Example 2:
Input: [4,8,12,16] output: 2
Example 3:
Input: [100] Output: 1
1 <= a. length <= 40000 0 <= A[I] <= 10^9
Thinking analysis and code
This is a typical sliding window problem. My general idea is as follows: 1. Obtain the difference array. 2. 3, if the different sign, it indicates that the condition is met; [left,right] [left,right] [left,right] [left,right] [left,right] [left,right] [left,right
If the array is less than or equal to 1, return the size of the array
class Solution {
public:
int juge(int a , int b)
{
if((a > 0 && b < 0) || (a < 0 && b >0)) return true;
else return false;
}
int maxTurbulenceSize(vector<int>& arr) {
if(arr.size() < =1) return arr.size(a);int n = arr.size(a);vector<int> diff(n - 1);
for(int i = 0; i < n - 1; i++)
{
diff[i] = arr[i+1] - arr[i];
}
int left = 0 ,right = 1;
int max_window_size = 1;
int zero_diff_times = 0;
if(diff[0] = =0) zero_diff_times++;
while(right < diff.size())
{
if(juge(diff[right],diff[right - 1]))
{
max_window_size = max(max_window_size,right - left + 1);
}
else
{
if(diff[right] == 0) zero_diff_times++;
left = right;
}
right++;
}
if(zero_diff_times == diff.size()) return 1;
return max_window_size+1; }};Copy the code1052. An angry bookstore owner
The title
Today, the bookshop owner has a shop ready for a trial opening. Customers [I] enter the store every minute, and all of them leave at the end of that minute.
At some point, bookstore owners get angry. If the bookstore owner is grumpy at the ith minute, then grumpy = 1, otherwise grumpy = 0. When the bookstore owner is angry, customers are dissatisfied for a minute. When they are not, they are satisfied.
Bookshop owners know a secret technique that can suppress their emotions and keep them from getting angry for X minutes, but they can only use it once.
Please return this day to business down, up to how many customers can be satisfied with the number. Example:
Customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1, 1,0,1,0,1], X = 3 Maximum number of satisfied customers = 1 + 1 + 1 + 7 + 5 = 16.
Tip:
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
Think analysis and preliminary code
1. Start from the first time period, traverse each time period with window length X, and calculate the number of customers who come during the time period when the boss is angry. 2. Go through the whole time period in turn and find the time when the boss is angry and the number of customers comes the most. 4. Add the two results to get the final result.
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int max_sum_start = 0;
int max_sum = 0;
for(int start = 0; start < customers.size() - X + 1; start++)
{
int sum = 0;
for(int i = start; i < start + X ; i ++)
{
if(grumpy[i] == 1) sum += customers[i];
}
if(sum >= max_sum) { max_sum = sum; max_sum_start = start; }}//cout << "max_sum= " << max_sum << endl;
int result = 0;
for(int i = 0; i < customers.size(a); i++) {if(grumpy[i] == 0) result+=customers[i];
}
returnresult+max_sum; }};Copy the codeObviously, the time is order N times X.
Optimize your thinking and code
For fixed length sliding Windows, one thing we should be familiar with is that every time the window slides, only the first and last two elements change, so we only deal with these two elements. The first window, however, needs to be filled in first. In the next window, if the new incoming time is angry, add the number of customers. If the new time out is angry, subtract the number of customers. The maximum value needs to be updated with each slide.
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int sum = 0;
// Count the number of customers who come when they are not angry
for(int i = 0; i < customers.size(a); i++) {if(grumpy[i] == 0) sum+=customers[i];
}
int left = 0, right = 0;
// The first field
while(right < X)
{
if(grumpy[right] == 1) sum += customers[right];
right++;
}
int max_sum = sum;
while(right < customers.size())
{
// Angry time has been removed from the window, reducing the total number of customers
if(grumpy[left] == 1) sum -= customers[left];
// Angry time is moved to the window, total customers increase
if(grumpy[right] == 1) sum += customers[right];
max_sum = max(max_sum,sum);
left++;
right++;
}
returnmax_sum; }};Copy the code1208. Make strings as equal as possible
The title
You are given two strings of the same length, S and T.
S in the case of a character I get to the t of the characters I need [I] – [I] t | s | overhead (overhead may be 0), which is two characters in the ASCII value of the absolute value of difference.
The maximum budget for a change string is maxCost. When converting a string, the total cost should be less than or equal to that budget, which means that the conversion of the string may be incomplete.
Return the maximum length that can be converted if you can convert a substring of S to its corresponding substring of t.
If there is no substring in S that can be converted to a corresponding substring in t, 0 is returned.
Example 1:
Input: s = ABcd, t = BCDF, cost = 3 Output: 3 Description: ABC in S can be changed to BCD. The cost is 3, so the maximum length is 3.
Example 2:
Input: s = “abcd”, t = “cdef”, cost = 3 Output: 1 Description: The cost for any character in S to be the corresponding character in T is 2. So, the maximum length is 1.
Example 3:
Input: s = “abcd”, t = “acde”, cost = 0 Output: 1 Explanation: You cannot make any changes, so the maximum length is 1.
Tip:
1 <= S. length, t.length <= 10^ 50 0 <= maxCost <= 10^6 Both s and t contain lowercase letters only.
Think analysis and code
This problem is a very typical sliding window problem. 1. First, we construct the difference absolute value array:
vector<int> diff(s.size());
for(int i = 0; i < diff.size(a); i++) { diff[i] =abs(s[i] - t[i]);
}
Copy the codeNext, we create the left and right boundaries of the sliding window and move it over the difference array. When the cost we currently have — the newly included cost on the right >= 0, we can continue to expand the window. Otherwise, if it is less than 0, it means we cannot continue to expand. But since we are looking for the maximum window length, we do not need to shrink the window at this time, just need to shift the entire window. Remember when you shift, you add the new cost that you remove to the current cost, just to make up for the loss. 5, the operation of updating the maximum length of the window must be in the time of extending the window. Of course, there is a little bit of confusion about whether the third point is >0 or >=0. If you have time, you can do it by hand, but if you don’t, try both of them and pick the right answer.
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
// Build the phase array
vector<int> diff(s.size());
for(int i = 0; i < diff.size(a); i++) { diff[i] =abs(s[i] - t[i]);
}
int left = 0, right = 0;
int max_length = 0;
while(right < diff.size())
{
// Expand the window
int new_In = diff[right];
maxCost = maxCost - new_In;
if(maxCost >= 0)
{
max_length = max(max_length,right -left + 1);
}
else
{
int new_Out = diff[left];
maxCost += new_Out;
left++;
}
right++;
}
returnmax_length; }};Copy the code