I spent a few days, from the strength of the buckle selected five topics with the same idea, to help you solve the set, if you think the article useful, remember to like to share, let me see your recognition, motivated to continue to do.
- 467. A unique substring in the surround string (medium)
- 795. Number of interval subarrays (medium)
- 904. Fruit baskets (medium)
- 992. subarrays of K distinct integers (difficulty)
- 1109. Flight Booking Statistics (Medium)
The first four problems are all subtypes of sliding Windows, and we know that sliding Windows work well in cases where the problem requires continuity, as do prefixes and sums. They are very important for optimizing time complexity in continuous problems. So if there is a problem you can solve by brute force, and the problem happens to have continuous limits, then techniques like sliding Windows and prefixes and sums should be considered.
In addition to these questions, there are many questions are similar routines, you can experience in the learning process. Today we are going to learn together.
Before the dishes
Let’s start with a simple question and identify the basic form and pattern of this kind of question to lay the foundation for the next four questions. When you understand the routine, then you can do this kind of problem directly.
It should be noted that the pre-knowledge of these four questions are all sliding Windows. If you are not familiar with them, you can take a look at the sliding window topic I wrote before.
Motif 0
We have N positive integers in array A, and now we need A new array B, whose ith digit B[I] is the sum from the 0th to the ith digit of array A.
This problem can be solved using prefixes and sums. Prefix sum is an important preprocessing, which can greatly reduce the time complexity of query. We can simply understand it as “the sum of the first n terms of a sequence”. The idea is that the NTH bit of an array stores the sum of the first n numbers in the array.
For [1,2,3,4,5,6], the prefix sum can be pre=[1,3,6,10,15,21]. We can use the formula pre[𝑖]=pre[𝑖−1]+nums[𝑖] to obtain the value of each prefix sum, so as to calculate and solve the problem through the prefix. In fact, the concept of prefix and sum is very simple, but the difficulty is how to use prefix and sum and how to use the relationship between prefix and sum to solve the problem.
Motif 1
If you were asked to find the total number of consecutive subarrays of an array, what would you do? Where continuous refers to the array index contiguity. [1 4], for example, the continuous subarray are: [1], [3], [4], [1, 3], [3, 4], [4] 1, you need to return to 6.
One way to think about it is that the total number of contiguous subarrays is equal to: the number of subarrays ending at index 0 + the number of subarrays ending at index 1 +… + Number of subarrays ending in index n-1, which is unquestionably complete.
Using the prefix of motif 0 and the idea of traversing and summing.
Reference code (JS) :
function countSubArray(nums) {
let ans = 0;
let pre = 0;
for (_ in nums) {
pre += 1;
ans += pre;
}
return ans;
}
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where N is the array length.
- Space complexity: O(1)O(1)O(1)
Since the number of subarrays ending in index I is I + 1, this problem can directly use the arithmetic sequence summation formula (1 + n) * n / 2, where n array length.
Motif 2
I’m going to change it a little bit, but what if I asked you to find the total number of consecutive subarrays with 1 difference between each other? If the index is 1 off, the value is 1 off.
Similar to the above idea, is nothing more than to increase the difference of judgment.
Reference code (JS) :
function countSubArray(nums) {
let ans = 1;
let pre = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] - nums[i - 1] = =1) {
pre += 1;
} else {
pre = 0;
}
ans += pre;
}
return ans;
}
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where N is the array length.
- Space complexity: O(1)O(1)O(1)
What if my difference only has to be greater than 1? In fact, just change the sign, isn’t that the number of ascending subsequences? I’m not going to repeat it here, but you can try it out for yourself.
Motif 3
We continue to expand.
What if I asked you to find the number of subarrays that are not greater than k? No greater than k means that none of the elements in the subarray are greater than k. Such as [1 4] subarray [1], [3], [4], [1, 3], [3, 4], [4] 1, no more than 3 subarray [1], [3], [1, 3], then [1 4] not greater than 3 subarray number is 3. Implement the function atMostK(k, nums).
Reference code (JS) :
function countSubArray(k, nums) {
let ans = 0;
let pre = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= k) {
pre += 1;
} else {
pre = 0;
}
ans += pre;
}
return ans;
}
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where N is the array length.
- Space complexity: O(1)O(1)O(1)
Motif 4
What if I asked you to find the number of subarrays whose maximum value is exactly k? For example, if the [1,3,4] subarray has [1], [3], [4], [1,3], [3,4], and the subarray whose maximum value is 3 has [3], [1,3], then the number of subarrays whose maximum value is 3 is 2. Function exactK(K, NUMS).
In fact exactK can utilize atMostK directly, i.e. AtMostK (k) -Atmostk (K-1), for reasons described in motif 5 below.
Motif 5
What if I asked you to find the number of subarrays whose maximum value is between k1 and k2? Implement the function betweenK(k1, k2, nums).
It betweenK between atMostK(k1, nums) – atMostK(k2-1, nums), where k1 > k2. If the values are discrete, like the ones I did above are integers. So I can just subtract 1, because 1 is the smallest interval between two integers.
So the region less than or equal to 10 minus the region less than or equal to 5 is the region greater than or equal to 5 and less than or equal to 10.
Notice I said less than 5, not less than or equal to 5. Since integers are discrete, the minimum interval is 1. So less than 5 here is the same thing as less than or equal to 4. It’s betweenK(k1, k2, nums) = atMostK(k1) -Atmostk (k2-1).
ExactK, therefore, is the special form of betweenK. BetweenK betweenK is equivalent to exactK when k1 == k2.
Therefore atMostK is the soul method, be sure to master, do not understand the advice to read more than once.
So with that in mind, let’s do the first problem.
467. A unique substring in the surround string (medium)
Topic describes
String s is considered an "abcdefghijklmnopqrstuvwxyz" infinite surrounding the string, so it s look like this: "... zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." .Now we have another string p. What you need is to find out how many unique non-empty substrings of P there are in S, and in particular if your input is the string P, you need to output the number of different non-empty substrings of P in the string S. Note: p consists only of lowercase English letters and may be larger than 10000. Example 1: Input: "A" Output: 1 Description: There is only one "A" subcharacter in the string S. Example 2: Input: "cac" Output: 2 Description: The string "cac" in string S has only two substrings "A" and "C". Example 3: Input: "zab" Output: 6 Description: There are six substrings "Z", "A", "B", "za ", "ab", and "zab" in string S. .Copy the codeFront knowledge
- The sliding window
Train of thought
They say let’s find the number of non-empty substrings in which P occurs in S, where S is a fixed infinite loop string. Since the data range of P is 10^5, it would take 10^10 operations to find all the substrings by force, which should time out. And they didn’t use a lot of information, so it’s definitely not right.
If you look closely, isn’t this a variation of motif 2? Without further ado, just go to the code and see how it looks.
To reduce the judgment, I’m using a hack here, where I put a ^ in front of the p.
class Solution:
def findSubstringInWraproundString(self, p: str) - >int:
p = A '^' + p
w = 1
ans = 0
for i in range(1.len(p)):
if ord(p[i])-ord(p[i-1= =])1 or ord(p[i])-ord(p[i-1= = -])25:
w += 1
else:
w = 1
ans += w
return ans
Copy the codeThere is a problem with the above code. Cac, for example, is going to be calculated as 3, when it should actually be 2. The root cause is that c has been miscalculated twice. So a simple idea is to use a set to record the substrings accessed. Such as:
{
c,
abc,
ab,
abcd
}
Copy the codeSince the elements in a set must be contiguous, the above data can also be stored in a hashmap:
{
c: 3
d: 4
b: 1
}
Copy the codeThe meaning is:
- A substring ending in b has a maximum length of 1, which is b.
- A substring ending in C has a maximum length of 3, which is ABC.
- A substring ending in D has a maximum length of 4, that is, abcd.
As for C, there is no need to save it. And we can figure that out using motif 2.
Specific algorithm:
- Define a LEN_mapper. Key is a letter and value is a length. Meaning the length of the longest continuous substring ending in key.
The key word is: longest
- A variable w records the length of a continuous substring, and the traversal updates len_mapper based on the value of W
- Returns the sum of all values in len_mapper.
For example, ABC, len_mapper is:
{
c: 3
b: 2
a: 1
}
Copy the codeAnother example is abCAB, where len_mapper remains the same.
For example: abcazabc len_mapper:
{
c: 4
b: 3
a: 2
z: 1
}
Copy the codeThis is the purpose of weight removal. This algorithm is not leaky, because the longest continuous substring must contain a continuous substring shorter than it, the idea and 1297. The method of pruning the maximum number of substring occurrences is similar.
Code (Python)
class Solution:
def findSubstringInWraproundString(self, p: str) - >int:
p = A '^' + p
len_mapper = collections.defaultdict(lambda: 0)
w = 1
for i in range(1.len(p)):
if ord(p[i])-ord(p[i-1= =])1 or ord(p[i])-ord(p[i-1= = -])25:
w += 1
else:
w = 1
len_mapper[p[i]] = max(len_mapper[p[i]], w)
return sum(len_mapper.values())
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where NNN is the length of the string P.
- Space complexity: Because it stores a maximum of 26 letters, the space is actually a constant, so the space complexity is O(1)O(1)O(1).
795. Number of interval subarrays (medium)
Topic describes
Given an array A whose elements are all positive integers, positive integers L and R (L <= R). Find the number of contiguous, non-empty subarrays whose largest element is greater than or equal to L and less than or equal to R. For example: input: A = [2, 1, 4, 3] L = 2 R = 3 output: 3: meet the conditions of subarray: [2], [2, 1], [3]. Note: L, R, and A[I] are integers in the range [0, 10^9]. Array A has A length range of [1, 50000].Copy the codeFront knowledge
- The sliding window
Train of thought
BetweenK it betweenK (k1) – atMostK(k2-1), between k1 and k2.
From motif 2, we know how to find the number of subarrays that satisfy certain conditions (in this case, elements less than or equal to R).
Put those two together and you can solve it.
Code (Python)
Is the code similar
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) - >int:
def notGreater(R) :
ans = cnt = 0
for a in A:
if a <= R: cnt += 1
else: cnt = 0
ans += cnt
return ans
return notGreater(R) - notGreater(L - 1)
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where NNN is the length of the array.
- Space complexity: O(1)O(1)O(1).
904. Fruit baskets (medium)
Topic describes
In a row of trees, the ith tree produces fruit of the tree[I] type. You can start with any tree you choose and repeat the steps below: Put the fruit from this tree into your basket. If you can't do that, stop. Moves to the next tree to the right of the current tree. If there are no trees on the right, stop. Notice that after selecting a tree, you don't have any choice: you have to do step 1, then step 2, then go back to Step 1, then step 2, and so on until you stop. You have two baskets, each of which can carry any amount of fruit, but you want each basket to carry only one type of fruit. What is the maximum amount of fruit trees you can collect using this program? Example 1: Input: [1,2,1] Output: 3 Explanation: We can collect [1,2,1]. Example 2: Input: [0,1,2,2] Output: 3 Explanation: We can collect [1,2,2] If we start from the first tree, we will only collect [0,1]. Example 3: Input: [1,2,3,2,2] Output: 4 Explanation: We can collect [2,3,2,2] If we start from the first tree, we will only collect [1,2]. Example 4: input: [3,3,3,1,2,1,1,2,3,3,4] output: 5 explanation: we can collect [1,2,1,1,2] if we start with the first tree or the eighth tree, we will only collect 4 fruit trees. 1 <= tree. Length <= 40000 0 <= tree[I] < tree. LengthCopy the codeFront knowledge
- The sliding window
Train of thought
The title is fancy. Let’s abstract it a little bit, so you’re given an array, and you’re told to pick a subarray, and that subarray has at most two numbers, and that subarray can be as large as it can be.
Isn’t it the same as motif 3? But k becomes a fixed value of 2. In addition, since they require a maximum of two numbers in the entire window, we can use a hash table to save it, right?
Set is not working. So not only do we need to know how many numbers are in the window, we also need to know how many times each number appears so that we can optimize the time complexity using sliding Windows.
Code (Python)
class Solution:
def totalFruit(self, tree: List[int]) - >int:
def atMostK(k, nums) :
i = ans = 0
win = defaultdict(lambda: 0)
for j in range(len(nums)):
if win[nums[j]] == 0: k -= 1
win[nums[j]] += 1
while k < 0:
win[nums[i]] -= 1
if win[nums[i]] == 0: k += 1
i += 1
ans = max(ans, j - i + 1)
return ans
return atMostK(2, tree)
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where NNN is the length of the array.
- Space complexity: O(k)O(k)O(k).
992. subarrays of K distinct integers (difficulty)
Topic describes
Given an array of positive integers A, if the number of different integers in A subarray of A is exactly K, the contiguous, not necessarily independent subarray of A is called A good subarray. (for example, there are three different integers in [1,2,3,1,2] : 1,2, and 3.) Returns the number of good subarrays of A. Example 1: input: A =,2,1,2,3 [1], K = 2 output: 7: just made up of two different integer subarray: [1, 2], [2, 1], [1, 2], [2, 3], [1, 2, 1], [2,1,2],,2,1,2 [1]. Example 2: input: A = [1,2,1,3,4], K = 3 output: 3 explanation: A subarray of exactly three different integers: [1,2,1,3], [2,1,3], [1,3]. 1 <= a. length <= 20000 1 <= A[I] <= A.length 1 <= K <= A. LengthCopy the codeFront knowledge
- The sliding window
Train of thought
ExactK = atMostK(k) -Atmostk (K-1) The other parts are the same as the above title 904. Fruit baskets.
In fact, it’s the same as any sliding window problem.
Code (Python)
class Solution:
def subarraysWithKDistinct(self, A, K) :
return self.atMostK(A, K) - self.atMostK(A, K - 1)
def atMostK(self, A, K) :
counter = collections.Counter()
res = i = 0
for j in range(len(A)):
if counter[A[j]] == 0:
K -= 1
counter[A[j]] += 1
while K < 0:
counter[A[i]] -= 1
if counter[A[i]] == 0:
K += 1
i += 1
res += j - i + 1
return res
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where NNN is the array length.
- Space complexity: O(k)O(k)O(k).
1109. Flight Booking Statistics (Medium)
Topic describes
There are n flights, and they're numbered from 1 to n. What we have here is a flight booking table with the I booking record [I] = [I, j, k] meaning we booked k seats for each flight from I to J. Return the number of seats booked on each flight in order of flight number. Example: the input: bookings = [,2,10 [1], [2,3,20], [2,5,25]], n = 5 output:,55,45,25,25 [10] tip: 1 <= bookings.length <= 20000 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000 1 <= bookings[i][2] <= 10000Copy the codeFront knowledge
- The prefix and
Train of thought
The description of the problem is not very clear. Let me briefly analyze the topic:
[I, j, k] actually means that there are k people on the plane at station I, all the way up to station J, and then no longer on the plane at station J + 1. So every station from I to J is going to have k more people.
Understanding the problem will only make it easier to write the following code.
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) - >List[int] :
counter = [0] * n
for i, j, k in bookings:
while i <= j:
counter[i - 1] += k
i += 1
return counter
Copy the codeThe code above is too complex to pass all the test cases.
Notice that the inner while loop is a continuous array with a single number added to it, and it’s not hard to think of ways to optimize using the prefix of the 0 motif.
One way to think about it is to add k to I, and then use the prefix sum trick to add k to everything from I to n. But what they want to add is an interval, where j plus 1 and everything after that gets added by another k. A simple trick is to subtract k from the j + 1 element so that the pluses and minuses cancel out.
Code (Python)
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) - >List[int] :
counter = [0] * (n + 1)
for i, j, k in bookings:
counter[i - 1] += k
if j < n: counter[j] -= k
for i in range(n + 1):
counter[i] += counter[i - 1]
return counter[:-1]
Copy the codeComplexity analysis
- Time complexity: O(N)O(N)O(N), where NNN is the array length.
- Space complexity: O(N)O(N)O(N).
conclusion
These problems are sliding Windows and prefix sum ideas. Buckle similar topics are really many, we only pay more attention to, will find this routine.
Both the prefix and sliding window techniques are fixed and have templates to set. The challenge is how do I think I can use this technique?
Here I summarize two points:
- Look for keywords. For example, if you have continuous, you should automatically think of sliding Windows and prefix sums. For example, dynamic programming and greed come to mind when solving problems of maximum and minimum. Once you think of that, you can compare it with the information in the problem and quickly troubleshoot the error algorithm and find the feasible solution. This thinking time will decrease as your sense of the problem increases.
- Write the violent solution first, then find the bottleneck of the violent solution, according to the bottleneck, it is easy to know what data structure and algorithm should be used to optimize.
Recommend a few similar topic finally, practice for everybody, must write oneself just go.
- 303. Fields and retrieval – Arrays are immutable
- Delete once to get the maximum sum of subarrays
- 1310. Subarray xor query
- 1371. Each vowel contains the largest string of even order
If you have any opinion on this, please leave a message to me. I will check the answer one by one when I have time.
More algorithms can be found in my LeetCode repository: github.com/azl39798585… . Currently it has 36K star.
You can also pay attention to my public account “Li Kou Jia Jia” take you to bite the hard bone of the algorithm.