I have brushed about 600 questions and summed up more than 200 questions. In addition, I have summarized more than ten common algorithm topics, basically covering most common test points and question types. All on my dead simple HTTP: / / https://github.com/azl397985856/leetcode.
However, as a novice, looking at the vast number of problems and materials will inevitably fall into a “do not know where to start” situation. “Don’t worry, you’re not alone.”
In fact, RECENTLY I have been thinking about “how beginners can improve their algorithm ability quickly and efficiently”. Therefore, I have been constantly positioning myself, and finally I made a positioning for myself “restore the whole process of problem solving with clear and straightforward language, and do the best algorithm problem solving in The West Lake area”.
I realized, however, that I had made a big mistake. My idea has always been to “help algorithm xiaobai improve algorithm ability and brush questions efficiently”. However, in addition to clear and straightforward algorithm problem solving, but also need system knowledge. So my assumption that everyone knows the basic data structures and algorithms probably doesn’t hold.
Little white phase division
If I were allowed to make a stage division for algorithm white, I would divide it into:
Stage one systematically learns data structure and algorithm knowledge.
First, you can’t just not know the basics, like not knowing a hash table at all, or just the simple API.
Second, you can’t constantly search for knowledge from the Internet, because it’s fragmented and doesn’t help newbies form their own “algorithmic view.”
Once you’ve successfully crossed the above two hurdles, congratulations, you can move on to the next level.
For this stage, want to cross. Need to systematically learn some basic knowledge, recommend to chew “algorithm 4” or directly chew the teaching material inside each university. If it is really difficult, you can first read “Algorithm Diagram”, “my first algorithm book” this kind of door, and then go to chew.
Stage two: brush the questions.
For example, according to the buckle of the label to brush. Therefore, the above learning stage does not necessarily mean that you have to learn all the basics before brushing, but learning a topic can be targeted to brush. For example, if I learn dichotomy, I can find a dichotomy problem to brush.
If you want to overcome this hurdle, in addition to doing more problems, there is another is to read more problems, write more problems. Of course, it depends on good solutions, which I’ll talk about later.
If you make it past these two hurdles, congratulations, you are no longer an algorithmic nerd (at least for non-algorithmic geeks).
My view of algorithms
Back to the question “My positioning error”. Because many young people did not go beyond stage 1, my so-called “restore the whole process of problem solving with clear and straightforward language, and do the best algorithm problem solving in The West Lake area” did not help them in essence. What they desperately needed was something that “systematically codified the ideas and routines of algorithms.” So I’m going to do 91, and that’s for the rest of the story.
Notice that I mentioned an “algorithmic view” above. I don’t know if it actually exists, but it doesn’t matter. If it doesn’t exist, I give it meaning. If it does, I redefine it.
Algorithmic view refers to your overall understanding of algorithms. For example, I was given a topic, how to examine the topic, how to abstract it into an algorithm model, and how to select the appropriate data structure and algorithm according to the model. This requires an understanding of the characteristics and usage scenarios of various data structures and algorithms.
Let me give you an example, this example is today (2020-06-12) my 91 group of daily questions.
API example:
class LRUCache:
def __init__(self, capacity: int):
def get(self, key: int) -> int: def put(self, key: int, value: int) -> None: # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value) Copy the codeFollowing the procedure above, let’s “trap” one.
- How the topic
After reading the problem, just grab a core point. In this case, the core point is “delete the longest unused”, “O(1) time”.
- Abstract algorithm model
This question is a design question. The API is designed for us, and all we need is the padding function, which means we don’t need to abstract the algorithm model.
- Select appropriate data structures and algorithms according to the model
Our algorithm has two operations: “get” and “put”. To support both of these operations, there must be a place to store the data. So where do we store it? An array? The list? Hash table? There are a lot of linked lists, one-way and two-way, cycle not cycle.
Because in the process of examining the first step, we obtained the key information of “O(1) time”. So:
- Array cannot be updated, deleted
- Linked lists cannot be found, updated, or deleted.
❝
Some people say list update, delete is
, so HOW do you find the nodes to delete? Worst-case scenario if we run it through and find it
❞
- The hash table is unordered and therefore cannot be “deleted most unused”.
It seems impossible to use any one of the three alone. So let’s consider combining multiple data structures.
I just said linked lists so delete and update are both
Specifically, I want to remove the node with the value 3 in the graph, and I need to move it once. Because I had to start from scratch to find it.
Or IF I want to update the 7 node in the graph, I have to move it twice.
(figure 2)
Is there any way to eliminate the time loss of this traversal? In fact, our fundamental purpose is to “find the target node”, and the most violent way to find the target node is “traversal”. Is there a more subtle way? No doubt this would not have been possible without the help of extra space. Our only idea is “space for time”.
Suppose you have a data structure, and you tell it what you want to look up, and it helps you find
Whereas the space complexity up here is zero
So, if we need to do something before 1, we’re going to iterate from the beginning, and if we need to do something after 1, we’re going to iterate from 1. The worst case time complexity can be reduced to
If you could go through the process above for each question, with some additions, I’m sure you’d be terrifyingly efficient.
Do you think that much about each problem?
Beginners are strongly advised to follow the logic above to think, do problems, and write a summary of the solution. As the number of problems increases, the quantity changes and the quality changes, you will find that the above steps can be “a matter of seconds”. If you’re good at diagrams, or if you often look at other people’s diagrams (like mine), then diagrams can help you retrieve information in your brain faster, in less time.
❝
A diagram is a hash table for the brain to retrieve information, right? Haha, Maybe.
❞
The water is very deep
I read a lot of people’s questions directly in two sentences, and then follow the code:
class Solution:
def integerBreak(self, n: int) -> int:
dp = [1] * (n + 1)
for i in range(3, n + 1):
for j in range(1, i):
dp[i] = max(j * dp[i - j], j * (i - j), dp[i])
return dp[n]
Copy the codeThis is, frankly, only for people who “go to the problem section and see if there’s a new and better solution.” But most of the people who look at it are the kind of people who don’t know how to do it. So this is not going to be useful.
In my opinion, good problem solving should be novice friendly, and can fully show the problem solver’s thinking. For example, when I see this topic, what comes to my mind first (it doesn’t matter whether it’s right or wrong), and then how do I screen the algorithm to a specific one or several. How did I come up with my final algorithm, any prior knowledge.
Of course, I also admit that many of my problems are straightforward answers, which are of little use to many people, and may even be counterproductive, giving them the illusion that they already know what to do. In fact, they don’t understand the original thinking of the problem solver. Maybe the person who wrote the problem solver thought it was “natural”, or maybe it was “just for show”.
Brush question order
Finally give xiaobai a brush question order, to help you maximize the use of their time.
Basics (30 days)
Foundation is always the most important, first the most basic of these familiar, do not miscut wood.
- Arrays, queues, stacks
- The list
- Tree and recursion
- Hash table
- Double pointer
Thoughts (30 days)
These ideas are highly return-on-investment and it is highly recommended that each small topic take some time to master.
- binary
- The sliding window
- Search (BFS, DFS, backtracking)
- Dynamic programming
Improvement (31 days)
These benefits are less obvious and often require a certain amount of skill accumulation. The frequency of occurrence is relatively low. But there are problems that require you to use these techniques. Or you can use these techniques to achieve a dimension reduction strike.
- greedy
- Divide and conquer
- An operation
- KMP & RK
- Check and set
- The prefix tree
- Line segment tree
- The heap
The last
I am currently writing a book on problem solving myself including the recently organized Algorithm 91, which is targeted at “Stage 1 to Stage 2”. In order to really help people grow up, I plan to spend three months making a systematic summary of data structures and algorithms to help people get over stage ONE. Of course, I will update the problem solving constantly, and I will take you through stage two in a clear and straightforward way.