Mr. Wang Guowei wrote in Human Words: “To become a great enterprise and a university in ancient and modern times, one must pass through three realms:
The west wind swept the green trees last night. Alone on the high building, looking at the end of the world road. ‘This first frontier is also. ‘I have no regrets. I am haggard for Iraq. ‘This second frontier is also. ‘He found thousands of degrees, suddenly look back, that person is, the lights dim. ‘This third realm.’
The same is true of algorithms.
Ramming foundation
In the initial stage, the algorithm world has just opened the door, this time confusion is normal, the key to solve the confusion is to think less and do more, go forward. With a “thousand mill thousand strike also tough, Ren Erdong southwest north wind” perseverance, climb up the algorithm of the high-rise, do “wang Tianya road”.
The first step in starting a new algorithm is to lay a solid foundation. Recommended reading:
- Algorithms 4th Edition – Robert Sedgewick
- Big Talk Data Structure– gemee
- Diagram of algorithms– Aditya Bhargava
- Introduction to Algorithms– Cormen,T.H.
⭐** Algorithm 4th Edition is suitable for beginners to get started. ⭐ Big Talk Data Structures and Algorithms Diagrams are interesting, easy to understand and perfect for beginners. ⭐ introduction to Algorithms ** is characterized by comprehensive, it is an encyclopedia of algorithms, focusing on broadening algorithm vision, suitable for learning after having a certain algorithm foundation.
The entry stage is to see some talent, the cost of time varies from person to person, about between 3 ~ 6 months, the above mentioned books to choose one of them to read the basic can enter. In this phase, you need to know a few common algorithms:
Among them, violence enumeration, greedy algorithm is easy to understand, can quickly get started. Algorithms related to number theory require some mathematical skills, including bit operations, power functions, modulus and other properties. Binary algorithms and depth-first search algorithms are relatively tricky, but they both have fixed templates. In addition, it has to be mentioned that the idea of depth-first search algorithm is very important, and depth-first search is the foundation of dynamic programming, divide and conquer and backtracking, which needs to be mastered emphatically.
🌹 Can be supplemented with simple problems in LeetCode, which often represent a class of classical algorithms, such as:
70. Climb the stairs
Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top?
🏆 the classic topic of dynamic programming algorithm, through this topic can understand the state, boundary conditions, state transition equation and other basic concepts.
112. Sum of paths
Given a binary tree and a destination sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of the values of all nodes along the path equals the destination sum.
🏆 Depth-first algorithm introductory topic, recursive implementation and iterative implementation are not difficult, you can learn to depth-first algorithm layer upon layer nested search, find the answer or reach the boundary stop basic solution ideas.
35. Search for insertion locations
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.
🏆 dichotomous algorithm typical problems, using dichotomous algorithm solution template can be easily solved, dichotomous algorithm algorithm idea is clear and clear, all.
169. The modal
Given an array of size n, find the mode. Mode is the element that occurs more than ⌊ n/2 ⌋ in the array. You can assume that the array is non-empty and that a given array always has mode.
🏆 simple problem of divide-and-conquer algorithm, if we know the mode of the left half and the right half of the array, we can use linear time to know which global mode is. This problem is wonderful is wonderful can have a variety of solutions, so that beginners can at least write violent enumeration algorithm AC topic, and then step by step, optimization algorithm.
944. Delete columns and create order
Given an array A of N lowercase character strings, each of which is of equal length. Select A delete index sequence and delete the character at each index for each string in A. The remaining string lines are read down to form columns. Suppose we select A set of delete indexes D, then after the delete operation, each remaining column in A must be in non-descending order, and you return the lowest possible value for D.length.
🏆 this is a greedy algorithm simple topic, greedy algorithm simple to understand, easy to use, suitable for beginners to master the first algorithm.
Achieve mastery through a comprehensive
Learning algorithm theory is like reading a book of martial arts secrets, but it is not enough to master the theory, and then to enter the actual practice stage.
Practice in real combat is very important. Without practice in real combat, theory is just talk on paper. For example, you’ll never know how prone dichotomy algorithms are to endless loops without a lot of practice. If a boundary condition is not properly controlled, the application will display a ruthless “Time Limit Exceeded”. After 20 minutes of debugging, you might just change while (left <= right) to while (left < right). Programmers are artisans in the final analysis, and the change of this one character is the embodiment of “one minute on stage, ten years of work off stage”. It takes a lot of practice to understand the different roles between the two.
For example, in dynamic programming algorithms, recursive functions are like “dreams within dreams” in Inception, which are layered on top of each other and gradually unfolded, making it difficult to control as a whole. After constant practice, we will know that the key point of dynamic programming algorithm is to grasp the dynamic transfer equation, only to deal with the transition and boundary conditions between two states, and slowly “small things become small things”.
This phase will take a long, long time, and you’ll get to know each algorithm as you fall and climb. Fortunately, at this stage, I don’t see talent but diligence. Every time I climb up from the pit, I dedicate myself to growth. Recommended advanced books include “Programming Pearls”, which explores a series of practical problems faced by programmers and how to solve them (solutions written in C/C++ code). The book selects many typical complex programming and algorithm problems, and elaborates and summarizes many unique and subtle design principles, thinking and problem-solving methods and practical programming techniques.
🌹 At this stage, you can try to practice the medium questions on the buckle. The medium questions will basically use only one algorithm, with some special restrictions, such as the left hook and right hook after you learn the theory of straight punch. Recommended exercises are:
1048. Longest string chain
Give a list of words, each of which is made up of lowercase English letters. If we can add a letter anywhere in word1 to make it word2, then we consider word1 to be the predecessor of word2. For example, “ABC” is the predecessor of “abac”. A word chain is a sequence of words [word_1, word_2,…, word_k], k >= 1, where word_1 is the predecessor of word_2, word_2 is the predecessor of word_3, and so on. Returns the maximum possible length of the word chain by selecting words from the given word list words.
🏆 Analysis shows that all possible word chains must be traversed to obtain the answer, and dynamic programming algorithm plays the role of memo, which is used to record the calculated answer and reduce the number of calculations.
47. Full permutation II
Given a sequence that can contain repeating digits, return all non-repeating permutations.
🏆 this problem is an enhanced version of 46. Full permutation. The problem with full permutation I is: Given a sequence with no repeated digits, return all possible full permutations. It can be solved by using depth-first search algorithm. On this basis, the problem is more difficult. There are two ways to solve it. The first method is the simplest, that is, the answer of the full array I can be used directly to duplicate. The second method is to sort the array first, and skip the repeated numbers in the full array. Such pruning optimization can reduce the number of iterations and improve the efficiency of the algorithm.
40. Sum of combinations II
Given an array of candidates and a target number target, find all combinations of the candidates that can be the sum of the number and target. Each number in the candidates must be used only once in each combination.
The backtracking algorithm derived from 🏆 depth-first search algorithm also uses the pruning optimization idea of question 47: the same number is only allowed to recurse the first one.
89. Gray code
Gray code is a binary number system in which two consecutive values differ by only one digit. Given a non-negative integer n representing the total number of encoded digits, print its Gray encoding sequence. Gray coded sequences must begin with 0.
🏆 one of the practical applications of dynamic programming algorithms.
79. Word search
Given a two-dimensional grid and a word, find out if the word exists in the grid. Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused.
🏆 The intermediate application of depth-first search, which uses a separate array to mark used elements, is also a common practice in DFS. The difficulty lies in the timing of restoring the marked array, which requires repeated practice and proficiency.
🌹 When you are comfortable with the medium problems of each type of algorithm, try the difficult problems. Difficult problems always combine two or more algorithms, or deepen the difficulty of classical algorithms, such as two-dimensional or even three-dimensional dynamic programming. Practicing difficult questions is like using the left hook and sweep legs at the same time. It not only makes the mind flow, but also brings an unparalleled sense of achievement after each AC. Recommended exercises are:
679. Twenty-four point game
You have four cards with numbers one through nine. You need to decide if you can get 24 from *, /, +, -, (,).
🧠 has only four cards and can perform only four actions. Even if all the operators are not swapped, there are only 12 * 6 * 2 * 4 * 4 * 4 = 9216 possibilities at most, which allows us to try all of these possibilities that would take a lot of work with a depth-first search algorithm.
124. Maximum path sum in binary trees
Given a nonempty binary tree, return its maximum path sum. In this case, a path is defined as a sequence that starts at any node in the tree and reaches any node. The path contains at least one node and does not necessarily go through the root node.
🧠 First, consider implementing a simplified function that calculates the maximum contribution of each node and its subtree to the path sum. Consider the second point: the maximum path does not necessarily include the root node. This means that at each step we check which option is better: continue with the current path or compute the new path with the current node as the highest node.
410. Maximum value of split array
Given an array of non-negative integers and an integer m, you need to divide the array into m contiguous non-empty subarrays. Design an algorithm that minimizes the maximum sum of these m subarrays.
🧠 dichotomy algorithm and greedy algorithm comprehensive exercise, careful analysis of its monotone relationship: the smaller the maximum value of array and, the larger the number of groups. And the range of the array and is determinable. According to this feature, the question can be converted into: when the sum of the subarray is maxSum, how many groups need to be divided into at least, can be divided within the limit of m groups. At each split, use the greedy strategy of placing as many elements as possible, until one group can’t fit, and then another group can be created. If the segmentation condition is met, the current value is recorded and the sum of subarrays is reduced by dichotomy. Otherwise, expand the sum of the subarray until the best answer is found.
new
In fact, a lot of programmers are stuck in the second level and can’t go any further. When it comes to one kind of algorithm, you can say: “I know”, “I will use”, “tread pit”, but can say “I fully understand the idea”, “I can think of some way to improve” even is few. This step is like the way of attack and defense in martial arts. When you master this layer, you can no longer stick to one sword and one sword, one move and one style. As jinshu says: flying flowers and picking leaves can hurt people, vegetation, wood, bamboo and stone can be swords.
The process of creating algorithms is hard and lonely. The birth of every classical algorithm is accompanied by “one will become ten thousand bones wither”. For example, in many languages you can call collection.sort () directly to implement quicksort. Before quicksort, there was a time when there were only three sorts: bubble, select, and insert. It wasn’t until 1959 that Hill came up with the “Hill sort” algorithm, which is probably known by very few people today. But it is the first sorting algorithm to break through the complexity, and its basic algorithm idea is as follows:
Select a delta sequence T1, T2… , where Ti > tj, tk = 1; Sort the sequence k times according to the number of incremental sequences k; In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
The GIF is shown below:
Hill sorting algorithm is more obscure, and not the best sorting algorithm, has been later to the rapid sorting algorithm to obsolete. However, there is no denying hill’s pioneering contribution to the evolution of sorting algorithms. In the way of climbing the algorithm peak, we have to remember these great guiders to encourage ourselves to continue to move forward.
💖 The algorithmic world is not perfect. There are not only classical algorithms, but also up-and-coming genetic algorithms and deep learning algorithms. There are many “treasures of King Solomon” in the algorithmic world, waiting to be discovered in “dim lights”.
Learning methods
There are many resources, blogs, and forums on the Web that make it easier for us to learn snippets of knowledge. However, this kind of learning method, while useful, is not particularly good. It is recommended that you find some systematic learning courses on the Internet to help you grow from the easy to the deep.
Algorithm learning is not done in a day, on the road to technical improvement, likou will always help you move forward.
This 📚 reproduced, the original address: zhuanlan.zhihu.com/p/73144439
We hope this article will help you 🧠 feel free to leave your thoughts in the comments 🌊, we will discuss and share 🔥