[western method takes you to learn algorithm] get the prefix and

I spent a few days selecting five topics with the same ideas from the force button to help you solve the problem. If you think the article is useful to you, remember to praise and share it. Let me see your recognition and have the motivation to continue to do it.

The first four questions are all subtypes of sliding window. We know that sliding window is suitable for continuous questions Prefix and The same is true. In continuous problems, they are of great significance to optimize the time complexity. Therefore, if you can solve a problem with violence, and the problem happens to have continuous restrictions, skills such as sliding window and prefix and should be thought of.

In addition to these questions, many questions are similar routines, which you can experience in the process of learning. Let's study together today.

Appetizer

Let's start with a simple question, identify the basic form and routine of this question, and lay the foundation for the next four questions. When you understand this routine, you can do this problem directly.

It should be noted that the pre knowledge of these four questions is a sliding window. Unfamiliar students can read what I wrote before Sliding window theme (idea + template)

Motif 0

There are N positive integers in array A. now a new array B is required. The ith number B[i] of the new array is the sum of the 0th to ith numbers of the original array a.

This problem can be solved by prefix and. 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 items of the sequence". This concept is actually easy to understand, that is, in an array, the nth bit stores the sum of the first n digits of 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 get the value of each prefix sum, so as to carry out corresponding calculation and problem solving through prefix sum. In fact, the concept of prefix and is very simple, but the difficulty is how to use prefix and in the problem and how to use the relationship between prefix and to solve the problem.

Motif 1

How can you find a continuous sub array? Where continuous refers to the continuous index of the array. For example, [1,3,4], its continuous subarray has: [1], [3], [4], [1,3], [3,4], [1,3,4], you need to return 6.

One idea is that the total number of consecutive subarrays is equal to: the number of subarrays ending with index 0 + the number of subarrays ending with index 1 ++ The number of subarrays ending with an index of n - 1 is undoubtedly complete.

At the same time, using the prefix and idea of motif 0, we can traverse and sum at the same time.

Reference code (JS):

function countSubArray(nums) {
  let ans = 0;
  let pre = 0;
  for (_ in nums) {
    pre += 1;
    ans += pre;
  }
  return ans;
}

Complexity analysis

  • Time complexity: $O(N) $, where N is the length of the array.
  • Space complexity: $O(1)$

Since the number of subarrays ending with index i is i + 1, this problem can directly use the summation formula of equal difference sequence (1 + n) * n / 2, where n is the length of the array.

Motif 2

I continue to modify the next topic. If you want to find the total number of consecutive subarrays with an adjacent difference of 1? In fact, when the index is 1, the value is 1.

Similar to the above idea, it is nothing more than the judgment of increasing the difference.

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;
}

Complexity analysis

  • Time complexity: $O(N) $, where N is the length of the array.
  • Space complexity: $O(1)$

What if my value difference is greater than 1? In fact, just change the symbol. Isn't this the number of ascending subsequences? I won't repeat it here. You can try it yourself.

Motif 3

We continue to expand.

What if I ask you to find the number of subarrays not greater than k? Not greater than k means that all elements of the subarray are not greater than k. For example, the subarray of [1,3,4] has [1], [3], [4], [1,3], [3,4], [1,3,4], and the subarray not greater than 3 has [1], [3], [1,3], so the number of subarrays not greater than 3 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;
}

Complexity analysis

  • Time complexity: $O(N) $, where N is the length of the array.
  • Space complexity: $O(1)$

Motif 4

What if I ask you to find the number of subarrays whose maximum value is just K? If the subarray [1,3,4] has the largest number of subarrays [1,3], [3,4], [3,4], then the subarray [1,4] has the largest number of subarrays [1,4], [3,4]. Implement the function exactk (k, Num).

In fact, exactK can directly use atMostK, that is, atMostK(k) - atMostK(k - 1). For the reason, see Part 5 of the motif below.

Motif 5

What if I ask you to find out that the maximum value of the subarray is just the number of subarrays between k1 and k2? Implement the function betweenK(k1, k2, nums).

In fact, betweenK can directly use atMostK, that is, atMostK(k1, nums) - atMostK(k2 - 1, nums), where K1 > K2. The premise is that the value is discrete. For example, the above questions are integers. So I can subtract 1 directly, because 1 is the smallest interval between two integers.

As described above, the area less than or equal to 10 minus the area less than 5 is the area greater than or equal to 5 and less than or equal to 10.

Note that I'm talking about less than 5, not less than or equal to 5. Since integers are discrete, the minimum interval is 1. Therefore, less than 5 is equivalent to less than or equal to 4. This is why betweenk (K1, K2, Num) = atmostk (K1) - atmostk (K2 - 1).

Therefore, it is not difficult to see that exactK is actually a special form of betweenK. When k1 == k2, betweenK is equivalent to exactK.

Therefore, atMostK is the soul method. You must master it. If you don't understand it, it's recommended to read it several times.

With the foreshadowing above, let's look at the first question.

467. The only substring in the surrounding string (medium)

Title Description

Put string s As“ abcdefghijklmnopqrstuvwxyz"Infinite surround string, so s It looks like this:"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". 

Now we have another string p . What you need is to find out s How many unique p Non empty substrings, especially when your input is a string p ,You need to output a string s in p The number of different non empty substrings. 

be careful: p It consists only of lowercase English letters, p The size of may exceed 10000.

 

Examples 1:

input: "a"
output: 1
 explain: character string S Only one of them"a"Sub character.
 

Example 2:

input: "cac"
output: 2
 explain: character string S String in“ cac"There are only two substrings“ a","c". .
 

Example 3:

input: "zab"
output: 6
 explain: In string S There are six substrings in“ z","a","b","za","ab","zab". .
 

Pre knowledge

  • sliding window

thinking

The topic is to find the number of non empty substrings of p in s, and S is a fixed infinite cyclic string. Since the data range of p is 10 ^ 5, it takes 10 ^ 10 operations to find all substrings, and it should timeout. Moreover, a lot of information about the topic is not used. It must be wrong.

Take a closer look at the title and find that this is not a variant of motif 2? Don't say much. Go directly to the code and see how much it looks like.

In order to reduce judgment, I use a black technology here, and a ^ is added in front of p.

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        p = '^' + 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

There is a problem with the above code. For example, cac will be calculated as 3, which should actually be 2. The root cause is that c is incorrectly calculated twice. Therefore, a simple idea is to use set to record the accessed substring. For example:

{
    c,
    abc,
    ab,
    abcd
}

Since the elements in the set must be continuous, the above data can also be stored in hashmap:

{
    c: 3
    d: 4
    b: 1
}

Means:

  • The maximum length of substring ending with b is 1, that is, b.
  • The maximum length of a substring ending in c is 3, which is abc.
  • The maximum length of substrings ending with d is 4, that is, abcd.

As for c, there is no need to save it. We can work it out in the way of motif 2.

Specific algorithm:

  • Define a len_mapper. Key is the letter and value is the length. It means the length of the longest continuous substring ending with key.

Keywords: longest

  • Use a variable w to record the length of continuous substrings, and the traversal process updates len according to the value of W_ mapper
  • Return len_ Sum of all value s in mapper.

For example: abc, len at this time_ Mapper is:

{
    c: 3
    b: 2
    a: 1
}

Another example: abcab, len at this time_ Mapper remains the same.

Another example: abcazabc, len at this time_ mapper:

{
    c: 4
    b: 3
    a: 2
    z: 1
}

This is the purpose of de duplication. This algorithm does not repeat or leak, because the longest continuous substring must contain shorter continuous substrings 1297. Maximum occurrences of substring The method of pruning is similar.

Code (Python)

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        p = '^' + 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())

Complexity analysis

  • Time complexity: $O(N) $, where $N $is the length of string p.
  • Space complexity: since a maximum of 26 letters are stored, the space is actually constant, so the space complexity is $O(1) $.

795. Number of interval subarrays (medium)

Title Description

Give an array whose elements are positive integers A ,positive integer L  as well as  R (L <= R). 

Find continuous, non empty, and the maximum element is greater than or equal to L  Less than or equal to R Number of subarrays.

for example :
input:
A = [2, 1, 4, 3]
L = 2
R = 3
 output: 3
 explain: Subarray satisfying conditions: [2], [2, 1], [3].
be careful:

L, R  and  A[i] All integers, range  [0, 10^9]. 
array  A  The length range of is[1, 50000]. 

Pre knowledge

  • sliding window

thinking

From motif 5, we know that betweenK can directly use atMostK, that is, atMostK(k1) - atMostK(k2 - 1), where K1 > K2.

From motif 2, we know how to find the number of subarrays that meet certain conditions (here, the elements are less than or equal to R).

These two can be solved by combining them.

Code (Python)

Is the code very 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)

Complexity analysis

  • Time complexity: $O(N) $, where $N $is the length of the array.
  • Space complexity: $O(1) $.

904. Fruit basket (medium)

Title Description

In a row of trees, the second i Tree generation tree[i] Type of fruit.
You can start with any tree you choose and repeat the following steps:

Put the fruit from this tree in your basket. If you can't, stop.
Move to the next tree to the right of the current tree. If there is no tree on the right, stop.
Please note that after selecting a tree, you have no choice: you must perform step 1, then perform step 2, then return to step 1, then perform step 2, and so on until you stop.

You have two baskets. Each basket 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 with 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 with the first tree, we will only be able to collect [0, 1]. 
Example 3:

Input:[1,2,3,2,2]
Output: 4
 Explanation: we can collect [2,3,2,2]
If we start with the first tree, we will only be able to 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 be able to collect four fruit trees.
 

Tips:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Pre knowledge

  • sliding window

thinking

The title is gaudy. Let's abstract it, that is to give you an array and let you select a sub array. This sub array has only two numbers at most. What is the maximum number of the selected sub array.

Isn't this the same as motif 3? It's just that k becomes a fixed value of 2. In addition, since the title requires at most two numbers in the whole window, can't we just save it with a hash table?

I can't. Therefore, we need to know not only how many numbers are in the window, but also how many times each number appears, so that we can use the sliding window to optimize the time complexity.

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)

Complexity analysis

  • Time complexity: $O(N) $, where $N $is the length of the array.
  • Space complexity: $O(k) $.

992. Subarray of K different integers (difficult)

Title Description

Given an array of positive integers A,If A The number of different integers in a subarray of is exactly K,Then called A This continuous and not necessarily independent subarray of is a good subarray.

(For example,[1,2,3,1,2] Zhongyou 3 Two different integers: 1, 2, and 3. )

return A Number of good subarrays in.

 

Example 1:

Input: A = [1,2,1,2,3], K = 2
 Output: 7
 Explanation: a subarray of exactly 2 different integers:[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
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,4].
 

Tips:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length


Pre knowledge

  • sliding window

thinking

From the motif 5, we know: exactK = atMostK(k) - atMostK(k - 1), so the answer is ready to come out. Other parts and the above topic 904 Fruit is like a basket.

In fact, it is similar to all sliding window problems.

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

Complexity analysis

  • Time complexity: $O(N) $, where $N $is the length of the array.
  • Space complexity: $O(k) $.

1109. Flight reservation Statistics (medium)

Title Description

here you are  n  There are flights from 1 to n Number.

We have a flight reservation form here  i  Reservation records  bookings[i] = [i, j, k]  It means we're starting from  i  reach  j  We have reservations on every flight k Seats.

Please return a length of n Array of  answer,Return the number of reserved seats on each flight in the order of flight number.



Example:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
 Output:[10,55,45,25,25]



Tips:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

Pre knowledge

  • Prefix and

thinking

The description of this problem is not very clear. Let me briefly analyze the topic:

[i, j, k] actually stands for K people coming up at station i. they are on the plane until station J, and they are not on the plane until station j + 1. Therefore, there will be more than k people at each station from station i to station J.

Understanding the topic will only make it easy 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

The above code complexity is too high to pass all test cases.

Note that the while loop in the inner layer is a continuous array, all of which are added with a number. It is not difficult to think that it can be optimized by using the prefix and idea of motif 0.

One idea is to add k to the position of i, and then use the prefix and technique to add k to the elements from i to n. But the question needs to add an interval. J + 1 and its subsequent elements will be added with an additional k. A simple trick is to subtract k from the element of j + 1 so that the positive and negative can be offset.

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]

Complexity analysis

  • Time complexity: $O(N) $, where $N $is the length of the array.
  • Space complexity: $O(N) $.

summary

These questions are the idea of sliding window and prefix sum. There are a lot of similar problems. If you pay more attention, you will find this routine.

The skills of prefix and and and sliding window are relatively fixed, and there are templates to set. The difficulty is how can I think of using this technique?

Here I summarize two points:

  1. Keyword not found. For example, if there is continuity in the title, you should think of sliding window and prefix and conditional reflection. For example, when the problem is to maximize and minimize, we think of dynamic programming and greed, and so on. After thinking about it, you can compare it with the topic information, quickly eliminate the error algorithm and find the feasible solution. This thinking time will decrease as your sense of problem increases.
  2. First write the violent solution, and 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.

Finally, I recommend several similar topics for you to practice. You must write them yourself.

If you have any opinions on this, please leave me a message. I will check and answer one by one when I have time.

For more algorithm routines, please visit my LeetCode problem solving warehouse: https://github.com/azl3979858... . It's already 36K star.

You can also follow my official account Li Kou Jia Jia to take you to the hard bone of algorithm.

Tags: Python Algorithm data structure leetcode

Posted by caspert_ghost on Sat, 14 May 2022 09:02:30 +0300