I came from a small white all the way, also brush in Leetcode for several years, also have some experience, also walked through a lot of pits, here to share a wave of my experience, please be patient to read it will certainly help.

Do not brush the problem blindly: brush the knowledge accumulation before the problem

To tell the truth, want to improve their algorithm, I think is down-to-earth more hands to brush, brush more questions.

However, if you are a little white, that is, you have not learned common data structures such as lists and trees, and common algorithm ideas such as recursion, enumeration, and dynamic programming, then I do not recommend that you blindly brush up. But first to find a book to learn the necessary knowledge, and then to brush the problem. Because, if these basic all do not understand, estimate a question to do a few hours, then see the answer all do not understand, do not have any train of thought, this is very uncomfortable. As time goes by, I estimate no motivation, I just started like this, a question answer to see a day, but still do not understand, what backtracking ah, violence ah, do not know what is meant.

That said, if you want to go to a site like Leetcode, then you need to have a certain foundation, which includes:

1, common data structure: linked list, tree (such as binary tree). (Yes, linked lists and binary trees are important, so we can leave the graphs for now.)

2, common algorithm ideas: greedy method, divide and conquer, exhaustive method, dynamic programming, backtracking. (Greed, exhaustion, divide and conquer is the foundation, dynamic programming is difficult, can be put on hold)

The above list is the most basic. That means before you brush, you have to go over these and brush again. If you even do not know these most basic words, then you brush the process, will be very uncomfortable, the train of thought will be relatively less.

In short, do not be urgent, first these basic over, and strive to understand, and then brush the problem. I learned these basic data structures and algorithms in the second semester of my freshman year. I didn’t watch videos. I learned them through reading books.

1. Data Structure and Algorithm Analysis (C Language Description Version)

I believe most people read the book written by Yan Weimin from Tsinghua University Press as a course in college. To be honest, as a beginner, I couldn’t stick to that book. It may be more suitable for big guys to read. I bought a book of data structure and algorithm analysis (c language version) “, is quite thin, but it felt great, the book let me learned a lot, the individual feels also pretty easy to understand, code implementation is implemented using c language, not a pseudo code, if you want to learn the structure of the data, I think this book is a good choice. A lot of people in the class have seen Data Structures, which they say is pretty good, but I haven’t seen it.

2. Challenge the programming competition

This book is also a freshman read, if you want to brush the problem, I recommend this book, which is divided into elementary, intermediate to advanced. Although each question did not speak in particular detail, but at that time all understand, really good. But I didn’t see the advanced part. The beginner and intermediate were comfortable. Also learned a lot, recommended to everyone.

The beauty of programming

It is highly recommended

4. Programming gems

5, programmer code interview guide: IT famous enterprise algorithm and data structure problem optimal solution

Do a supplement: these books I have saved the electronic version, but Baidu Cloud sent out often link failure, I am not good to update, but you can follow my public number: helpless pain code farmers, reply ** “e-book” ** can get. My public account also has more than 100 original articles, many of which are to explain the algorithm, and you are also very welcome to follow and learn together.

To tell you the truth, I spent almost all of that semester on data structures and algorithms, but I brush up on very few problems, just some examples from books. So when I go through these basic, and then go to some websites brush questions is still very dish.

So you must not expect to think that after learning these ideas brushing questions will be very cattle, only more brushing questions, only more hands-on practice, your sensitivity will improve.

Summary:

There is no shortcut to improving the data structure and algorithm. The best shortcut is to brush more questions. However, you need to learn some basic data structures and algorithmic ideas before you can brush them.

AC is not the goal. We want perfection

How to brush? How do you treat an algorithm problem?

I think, when doing the problem, we must pursue perfection, do not put a problem to work out, submit through, and then hurry to the next one. I don’t think it makes a lot of sense, because there are too many ways to solve a problem, and some of the ways are rough, and we should be looking for the best way.

There is a correlation between algorithmic performance and the number of problems, but it’s not linear. That is to say, when doing the problem, to strive for more than one solution, if they really can not come up with other ways, you can go to see how others do, do not feel that imitation of others is a shame.

When I’m doing a problem, when I see a problem, maybe my first thought is to do it in a very crude way, because a lot of problems are easy to do with brute force, but the time complexity is very high. After that, I will slowly think about other ways to reduce the time complexity or the space complexity. And then finally, I’m going to look at what other people are doing, and of course, it’s not going to work out that way for every problem.

The quality of an algorithm is measured by the complexity of time and complexity of space, so we want to strive for perfection, we need to minimize these two, so that they complement each other.

Let me give you an example:

Problem: A frog can jump up one or two steps at a time. How many ways can the frog jump up an N step?

I have analyzed this problem in the previous chapter, if you do not understand, you can first read the previous article: Recursion and dynamic Programming – Basic Article 1

Method 1: : Violent recursion

This question is not difficult. Maybe you will do the following:

public static int solve(int n){
    if(n == 1 || n == 2){
        return n;
    }else if(n <= 0){
        return 0;
    }else{
        returnsolve(n-1) + solve(n-2); }}Copy the code

The time complexity of doing this is exponential. But if you submit it and you get away with it, and then you move on to the next problem, you need to think about it.

Method two: space for time

Strive for perfection, we can consider using space for time: this question how you think carefully, you will find that there are a lot of repeated implementation. So here’s what you can do:

Static Map<Integer,Integer> Map = new HashMap(); public static int solve(int n){if(n <= 0)return 0;
    else if(n <= 2){
        return n;
    }else{// Whether to calculateif(map.containsKey(n)){
            return map.get(n);
        }else{
            int m = solve(n-1) + solve(n-2);
            map.put(n, m);
            returnm; }}}Copy the code

In this way, time can be greatly shortened. In other words, when you do a problem, and you find that the time complexity is high, you can think about whether there’s a better way, whether you can trade space for time.

Method three: Fibonacci series

In fact, we can reduce the space complexity by not requiring a HashMap to store state:

public static int solve(int n){
    if(n <= 0)
       return 0;
    if(n <= 2){
        return n;
    }
    
    int f1 = 0;
    int f2 = 1;
    int sum = 0;
    for(int i = 1; i<= n; i++){
        sum = f1 + f2;
        f1 = f2;
        f2 = sum;
    }
    return sum;
}
Copy the code

I show you this problem, not to teach you how to do this problem, but to do the following:

1, in the brush, we should strive to perfect.

I can’t think of these methods, how to do? So you can look at what other people have done, and then, when you come across a similar problem, you’ll be more thoughtful, you’ll know which way to go.

3. You can start with a problem from simple violence, consider the measurement between space and time, and optimize little by little.

Challenge yourself to get out of your comfort zone

What is a comfort zone? When brushing a problem, may have a kind of problem is you understand more, you have thought every time a look, and then half an hour on the code, submit the code, and then passed, and then, wow, and more brushing a problem, the in the mind is very comfortable.

However, remember that you can do more of these exercises in the early stages to improve your enjoyment, but I recommend that you slowly get out of your comfort zone, do something you’re not good at, and keep doing this for a while. For example, I think I’m pretty good at recursion problems, but I’m pretty good at dynamic programming problems, because I have to think about it for a long time, and I’m a little afraid of it, and I don’t have much confidence. However, there was a period of time when I felt that I only brush the dynamic programming problem, directly selected the topic in Leetcode, and did seventy or eighty consecutive times. It was very uncomfortable at the beginning, but later I gradually knew the routine. A problem was reduced from two or three hours to half an hour, and it was completed in a simple ten minutes. I feel that I am not afraid of this type of problem.

So, I suggest you learn to get out of your comfort zone.

Recommend some brush the website

I generally brush in Leetcode and ox guest net, feel very good, the difficulty of the topic is not very big.

In the cow passenger net there, I mainly brush sword refers to the Offer, but there is also an online brush Leetcode, but the number of questions is less. Cow guest net brush questions have a very convenient place is a discussion area, where there will be a lot of big guys to share their solutions, we do not have to go to Baidu to find solutions. So when you’re done, you really can’t think of a convenient way to go and see how other people do it.

As for Leetcode, most of the questions are given the official answer, is also a good brush problem website. You can choose one or both.

Of course, there are other brush the website, however, other websites did not brush, not clear how.

As for Leetcode, there is a Chinese version and an English version. I suggest the English version. There are various solution analyses of the big guys in the English version.

Leetcode is available in Chinese

The English version

Choose according to your interests.

Learn some problem solving skills

To be honest, there are some problems that you don’t know are so beautiful and elegant until you look at other people’s solutions, and then, oh, my god, this is still possible. And in the process of brushing, we will continue to accumulate these skills, when you accumulate more, you will form a nerve response, suddenly think of a method. There are many techniques, such as array subscripts, bitmaps, double Pointers, and so on, and I’ve shared an article summarizing some of them myself. To give you an example, sometimes there are techniques that really make you say, “Oh my God.”

1. Find numbers that do not repeat

You are given a set of integer numbers, in which one number appears only once, and the other numbers appear twice, and you are asked to find one number.

This is probably a problem that a lot of people would use a hash table to store it, and each time you store it, you record the number of times a certain number appears, and then you go through the hash table again to see which number appears only once. This method is O(n) in time, and O(n) in space.

However, I would like to tell you that using bit operations to do it, absolutely high!

We just said that the xor result of two identical numbers is 0, and the xor result of a number and 0 is itself, so let’s xor the whole set of integers, for example, this set of data is 1, 2, 3, 4, 5, 1, 2, 3, 4. Five of them appear only once, and the others appear twice. All of them are different or different, and the results are as follows:

Since Xor supports commutative and associative laws, it follows that:

1 ^ 2 ^ 3 ^ ^ 4 5 ^ 1 ^ 2 ^ 3 ^ 4 = ^ ^ 1 (1) (2 ^ 2) ^ ^ (3 ^ 3) (4 ^ 4) 5 = 0 ^ ^ ^ ^ ^ 0 0 0 5 = 5.

In other words, the number that appears twice after xor becomes 0, and the number that appears once after xor is equal to itself. Is this a good solution? So the code looks like this

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1; i < arr.length; i++){ tmp = tmp ^ arr[i]; }return tmp;
}
Copy the code

It’s O(n) in time, O(1) in space, and it looks pretty awesome.

2. M to the n

If you were asked to solve for 2 to the n, and you couldn’t use the system’s own POW function, what would you do? This is not easy, just multiply n m’s in succession, the code is as follows:

int pow(int n){
    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * m;
    }
    return tmp;
}
Copy the code

But if you do this, I can only ha ha, the time complexity is O(n), even elementary school students can! If you had to do it with bit operations, how would you do it?

For example, if n = 13, the binary representation of n is 1101, then m to the 13th power can be disassembled as:

M ^1101 = m^0001 * m^0100 * m^1000.

We can read 1101 bit by bit by &1 and >>1, and multiply the multiplier represented by this bit to the final result when it is 1. Just look at the code, it’s easier to understand:

int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n ! = 0) {if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    
    return sum;
}
Copy the code

It’s almost order logn in time, and it looks pretty awesome.

More algorithmic skills, welcome everyone to pay attention to my headline number, will certainly let you gain drop.

And the importance of data structures

I’ve been talking about how I usually learn algorithms. In the data structure method, I just listed that you must learn linked lists and trees (binary heap), but this is the most basic, before brushing the problem to master, for data structure, I listed some of the more important:

1, linked list (such as unidirectional linked list, two-way linked list).

2. Trees (such as binary trees, balanced trees, red-black trees).

3, graph (such as shortest path algorithms).

4, queue, stack, matrix.

For these, oneself must begin to achieve again. You can read a book, you can watch a video, you can watch the video for beginners, but you can watch the video first, and then my recommendation is to read the book.

For balanced tree, for example, you may follow the book code implementation, after a while you will forget, but it does not matter, though you forgot, but if you use code before, understand, so when you see again, will remember soon, soon know train of thought, and your ability to abstract and so on will be in imperceptible in ascension. And then we learn about red-black trees, all kinds of data structures, very quickly.

The single most important

Go do it, go do it, go do it. Say the important words three times.

Do not find a pile of resources, set a good study plan, I want to stay to so-and-so day to do…..

Don’t do this, but when your passion comes, do it immediately, don’t leave it for a holiday ah what the hell, many people who think this way, will end up doing nothing.

Don’t feel like you have a lot to learn and don’t know where to start. As I said above, you can learn the most basic, and then brush the problem, brush the problem is a need to adhere to the long-term things, one year, two years. In the process of brushing, you can intersperse and learn other data structures.

Have a harvest? Hope the old iron to a triple strike, to more people see this article

1, give me a thumbs up, can let more people see this article, by the way to inspire me, hee hee.

2, old iron people, pay attention to my original wechat public number “handsome play programming **”, focus on writing algorithm + basic knowledge of computer (computer network + operating system + database +Linux). Save it so you can see something after, don’t believe you hit me.

Finally, let’s take a look at github, where you can download hundreds of popular ebooks. Here are some screenshots

The address is here:Click to go to Github