preface

A lot of things have happened recently, and recently the front end sharing meeting has come as scheduled. Fortunately, this sharing meeting is available on the weekend, so let’s make a summary.

This time I want to share the algorithm and data structure, brush for a period of time, stroll around LeetCode, read a lot of articles about this aspect, have some insights, ready to make a record.

When you want to spend time to understand and learn something that is very difficult for you, we need to make clear the goal, learn what it means, what it does, what it can help you in.

It’s a must for growth. Yeah, pay rise, pay rise, pay rise.

So the question comes, why should enter big factory ⬇️

The goal of going to Dafang when you are young is to avoid [you have to have an Epiphany, which is the basic skill of others]

Well, that’s where the small talk ends. Let’s get started

Standing on the shoulders of giants, it is very easy to learn, here I am reference online algorithm brush route, can refer to ~

Public number front-end UpUp, reply algorithm, you can get the brain map, and the title summary PDF at the end of the article.

Let’s take a look at this brain map

The data structure

Data structure can be said to be the foundation of the algorithm, without a solid foundation of data structure, it is very difficult to learn the algorithm well, even through, and good algorithm often depends on which data structure you use. It is also necessary to learn this topic well, so we can do a little classification.

  • Common data structures

    • Array, string
    • The list
    • The stack
    • The queue
    • The tree

  • High-level data structure

    • figure
    • The prefix tree
    • Line segment tree
    • Tree array
    • Chairman of the tree

So obviously, the most common data structures have to be mastered, and for the more advanced data structures, if you have the time, if you have the love of it, you can get into it, like this chair tree, which is a log algorithm for solving some problems, which is helpful in some scenarios.

I want to mention trees here. The structure is obvious and intuitive. Trees have a lot of properties, and I can’t list them all. For example, trees are often tested in interviews:

Common binary Tree, balanced binary Tree, complete binary Tree, binary search Tree, Quadtree, n-ary Tree.

How far do we need to go with it?

For common tree traversal, from the tree preorder traversal, to the middle order traversal, subsequent traversal, and even hierarchical traversal, it is very important to master the recursive and non-recursive writing of these four kinds of traversal, and then you need to understand the time and space complexity of the various writing methods.

Taking the time to prepare for an interview is a great way to understand recursion. It can also help you learn a little bit about graph theory. More specifically, trees are popular for interview interviews, especially binary trees!

Mastering these data structures is the foundation for most algorithmic interview questions, so be sure to practice the questions to understand them deeply.

Sorting algorithm

This should be the most frequently tested, the most central algorithm for interviews. If you understand the sorting algorithm very well, then the rest of the algorithms will do the same thing.

At that time, I combed through the common 6 sorting algorithms:

  • Bubble sort
  • Count sorting
  • Quick sort
  • Merge sort
  • Insertion sort
  • Selection sort

Before this, I also wrote a sorting algorithm article, personally think concise and comprehensive, can see “algorithm and data structure” comb 6 sorting algorithm

Sometimes, interviewers like to ask about bubble sort and insert sort, basically to check your basics and see if you can write bug-free code quickly.

For example, when the interviewer asks you to merge sort, quicksort, topological sort, etc., this time is to investigate your usual accumulation of algorithms, so it is necessary to do a summary.

Let’s take merge sort for example, how do we make this clear? First, we should make this clear:

The core idea of merge sort is divide and conquer, which is to divide a complex problem into two or more identical or similar subproblems, and then divide the subproblems into smaller subproblems, until the subproblems can be easily solved directly, and the solution of the original problem is the combination of the subproblems. Merge sort embodies the idea of divide and conquer.

When you clear this idea with the interviewer, he or she will know and think, hey, this is a great guy! Then you have the rest of it!

Once you have the idea, it’s not hard to achieve:

We start by dividing the array in the middle into two subarrays, and then we recursively divide the subarray into smaller subarrays, until there’s only one element in the subarray, and then we sort.

The way to sort is to merge two elements in size order, and then successively merge the sorted subarrays in recursive return order, until the entire array is sorted.

Post a copy of the previous code:

const merge = (left, right) = > { // Merge the array

    let result = []
    // Use the shift() method to delete the first element and return the value
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    while (left.length) {
        result.push(left.shift())
    }

    while (right.length) {
        result.push(right.shift())
    }
    return result
}

let mergeSort = function (arr) {
    if (arr.length <= 1)
        return arr
    let mid = Math.floor(arr.length / 2)
    // Split the array
    let left = arr.slice(0, mid),
        right = arr.slice(mid);
    let mergeLeftArray = mergeSort(left),
        mergeRightArray = mergeSort(right)
    return merge(mergeLeftArray, mergeRightArray)
}

// let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
// console.log(mergeSort(arr))
Copy the code

For this part of the algorithm, can be around the idea from the problem ->> implementation process ->> code implementation. Basically with these three steps to achieve, grasp the common sorting algorithm to complete is no problem.

So I’m going to stop there for the moment.

Dynamic programming

Dynamic programming is difficult. It can be said that many interviewees are also the part I am most afraid of, especially in the interview, I am afraid that the interviewers will test this algorithm. For problems we haven’t done before, it’s very important to be able to write the state transition equation. Let’s talk about this topic next.

First of all, I strongly recommend before analyzing how to prepare this topic: “Algorithms and Data Structures” a brain map that shows you the beauty of dynamic programming algorithms

If you look at it from the like point of view, it’s probably the most you’ve ever been sure of since I wrote the algorithm, so you can look at it, but I’ll cover some of it here.

How to learn dynamic programming, where to start, how to do it this way, how to brush up on the problem, is certainly a problem that many beginners will encounter at the beginning.

  • concept
  • What problem does dynamic programming solve
  • Dynamic programming problem solving steps
  • How to brush dp topic efficiently

First, you have to understand what dynamic programming is, what the idea is, and what the definition is. Here’s how Wikipedia defines it:

It is both a mathematical optimization method and a programming method.

First of all, it can be regarded as a means of optimizing the operation of some repeated subproblems, and many overlapping subproblems can be solved programmatically, such as memory stroke search. For example, if an original problem can be broken down into many subproblems, and there is no follow-up between them, and the current decision has no effect on the follow-up, then the optimal solution of each subproblem can be combined into the optimal solution of the original problem.

Of course, everyone understands dynamic programming differently, and when applied to specific scenarios, we need to express its meaning in terms of multidimensional states, which is what the state transition equation means.

Well, what problem does dynamic programming solve? Well, obviously, for repetitive problems, it solves very well, so in one dimension, it optimizes the time complexity of an algorithm, in the general sense, trading space for time.

Dynamic programming problem solving steps: this should be the actual operation of landing, we need to go through a large number of problems to complete, specific we need to do?

Solution idea, three steps 👇

  1. State definition
  2. List the state transition equation
  3. Initialization state

“Algorithms and Data structures.” A brain map that shows you the beauty of dynamic programming algorithms.

How high efficiency brush DP topic: first of all, you have to find the corresponding DP topic, here, I help you ready, next I say how I brush leetcode above the topic.

In general, brush the medium LEetcode on the DP topic, basically can meet the requirements. So for medium DP problems, most of the time, I write not to eat, then how should I do?

  • First of all, I look at the answer key, write down its state transfer equation, carefully taste, its definition, so resolved before I what difficulties, why I didn’t think of.
  • Then, after reading it, try to solve the problem according to the idea, can I achieve it alone?
  • If not, just follow the code, write it again, see more of how the state transition equation is written, bookmark this topic.
  • Wait until the next time, or the next day, look at the problem again, and see if you can do it alone, and if you can’t, do it the next day.

Still have, my personal suggestion, brush DP, had better from easy to difficult, this way oneself also can have confidence, also won’t go to fear it.

Summary of advanced questions

Here are some of the topics I collected. I hope they will be helpful to you.

simple

  • Climb the stairs
  • Al shabaab
  • Use minimal cost to climb stairs
  • Continuous sequence
  • Three problems

medium

  • Robbery II
  • The best time to buy and sell stocks includes the cold period
  • Robbery III
  • Different paths
  • Different Paths II
  • Longest ascending subsequence

difficult

  • The best time to buy and sell stocks III
  • The best time to buy and sell stocks
  • The frog crossing the river
  • Word Split II
  • Maximum submatrix

Search algorithm

It is also particularly important to focus on the depth first search algorithm (DFS) and the breadth first search algorithm (BFS).

I was looking through my blog and I happen to have a post on a similar issue that you can check out ** “Algorithms and Data Structures” The beauty of DFS and BFS algorithms **.

However, I have a look, when I wrote it, it was a little rough, a lot of basic concepts were not clear, so it may be suitable for some people who have a basic understanding of this part of the friends.

Here’s an interesting title:

Minimum number of moves through the maze

If you labyrinth also encountered similar problems, can consider to search algorithm, from my personal point of view, its way of thinking is simulating the thinking of people, each time you come to a crossroads, where I can go, before I walked through the road, how to ensure that the next can’t walk, there needs to be in programming point of view, how to achieve?

Here is my experience. For the problem I just mentioned, I used BFS for blind guessing. If I have done many problems, I will naturally learn from them.

Give some advice:

At the beginning, I may not be able to grasp my mind and have ideas, but the code is difficult to write clearly, so how to do it? Look at the solution, understand others writing is very good, can be more than a comparison, to see which solution code is you can understand at present, and then copy down, look at it again.

The most common way to do this is to draw a picture to see what changes need to be made mentally to the actual code and how to optimize the process. Finally, combined with other people’s code, must not directly copy, do not think why write so, or later found, is not much effect, must be more combined with their own understanding.

Well, won’t just look at the problem, think more why write so!!

By the time I write here, it is already 1 o ‘clock in the morning. The direction of algorithm and data structure is too big to finish an article. I hope this article can be of a little help to you, to me, or to you, so that its existence has a little meaning.

The following is the problem SET I brush, the needs of their own, the public number: front-end UpUp, pay attention to it, find me to get PDF documents can also.

Summary of advanced questions

This topic wants to advance, brush the topic that I provide below 👇

DFS

  • The maximum depth of a binary tree
  • The minimum depth of a binary tree
  • Circle of friends
  • Find the ultimate safe state
  • The longest increasing path in the matrix
  • minesweeper
  • randomly

BFS

  • Sequence traversal of n-fork tree
  • Binary tree sequence traversal
  • Minimum height tree
  • minesweeper

Topic summary

I brush the course before is according to this set of questions, I think inside the problem gradient or quality are very good.

Get this PDF for some time, so do not know who the specific author is, if there is infringement, can be deleted.

Array & linked list

simple

  • Leetcode-cn.com/problems/re…

  • Leetcode-cn.com/problems/ro…

  • Leetcode-cn.com/problems/me…

  • Leetcode-cn.com/problems/me…

medium

  • Leetcode-cn.com/problems/sw…

  • Leetcode-cn.com/problems/3s…

Map & Set

simple

  • Leetcode-cn.com/problems/va…

medium

  • Leetcode-cn.com/problems/gr…

Stack & queue

simple

  • Leetcode-cn.com/problems/re…

  • Leetcode-cn.com/problems/re…

medium

  • Leetcode.com/problems/la…

  • Leetcode.com/problems/tr…

Binary search

simple

  • Leetcode-cn.com/problems/ar…

medium

  • Leetcode-cn.com/problems/po…

difficult

  • Leetcode-cn.com/problems/du…

recursive

simple

  • Leetcode-cn.com/problems/ma…

  • Leetcode-cn.com/problems/sy…

  • Leetcode-cn.com/problems/mi…

  • Leetcode-cn.com/problems/mi…

  • Leetcode-cn.com/problems/bi…

  • Leetcode-cn.com/problems/ra…

medium

  • Leetcode-cn.com/problems/lo…

Hash table

simple

  • Leetcode-cn.com/problems/tw…

  • Leetcode-cn.com/problems/va…

medium

  • Leetcode-cn.com/problems/lo…

  • Leetcode-cn.com/problems/to…

difficult

  • Leetcode-cn.com/problems/nu…

Binary tree

simple

  • Leetcode-cn.com/problems/mi…

  • Leetcode-cn.com/problems/lo…

medium

  • Leetcode-cn.com/problems/sy…

  • Leetcode-cn.com/problems/bi…

  • Leetcode-cn.com/problems/bi…

difficult

  • Leetcode-cn.com/problems/se…

Binary search tree

simple

  • Leetcode-cn.com/problems/mi…

  • Leetcode-cn.com/problems/lo…

medium

  • Leetcode-cn.com/problems/va…

  • Leetcode-cn.com/problems/ra…

  • Leetcode-cn.com/problems/co…

difficult

  • Leetcode-cn.com/problems/co…

figure

medium

  • Leetcode.com/problems/nu…

  • Leetcode-cn.com/problems/co…

Heap and sorting

simple

  • Leetcode-cn.com/problems/kt…

difficult

  • Leetcode-cn.com/problems/fi…

DFS

simple

  • Leetcode-cn.com/problems/ma…

  • Leetcode-cn.com/problems/mi…

medium

  • Leetcode-cn.com/problems/fr…

  • Leetcode-cn.com/problems/fi…

difficult

  • Leetcode-cn.com/problems/lo…

  • Leetcode-cn.com/problems/mi…

  • Leetcode-cn.com/problems/wo…

BFS

simple

  • Leetcode-cn.com/problems/n-…

  • Leetcode-cn.com/problems/bi…

  • Leetcode.com/problems/bi…

medium

  • Leetcode.com/problems/bi…

  • Leetcode-cn.com/problems/mi…

  • Leetcode-cn.com/problems/mi…

Trie tree

simple

  • Leetcode-cn.com/problems/lo…

medium

  • Leetcode-cn.com/problems/im…

  • Leetcode-cn.com/problems/ad…

difficult

  • Leetcode-cn.com/problems/wo…

Divide and conquer algorithm

simple

  • Leetcode-cn.com/problems/ma…

medium

  • Leetcode-cn.com/problems/ma…

  • Leetcode-cn.com/problems/se…

Backtracking algorithm

simple

  • Leetcode-cn.com/problems/le…

medium

  • Leetcode-cn.com/problems/su…

  • Leetcode-cn.com/problems/pe…

  • Leetcode-cn.com/problems/co…

difficult

  • Leetcode-cn.com/problems/n-…

Greedy algorithm

simple

  • Leetcode-cn.com/problems/as…

medium

  • Leetcode-cn.com/problems/be…

Dynamic programming

simple

  • Leetcode-cn.com/problems/cl…

  • Leetcode.com/problems/ho…

medium

  • Leetcode-cn.com/problems/be…

  • Leetcode.com/problems/ho…

  • Leetcode.com/problems/ho…

  • Leetcode.com/problems/un…

  • Leetcode.com/problems/un…

difficult

  • Leetcode-cn.com/problems/be…

  • Leetcode-cn.com/problems/be…

❤️ Thank you all

If you found this helpful:

  1. Like support, let more people can also see this content.
  2. Follow the public account front-end UpUp, contact the author 👉 DayDay2021, let’s learn and progress together.
  3. If you like it, you can also read TianTian’s recent article (thanks to the encouragement and support from friends of Mine 🌹🌹🌹) :
    • “Algorithms and Data Structures” A brain map shows the beauty of dynamic programming algorithms (370+👍)
    • “Algorithms and Data Structures” The Beauty of Trie Trees (200+👍)
    • “Algorithms and Data Structures” : The Beauty of diet-and-conquer algorithms (190+👍)
    • “Algorithms and Data Structures” The Beauty of DFS and BFS algorithms (240+👍)
    • “Algorithm and Data Structure” comb 6 sorting algorithms (220+👍)
    • “Algorithms and Data Structures” takes you through the beauty of hashing algorithms (210+👍)
    • “Algorithms and Data Structures” shows you the beauty of backtracking algorithms (190+👍)