The addresses of the first two are here, and those of you who haven’t read them are advised to read them first.

  • Let’s talk about how I did it.
  • Let’s talk about how I did it. (Second snap)

This may be the final chapter in the series. This time I’m going to talk about a little bit of hardcore, some super practical ideas that you can use in almost any algorithm.

In the last section, we posed two questions:

  • How to lock which algorithm to use? For example, if I see this problem, how do I know which solution to use? Binary? Dynamic programming?
  • A look will be, a written waste, how to overcome?

Today, I will round a original blow under the cow force. No more talking. Get straight to the business. If you think it is useful, please support me once, so that I can stick to it and bring more dry goods to everyone.

How to lock which algorithm to use?

Why do a lot of people know how to solve the problem just by looking at it?

  • One possibility is that he or she has done the same or similar problems before, forming an internal memory and directly extracting the previous memory.
  • Another possibility is that the questions give clear hints, and they “deceive” based on the information, which is the sense of the question.
  • The last one is to try brute force solutions at the beginning, find some steps that can be optimized, and then slowly peel away the cocoon and derive the final answer.

Next, let’s talk about the second and the third. As for the first one, it can not be solved by an article, which requires us to do more questions, and when doing questions, we should summarize and communicate more.

The keyword

Keywords can play a prompt role in solving problems. This is very easy to understand, assuming that the topic does not restrict information and other keywords, it is playing rogue, no algorithm at all. For example, “Find target in an array”, this problem is boring, normally do not have this algorithm. The possible form of the problem is to add the word ordered to make an ordered array. So order is the key word.

There are many other examples, but let’s take a look at common keywords and what their possible solutions are.

  • If the topic is extremum, counting, it’s probably dynamic programming, heap, etc.

  • If the topic is ordered, it may be two-pointer. Like dichotomy.

  • If the problem requires continuity, it might be a sliding window.

  • If they’re asking for all possibilities and they need path information, it might be backtracking.

These are just the first possible solutions you should think of when you see the keywords, and whether they are correct or not, and whether they are up to the complexity level requires a second processing in your head.

As to whether the complexity is up to par, I’ll tell you later.

Limiting conditions

A lot of questions will give you some indication of the range of data, so be sure to pay attention. For example, 1681. Minimum incompatibility, so I’m going to skip the description, and we’re not going to go into the exact solution here. The function signature for this problem is as follows:

def minimumIncompatibility(self, nums: List[int], k: int) - >int:
Copy the code

Here’s the tip:

1 <= k <= nums.length <= 16 Nums. length is divisible by k. 1 <= nums[i] <= nums.lengthCopy the code

What do you think of this?

Note that the length and value of nums are small, and this problem is most likely violence backtracking + state compression. Check out my history article on backtracking and state compression techniques.

Here’s another super useful tip for you.

  • If n is 10 or so, then the algorithm is usually n! The time complexity of.
  • If n is around 20, then the algorithm is usually 2 to the n time

1681. Minimum incompatibility is probably exponential in complexity.

So why is 10 or so n factorial? , 20 is 2 ^ n? Here’s a trick you might not know. I want you to remember a number 10 million.

The reason it’s around 10 or 20 is because you bring in n and it’s almost always 10 million. Or if n is 10710^7107, that’s probably O(n)O(n)O(n), because 10710^7107 is 10 million.

For example, in my previous article “I don’t know you when I put on clothes? Let’s talk about the longest ascending subsequence”, all of the above questions are N2N^2N2 in time complexity, which can pass almost all test cases. Why is that? Because they have a range of 2500, so what’s 2500 squared? It’s more than 6 million, so the range is up to 3000, and the square is pretty much solvable, but I’m only talking about most cases, and you have to be aware that the closer you get to the threshold, the more likely you’re going to time out.

Or 1631. Minimum physical exertion path. Title description:

You're going on a hike. Rows x columns heights[row][col] specifies the height of a row. You start with the upper-left cell (0, 0) and you want to go to the lower-right cell (rows-1, soxes-1) (note that the subscripts start numbered at 0). You can go up, down, left or right at a time, and you want to find the path that takes the least effort. The energy cost of a path is determined by the maximum absolute value of the height difference between adjacent grids on the path. Return the minimum energy expended from the top left corner to the bottom right corner.Copy the code

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5] output: 2 description: the absolute value difference of continuous grid of path [1,3,5,3,5] is at most 2. This path is better than path [1,2,2,2,5] because the other path has a maximum difference of 3.Copy the code

The function signature for this problem is as follows:

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) - >int:
Copy the code

Here’s the tip:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6
Copy the code

First, we need to go at least from the top left to the bottom right, so the time complexity is already O(Rows ∗columns)O(Rows * columns)O(Rows ∗columns). And they tell us that neither of these numbers is greater than 100, so the maximum is 10410 to the 4104. The data range for absolute height difference on the route does not exceed 10610^6106.

The brute force method is one trial at a time, and it’s just a direct multiplication of the two, which is 101010 to the 101010, which is greater than 10710 to the 7107, so it’s usually not AC.

O(Rows * columns)O(Rows * columns) is impossible because you need to go at least once. But what if 10610^6106 is not linear, but exponential? In exponential complexity, the first thing to think about is binary.

Pseudocode for this problem:

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) - >int:
        def test(mid, x, y) :
            # dosomething
        l, r = 0.10**6
        # leftmost binary template of values that satisfy the condition. You can go to leetcode-Cheatsheet for more algorithm templates
        while l <= r:
            mid = (l + r) // 2
            # test if there is a path from (0,0) to (rows-1,cols-1), and the absolute value difference between the paths is not greater than mid
            if test(mid, 0.0):
                r = mid - 1
            else:
                l = mid + 1
        return l
Copy the code

Do you think 10 million is an important number? 10 million is not only my life goal, but also a number to keep in mind all the time! ^_^

Optimization of violence

Finally, the technique for identifying possible solutions to a problem is violence optimization.

The short answer is brute force, then think about the performance bottleneck, and then try to optimize the bottleneck using data structures and algorithms.

For example, 316. Removing repeated letters, I just brute force it out first. It takes too long to determine whether O(N)O(N)O(N) is needed on the stack. Because I’m using hash tables to optimize. And the idea of using a hash table was definitely not what I had in mind at the beginning, but I had to solve it by force, and then I realized I had to use a hash table when I found performance bottlenecks in the algorithm. I’m not going to tell you how to solve this problem in detail, but you can just click on it and look at my problem. Or go to force buckle to search a problem directly, the unofficial solution of the first rank problem should be me.

To sum up, we must not underestimate violence. Brute force solution pruning is probably too much. If not, think about where the bottleneck is and optimize it with appropriate data structures and algorithms. This is not a casual remark. For example, the following coin change problem is a violent solution to find the bottleneck, adding a memorization to remove the repetition subproblem is dynamic programming

A look will be, a written waste, how to overcome?

To solve this problem, the advice I gave you before is to review more, write more.

Then I talked to some friends and realized I was a little bit of a survivor bias. I find that a lot of people start learning algorithms without algorithmic thinking, which is not desirable.

But algorithmic thinking is something you asked me to spell out for you in this article, which is not realistic. Today I’m going to share with you an algorithm idea that I think is the most important — divide and conquer.

Partition thinking

“It’s easy to read, but easy to write. How to overcome it?” One possibility is that you don’t think divide-and-conquer. Our brains are designed to process simple things, not seemingly complex ones. So when you have a complex thing, the first thing you should do is think about whether you can break it down and break it down one by one.

The number of occurrences of 2 is as follows: the number of occurrences of 2 is as follows:

Write a method that counts the number 2 occurrences from 0 to n inclusive. Example: Input: 25 Output: 9 Explanation: (2, 12, 20, 21, 22, 23, 24, 25)(note that 22 should count as two) Hint: n <= 10^9Copy the code

A lot of people get confused when they see this problem. How many cases does it take? You can’t just try it out one number at a time, can you?

In fact, if you look at the data range where n is up to 10 to the ninth, more than 10 million, you know you can’t do that.

So quietly open the solution, not only sigh “so ah!” “, “How did you come up with that? What a brain!”

Let me tell you what you don’t have. What you lack is not a good brain, but the awareness and ability to turn complex problems into several simple ones.

In this case, I can break it down into subproblems.

  • The number of occurrences of the digit 2 from 0 to n inclusive
  • The number of occurrences of the tens digit 2 from 0 to n inclusive
  • .

The final answer is the sum of these subquestions.

After such a train of thought, we can open up the train of thought. The rest of the task is easy. Because every time you fix a digit, you divide the number into left and right parts, so the number of times the digit is 2 is the cartesian product of all the possible left and right parts, which is a times b.

Let’s say n is 135.

You can’t have a 2 in the hundreds place, because 2xx must be more than 135.

How many 2’s do we have in the tens place? Follow the idea above:

  • On the left-hand side, we have the hundreds place, and the hundreds place could be 0 or 1, either way.
  • The ones place on the right-hand side, the ones place could be 0 minus 9 in 10 different ways.

So the number of times the tens place is 2 is 2 times 10 is 20.

How many twos do we have in that place? Follow the idea above:

  • On the left, we have the tens place and the hundreds place, which could be [0-13], 14 possibilities.
  • There’s nothing on the right-hand side. 1 possibility.

So there are 14 times that the ones place is 2.

So the number of occurrences of 2 up to 135 is 20 + 14 = 34.

Of course, there are some details, like what happens if one of the digits is less than 2 or exactly 2? I won’t talk about it here. I’ll just post the code here, and you can go ahead and do it yourself.

class Solution:
    def numberOf2sInRange(self, n: int) - >int:
        ans = 0
        m = 1
        while m <= n:
            cur = n // m % 10
            if cur > 2: ans += (n // m // 10 + 1) * m
            else:
                if cur == 2: ans += n % m + 1
                ans += (n // m // 10) * m
            m *= 10
        return ans
Copy the code

Replace 2 with some other number x, and you can count the number of occurrences of x up to n.

Here’s an example of why you don’t have a clue about some topics:

  • Or you haven’t seen this kind of problem before, so you can’t do it.
  • Or you’re not algorithmic enough. Like the divide-and-conquer algorithm I talked about above.

A look will show that this kind of question you are answered, so a look will, a written waste, generally do not develop good algorithm thinking, and divide and conquer is a very important algorithm thinking. Once algorithmic thinking is in place, the rest of the details can be practiced slowly. There are no shortcuts. But there are shortcuts to algorithmic thinking, we should pay special attention to the learning of algorithmic thinking before we brush the questions.

Let me give you a couple more examples to help you understand.

Three questions will take you through the idea of divide and conquer

  1. Find the element in an array nums with the value target and return the array subscript. The problem guarantees that there is one and only one nums number equal to target.
  2. Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1. You can think of an infinite number of each coin. (322. Small change)
  3. The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other. (51. N)

These questions cover three types of difficulty: easy medium and hard. Now, let’s look at these problems.

The first question

For the first problem, the answer is nothing more than 0, n-1. Therefore, we can divide the problem into the following sub-problems:

  • Is zero? no
  • Is 1? no
  • Is 2? no
  • .

The final answer is the index that answered “yes” to the subquestion. Technically, there is only division, no rule, and this division is subtly different from the previous division. The front of the points after the back to use, this point is directly thrown away. Similarly, there is dichotomy, which is a kind of “divide and conquer” with only divide and no rule.

The second question

Coins is a variable, and amount is a variable. How do they feel about each other? How am I supposed to figure it out?

We start with specialities, such as Coins = [1, 2, 5] and amount = 11. For the convenience of description, I used f([1,2,5], 11) to represent coins as [1,2,5], and the minimum number of coins needed for amount 11.

I don’t know what the final minimum number of coins was. So WHY don’t I just go through all the scenarios, compare which one uses the least amount of coins?

The final algorithm is really based on this simple idea.

When you pick the first coin, there are only three choices: choose 1, choose 2, and choose 5.

  • If we pick 1 first, then we just have to make 10. So how do we get 10? F ([1, 2, 5], 10).
  • If we pick 2 first, then we just have to make 9. So how do we get nine? F ([1, 2, 5], 9).
  • If we pick 5 first, then we just have to pick 6. So how do we get six? F ([1, 2, 5], 6)?

This is the case where we picked a coin, and since we didn’t get to the amount, we keep repeating until we do.

So you can draw something like this logical tree structure, but I didn’t draw it all because there were so many nodes.

Ever find that your brain has no idea what to do with a big problem when it’s much easier to break it down into smaller ones? When we’re done dividing, we still have to rule.

It’s like you’re the supervisor, and you assign the assignment, and then you take the assignment and you put it together and you make a powerpoint or something.

But it’s not hard. And since the problem is the least number of coins, I’m going to take the least number of coins.

1 + min(f([1.2.5].10),f([1.2.5].9),f([1.2.5].6))
Copy the code

To sum up:

We can start with a few special cases of this problem to open our minds. The above means are described in pseudocode:

for (int coin : coins) {
    f(coins, amount - coin)
}
Copy the code

And when we do that, we’re dealing with the boundaries and the rules.

The complete divide-and-conquer code is:

public int f(coins, amount) {
    if (amount < 0) {
        // Illegal solution, represented by positive infinity
        return Float.POSITIVE_INFINITY
    }
    // Leaf node
    if (amount == 0) {
        // Find a solution that is not the smallest "cure" phase processing.
        return 0
    }
    int ans = Float.POSITIVE_INFINITY
    for (int coin : coins) {
        ans = Math.min(ans, 1 + f(coins, amount - coins))
    }
    return ans
}

Copy the code

In order to highlight the main framework of my algorithm, I have omitted some details. So if I had no solution, I would have returned -1, and I would have returned plus infinity.

Those of you who have done this before know that this is a typical backpack problem. If I had to do it now, I would probably also solve the bottom-up DP table directly (although dp table and mnemonic recursion have no essential mental difference). But how did the algorithm come up with this point, how to step by step optimization, we must drill to the end, so that the efficiency of the brush problem is high.

The third question

If you don’t understand the meaning of the topic, you can go to the original topic 51.n Queen. This is a typical backtracking problem. What is backtracking? In short, it is one try at a time, failing to go back to the previous step to try again.

Where do I put all these boxes? Each grid also has constraint relations! What a mess. I have no idea.

Don’t worry. Keep thinking divide-and-conquer. So this problem is asking us to put N queens on an N X N board. Isn’t that:

  • What column should the queen be in in the first row?
  • In what column should the queen of the second row be placed?
  • In what column should the queen of the third row be placed?
  • .

Change to “What row should the queen of column X be in?” This sub-problem partitioning model is also possible.

Pseudo code:

public int placeRow(i) {
    // Decide which column to place in
}

for (int i=0; i<n; i++) { placeRow(i) }Copy the code

If the subproblems above are solved, then the whole problem is solved, right?

But the subproblem above, still can’t be solved directly. For example, “What column should the queen in the first row be in?” I don’t know. That’s okay, let’s move on to the question “What column should the queen of the first row be in?” Let’s break this down.

  • Does the queen in the first row go to the first column?
  • Does the queen in the first row go to column 2?
  • Is the queen in the first row in the third column?
  • .

Continue with the placeRow code above. Here is the pseudocode:

public  boolean canPlaceQueue(i, j) {
    // According to the current chess game (whether can not attack each other), analyze the position I and J can put the queen.
}
public int placeRow(i) {
    for (int j=0; j<n; j++) {if (canPlaceQueue(i, j)) {
            // Put the queen in (I,j) to update the current game
            placeQueue(i, j)
        }
    }
}
Copy the code

The only problem now is to implement canPlaceQueue(I, j) and placeQueue(I, j).

Note that we do placeQueue(I, j), which is probably a mutable operation. So if a path doesn’t work and needs to be backtracked, mutable data needs to be unmodified. Of course, it doesn’t matter if your data is immutable. Immutable, however, risks memory removal or timeouts.

Since this is only about thinking, not about the topic itself, so or point to the end, I will not talk about the details of the algorithm behind, I hope readers can improve their own code.

More and more

There are too many similar examples to mention, so I’ll just give you a few.

  • 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. The number of consecutive subarrays is equal to: number of subarrays ending at index 0 + number of subarrays ending at index 1 +… + Number of subarrays ending with index n-1

  • 70. Climbing stairs makes you wonder how many ways to get to the last step. There are too many for me to count. But I can break it down into two subproblems. If I use f(n) as the number of ways to get to the NTH level, then F (n) = f(n-1) + f(n-2). But I can’t do n minus 1 either. That’s okay. Let’s keep breaking it down. Is this much different from the coin problem above? For this problem, partition is just splitting into two subproblems, and the solution is just summing.

This is the simplest recursive dynamic programming with no choice

  • 746. Climb the stairs at minimal cost and get a skin change again?

  • 220 Games of the week – Jump Game VI is not up stairs to change skin? This time it was k steps.

This one is 10510 to the 5105, and if you don’t optimize it, it’s going to be N2N^2N2, so it’s going to be 101010 to the 101010 and it’s not going to be over 10 million. How to optimize it is a bit off topic, so I won’t go into it here.

  • 62. You can’t tell if you’re climbing stairs by wearing two-dimensional clothes on different paths?

There are too many related skin change topics, we can go to my plug-in to see.

conclusion

Now, I’m going to share with you a very important algorithm idea that you can use in a lot of problems. The topics that can use the idea of divide and conquer are “dynamic programming”, “divide and conquer”, “backtracking” and so on. You can refer to my way of thinking when doing problems at ordinary times.

If you are faced with a complex problem, try the following methods.

  • Try disassembling it first and see if you can break it down into a few small problems.
  • Draw on a sketch, start with a particular situation, see if you can find any clues
  • Violence simulation. See if you can optimize the algorithm by pruning and adding the right data structure.

If you have better dry goods skills, I hope you can communicate with me, looking forward to it!

In addition to the algorithmic ideas, I also share with you two super useful techniques:

  • Look at the keywords. A lot of times the keyword plays the role of cue, whether it is right or not, we have to think of. Do a quick mental check to see if you can AC.
  • Look at the constraints. Just remember one number. 10 million.

Finally, I told you a careful – “do not look down on violence”. Not only will brute force help you open your mind, but sometimes brute force plus pruning (or data structure optimization) goes too far. Work miracles, Oh yeah! (^o^)/

Love triple punch

1. Please click here to support me. Your reading is the motivation for my creation.

2. Pay attention to the public account force buckle plus, take you to bite the hard bone of the algorithm! Add a star, don’t miss every opportunity to grow.

3. If you find this article helpful, please forward it for me.