ARTS #015

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

ARTS 015

This is article 15

Algorihm algorithm question

The algorithm questions we did this week were preorder traversal, inorder traversal, and postorder traversal of a binary tree. Each type of traversal is implemented recursively and iteratively, respectively. The recursive implementations of the three traversals are basically the same, but the iterative implementations of the three traversals are different. Among them, the iterative implementation of the post-order traversal is the most difficult.

The difference between recursion and iteration: Recursion: The programming technique in which a program calls itself is called recursion Iteration: Use the original value of the variable to calculate a new value of the variable. Iteration means A keeps calling B.

Movie story examples: Iteration - “Edge of Tomorrow” Recursion - “Inception”

参见：
https://blog.csdn.net/laoyang360/article/details/7855860
Google：递归 迭代
斐波那契数列为:0,1,1,2,3,5...
//迭代实现斐波那契数列  
long fab_iteration(int index)  
{  
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        long f1 = 1L;  
        long f2 = 1L;  
        long f3 = 0;  
        for(int i = 0; i < index-2; i++)  
        {     
            f3 = f1 + f2; //利用变量的原值推算出变量的一个新值  
            f1 = f2;  
            f2 = f3;  
        }  
         return f3;  
    }  
}  
  
//递归实现斐波那契数列  
 long fab_recursion(int index)  
 {      
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        return fab_recursion(index-1)+fab_recursion(index-2);    //递归求值  
    }  
} 

Preorder traversal: root node —> left subtree —> right subtree In-order traversal: left subtree —> root node —> right subtree Post-order traversal: left subtree —> right subtree —> root node

94. Binary Tree Inorder Traversal

Difficulty: Medium

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

**Input:** [1,null,2,3]
   1
    \
     2
    /
   3

**Output:** [1,3,2]```

**Follow up:** Recursive solution is trivial, could you do it iteratively?



#### Solution

Language: **C**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
 

// recursive solution recursive implementation

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    //左子树
    int returnSizeLeft = 0;
    int *left = NULL;
    if(root->left != NULL){
        left= inorderTraversal(root->left, &returnSizeLeft);
    }
    
    //根结点
    
    //右子树
    int returnSizeRight = 0;
    int *right = NULL;
    if(root->right!= NULL){
        right = inorderTraversal(root->right, &returnSizeRight);
    }
    
    *returnSize = returnSizeLeft + returnSizeRight + 1;
    int* traversalResult=(int*)malloc((*returnSize)*sizeof(int));
    
    int index = 0;
    for (int i =0; i<returnSizeLeft; i++) {
        traversalResult[index++] = left[i];
    }
    free(left);
    
    traversalResult[index++] = root->val;
    
    for (int i =0; i<returnSizeRight; i++) {
        traversalResult[index++] = right[i];
    }
    free(right);

    return traversalResult;
}

// iteratively solution iterative implementation

//迭代算法 iteratively
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
   struct TreeNode** traversalResult=(struct TreeNode**)malloc(1000*sizeof(struct TreeNode*));
   if (root == NULL) {
       *returnSize = 0;
       return NULL;
   }
   int *result=(int*)malloc(1000*sizeof(int));
   *returnSize = 0;
   
   int index = 0;
   struct TreeNode* p = root;
   
   while (p != NULL || index>0) {
       printf("%d",index);
       while (p != NULL) {
               traversalResult[index++] = p;
               p = p->left;
       }
       if (index >= 1) {
           p = traversalResult[--index];
           result[(*returnSize )++] = p->val;
           p = p->right;
       }
   }
   return result;
}

144. Binary Tree Preorder Traversal

Difficulty: Medium

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[1,2,3]`

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

Language: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

//iteratively solution 迭代解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
        if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int * result = (int *)malloc(sizeof(int) * (1000));
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
   
    struct TreeNode* p=root;
    *returnSize = 0;
    int stackIndex = 0;
   
    while (p || stackIndex > 1) {
    
        result[(*returnSize)++] = p->val;
        
        if (p->right) {
            stack[stackIndex++]=p->right;
        }
        
        p = p->left;
        
        if (stackIndex > 0&&!p) {
             p = stack[--stackIndex];
        }
    }
    
    
    return result;
}

//recursive solution 递归解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        * returnSize = 0;
        return NULL;
    }
    
    //左节点
    int leftSize =  0;
    int *left = NULL;
    if(root->left){
       left =  preorderTraversal(root->left, &leftSize);
    }
    
    //右节点
    int rightSize =  0;
    int *right = NULL;
    if(root->right){
       right =  preorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize + 1;
    int * result = (int *)malloc(sizeof(int) * (*returnSize));
    
    
    int index = 0;
    
    //根节点
    result[index++] = root->val;
    
    //左节点
    for (int i =0; i<leftSize; i++) {
        result[index++] = left[i];
    }
    free(left);
    
    //右节点
    for (int i =0; i<rightSize; i++) {
        result[index++] = right[i];
    }
    free(right);
    
    return result;
}

145. Binary Tree Postorder Traversal

Difficulty: Hard

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[3,2,1]`

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

Language: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

////迭代实现 iteratively solution
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int *)malloc(sizeof(int) * 1000);
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    
    * returnSize  = 0;
    int stackIndex = 0;
    int *flag = (int *)malloc(sizeof(int) * 1000);//用来标记是否是第二次访问这个节点
    
    struct TreeNode* p = root;

    while (p || stackIndex > 1) {
        if (p) {
            int dex = stackIndex++;
            stack[dex] = p;
            flag[dex] = 1;
            
        }
        
        if (p->right) {
            int dex = stackIndex++;
            stack[dex] = p->right;
            flag[dex] = 0;
        }
        
        p = p->left;
        if (!p && stackIndex > 0) {
            int loop =1;
            while (loop && stackIndex>0) {
                int index = --stackIndex;
                p = stack[index];
                if (flag[index] == 1) {
                    result[(*returnSize)++] = p->val;
                    loop = 1;
                }
                else{
                    loop =0;
                }
            }
            if (stackIndex==0) {
                return result ;
            }
        }
    }
    return result;
}

//递归实现 Recursive solution
int* postorderTraversal_1(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int *left = NULL;
    int leftSize = 0;
    if (root->left) {
        left = postorderTraversal(root->left, &leftSize);
    }
    
    int *right = NULL;
    int rightSize = 0;
    if (root->right) {
        right = postorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize  + 1;
    int *result =  (int *)malloc(sizeof(int) * (*returnSize));
    int index = 0;
   
    for (int i = 0; i < leftSize; i++) {
        result[index++] = left[i];
    }
    
    for (int i = 0; i < rightSize; i++) {
        result[index++] = right[i];
    }
    
    result[index] = root->val;
    
    free(left);
    free(right);
    
    
    return result;
}

Review

Review as an article alone: https://dandan2009.github.io/2018/11/17/accelerating-your-coding-skills/

TIPS

This week, let’s sort out the concepts related to binary trees.

Some related concepts of binary trees:

A binary tree is a tree structure in which each node has at most two branches (that is, there are no nodes with a branch degree greater than 2). Usually branches are called “left subtree” or “right subtree”. The branches of a binary tree have left and right order and cannot be reversed at will. The i-th level of the binary tree has at most 2^i-1 nodes

different from ordinary trees The number of nodes of an ordinary tree is at least 1, while the number of nodes of a binary tree can be 0; There is no limit to the maximum branching degree of a normal tree node, while the maximum branching degree of a binary tree node is 2; The nodes of an ordinary tree have no left or right order, while the nodes of a binary tree have a left or right order.

Binary trees are usually used as data structures. A typical usage is to define a labeling function for the nodes and associate some values ​​with each node. The binary tree marked in this way can implement binary search tree and binary heap and be used for efficient search and sorting.

Binary trees are not a special case of trees Although there are many similarities between the concepts of trees and binary trees, they are two different data structures. Because from the definition: A binary tree is neither a tree with only two subtrees nor a tree with at most two subtrees. The main difference between a tree and a binary tree is that the subtree of a node in a binary tree must distinguish between the left subtree and the right subtree. Even if the node has only one subtree, it must be clearly stated whether the subtree is the left subtree or the right subtree. As for a tree, no matter how many subtrees it has, the status of each subtree is the same, unlike a binary tree where left and right are distinguished.

A binary tree is a special ordered tree: each node has at most two branches (child nodes), and the branches have left and right order and cannot be reversed. Two special binary trees: Complete Binary Tree: Except for the last layer, if all other layers are full, and the last layer is either full, or missing several consecutive nodes on the right (note that it is on the right, not on the left). Full Binary Tree: Each level is full (except the last level, where the last level refers to the leaf node).

Binary trees can be stored using arrays or linked lists. If the binary tree is full, it can be arranged compactly without wasting space. If the index of a node is i, (assuming the root node’s index is 0) then the index of its left child node will be 2i+1, and the index of its right child node will be 2i+2; and its parent node (if there is one) will have the index $\frac{i-1}{2}$. This approach is more conducive to compact storage and better locality of access, especially in preorder traversal. However, it requires continuous storage space, so a lot of space will be wasted when storing a general tree composed of n nodes with height h. In the worst case, if each node of a binary tree with depth h has only a right child, the storage structure needs to occupy 2^h - 1 space. In fact, there are h nodes, which wastes a lot of space and is a major shortcoming of the sequential storage structure.

A complete binary tree stored in an array

Depth First Traversal In depth priority, we want to access the farthest node from the root node. Different from the depth-first search of the graph, there is no need to remember every node visited, because there will be no cycles in the tree. Pre-order, In-order and Post-order traversal are all special cases of Depth-first traversal. See depth-first search.

Breadth-first traversal Unlike depth-first traversal, breadth-first traversal visits the nodes closest to the root node first. See breadth-first search. Breadth-first traversal of a binary tree is also called level-by-level traversal. The algorithm is implemented with the help of queues.

Binary tree Definition: Binary tree t is a set of finite elements (can be empty). When the binary tree is not empty, there is an element called the root, and the remaining elements (if any) are composed of two binary trees, called the left subtree and the right subtree of t respectively.

The fundamental difference between a binary tree and a tree is:

Binary trees can be empty, but trees cannot be empty. Each element in a binary tree has exactly two subtrees (one or both of which may be empty). Each element in the tree can have several subtrees. In a binary tree, the subtrees of each element are ordered, that is, they can be distinguished by the left and right subtrees. The subtrees of the tree are unordered. The figure below shows a binary tree representing a mathematical expression. There are a total of 3 mathematical expressions. Each operator can have one or two operands, the left operand is the left subtree of the operator, and the right operand is the right subtree. Leaf nodes in the tree are constants or variables.

Characteristics of binary trees Characteristic 1: The number of edges of a binary tree containing n (n>0) elements is n-1.

Prove that every element in a binary tree (except the root node) has exactly one parent node. There is only one edge between the child node and the parent node, so the number of edges is n-1.

The height or depth of a binary tree refers to the number of levels of the binary tree.

Characteristic 2: If the height of a binary tree is h, h≥0, then the binary tree has at least h elements and at most 2h−1 elements.

Proof: Since each level must have at least 1 element, the number of elements is at least h. Each element has at most 2 child nodes, so the i-th layer node elements are at most 2i-1, i>0. When h=0, the total number of elements is 0, which is 20−1. When h>0, the total number of elements will not exceed ∑hi=12i−1=2h−1.

Characteristic 3: The maximum height of a binary tree containing n elements is n, and the minimum height is ⌈log2(n+1)⌉.

Proof Since there is at least one element in each level, the height cannot exceed n. From property 2, we can know that a binary tree with height h has at most 2h−1 elements. Because n≤2h−1, therefore h≥log2(n+1). Since h is an integer, h≥⌈log2(n+1)⌉.

When a binary tree with height h has exactly 2h−1 elements, it is called a full binary tree. The picture below is a full binary tree with a height of 4.

Assume that the elements in a full binary tree of height h are numbered from 1 to 2h−1 in order from top to bottom and from left to right, as shown in the figure above. Assume that k elements are deleted from the full binary tree, and their number is 2h−i, 1≤i≤k. The resulting binary tree is called a complete binary tree. The three complete binary trees are shown in the figure below. Note that a full binary tree is a special case of a complete binary tree, and the depth of a complete binary tree with n elements is ⌈log2(n+1)⌉.

In a complete binary tree, an element has a very good correspondence with the number of its children. The relationship is given in Property 4 below.

Characteristic 4: Suppose the sequence number of an element in a complete binary tree is i, 1≤i≤n. Then the following relationship is established:

1. When i=1, the element is the root of the binary tree. If i>1, the number of the parent node of the element is ⌊i/2⌋.
2. When 2i>n, the element has no left subtree, otherwise, the number of its left subtree is 2i.
3. If 2i+1>n, the element has no right subtree, otherwise, the number of its right subtree is 2i+1.

Binary tree

1. Basic form of binary tree:

Binary trees are also defined recursively, and their nodes are divided into left and right subtrees. Logically, binary trees have five basic forms:

(1) Empty binary tree (2) Binary tree with only one root node (3) Only the right subtree (4) Only left subtree (5) Complete binary tree

Note: Although binary trees have many similarities to trees, binary trees are not a special case of trees.

2. Two important concepts:(1) Complete binary tree - a binary tree in which only the node degrees of the bottom two levels are less than 2, and the nodes of the bottom level are concentrated in several positions on the leftmost side of the level; (2) Full binary tree - a binary tree in which every node except leaf nodes has left and right cotyledons, and the leaf nodes are all at the bottom.

3. Properties of binary trees (1) In a binary tree, the total number of nodes at level i does not exceed 2^(i-1); (2) A binary tree with depth h has at most 2^h-1 nodes (h>=1) and at least h nodes; (3) For any binary tree, if the number of leaf nodes is N0 and the total number of nodes with degree 2 is N2, Then N0=N2+1; (4) The depth of a complete binary tree with n nodes is int(log2n)+1 (5) If the nodes of a complete binary tree with N nodes are stored in a sequential manner, the nodes have the following relationship: If I is the node number, then if I<>1, then the number of its parent node is I/2; If 2I<=N, then the number of its left son (that is, the root node of the left subtree) is 2I; if 2I>N, there is no left son; If 2I+1<=N, then the node number of its right son is 2I+1; if 2I+1>N, there is no right son. (6) Given N nodes, h(N) different binary trees can be formed. h(N) is the Nth term of Cattelan number. h(n)=C(n,2*n)/(n+1).

full binary tree A binary tree with depth k and 2 to the (k) power - 1 node. Features: The number of nodes on each level is the maximum number of nodes.

The definition of a complete binary tree: A binary tree with depth k and n nodes is called a complete binary tree if and only if each of its nodes corresponds to a node numbered from 1 to n in a full binary tree with depth k. Features: Leaf nodes can only appear on the two largest levels; for any node, if the maximum level of its descendants under the right branch is l, then the maximum level of its descendants under the left branch must be l or l+1. Full binary tree: a binary tree with a depth of k and 2 to the power of 1 - 1 nodes. Features: The number of nodes on each layer is the maximum number of nodes. A full binary tree is definitely a complete binary tree. A complete binary tree is not necessarily a full binary tree.

But the binary search tree has a very troublesome problem. If random data is inserted into the tree, the execution effect is very good, but if ordered or reverse-order data is inserted, the execution speed of the binary search tree becomes very slow. Because when the inserted values ​​are ordered, the binary tree is unbalanced, and its ability to quickly find, insert, and delete specified data items is lost.

To solve this problem, we can use multi-tree.

A 2-3-4 tree is a multi-tree, with each node having up to four child nodes and three data items. The 2-3-4 tree, like the red-black tree, is also a balanced tree. Its efficiency is slightly worse than the red-black tree, but it is easier to program. The meanings of 2, 3, and 4 in the name of the 2-3-4 tree refer to the number of child nodes that a node may contain. There are three possible situations for non-leaf nodes:

A node with a data item always has two child nodes; A node with two data items always has three child nodes; A node with three data items always has four byte points.

Binary search tree, 2-3-4 tree, red-black tree

Binary tree

Reference; https://zh.wikipedia.org/wiki/二叉树 https://www.cnblogs.com/myjavascript/articles/4092746.html

Share

How to learn data structures and algorithms? I have shared this once before, and recently I saw an article that is very consistent with my thoughts. Here is a summary:

The basics you need before answering questions

1. Common data structures: linked lists, trees (such as binary trees).
2. Common algorithm ideas: greedy method, divide and conquer method, exhaustive method, dynamic programming, backtracking method.
3. Common sorting algorithms

If you don’t even know these most basic things, then you will have a hard time solving the questions and you will have relatively few ideas. It can be said that for many questions you will only use brute force methods, so you still need to be proficient in these basic things before solving the questions.

You must also read books and study systematically.

The last one must be practiced more. During the practice process, you must learn other people’s excellent solutions. Don’t do it yourself and everything will be fine. You must look at other people’s implementations and analyze them carefully yourself.

In addition to leetcode, there are also nuke.com and the following websites for writing questions. 18 Websites to Practice Your Programming Skills https://blog.csdn.net/lyn167/article/details/52134859 [topcoder] https://www.topcoder.com/ HackerEarth http://www.hackerearth.com/ Coderbyte https://coderbyte.com/ Project Euler: https://projecteuler.net/

Reference: How did I learn data structures and algorithms? ：https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ WeChat content is often lost, here is a copy: Original link: https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ

The status of data structures and algorithms is self-evident to a programmer. Today’s article is not here to advise you to learn data structures and algorithms, nor is it here to tell you how important data structures and algorithms are.

Mainly because in the past few days, readers have asked me how I learned data structures and algorithms, whether there are any shortcuts, whether to watch videos or read books, where to study questions, etc… And some of them are juniors and seniors, so I am anxious and worried for you…

So today I will share how I usually study.

The shortcut to learning algorithms is to answer more questions To be honest, when it comes to shortcuts, I think it is to be down-to-earth and practice more questions, and answer more questions.

However, if you are a novice, that is to say, you have not even learned common data structures, such as linked lists, trees, and common algorithm ideas, such as recursion, enumeration, and dynamic programming, then I do not recommend you to study the questions. Instead, go find a book to learn these first, and then answer the questions.

In other words, if you want to go to a website such as leetcode to answer questions, you must first have a certain foundation. These foundations include:

1. Common data structures: linked lists, trees (such as binary trees).

2. Common algorithm ideas: greedy method, divide and conquer method, exhaustive method, dynamic programming, backtracking method.

The ones listed above are the most basic ones. That is to say, before you answer the questions, you should go through these again and then answer the questions. If you don’t even know these most basic things, then you will have a hard time answering the questions and you will have relatively few ideas.

In short, don’t be in a hurry. Go through these basics first and try to understand them before answering the questions. I learned these basic data structures and algorithms in the second semester of my freshman year. I didn’t watch the videos. I learned them by reading books. The books I read at that time were:

1. Algorithm Analysis and Analysis Basics: This book is relatively simple and is recommended for novices.

2. Data structure and algorithm analysis—C language description: The code is written in C. It is recommended to read it.

3. Challenge Programming Competition (Second Edition): This is also a very good book, recommended.

For details, you can read my other article, which introduces these books: Algorithm and data structure books and video benefits

To be honest, I spent almost all my time in that semester on data structures and algorithms, but there were very few questions, just some examples from the book. So after I went through these basics, it was still very difficult to go to some websites to answer questions.

So don’t expect to think that you will be good at answering questions after learning these ideas. Only by answering more questions and practicing more can your sensitivity be improved.

Let me talk about a very popular column a while ago - [The Beauty of Data Structures and Algorithms]

I didn’t buy this column. What I want to say is, if you buy it, you must read it and don’t waste it. Don’t think that you will become more awesome after learning this column. If you just follow the progress of learning this column, you will not spend time to answer questions and do hands-on time. Then I can guarantee that you will still be good at it after you finish studying.

To summarize:

There is no shortcut to improving data structures and algorithms. The best shortcut is to answer more questions. However, the prerequisite for solving the questions is that you must first learn some basic data structures and algorithm ideas.

pursuit of perfection How to answer questions? How to deal with an algorithm problem?

I think that when doing questions, you must pursue perfection. Never finish a question, submit it and pass it, and then rush to the next one.

There is a certain relationship between the improvement of algorithmic capabilities and the number of questions, but it is not a linear relationship. In other words, when solving a problem, you should strive to solve multiple problems. If you really can’t think of another way, you can go and see how others do it. Don’t feel that it is shameful to imitate what others do.

When I am doing a question, when I see a question, my first thought may be to solve it in a very crude way, because many questions are easy to solve using the brute force method, but the time complexity is very high. After that, I will slowly think about it and see if there are other ways to reduce the time complexity or space complexity. Finally, I will look at what others have done. Of course, not every question will be executed this way.

Measuring the quality of an algorithm problem is nothing more than time complexity and space complexity. Therefore, if we want to strive for perfection, we must minimize these two and make them complement each other.

Let me give you an example:

Question: A frog can jump up 1 step or 2 steps at a time. How many ways can the frog jump up an n-level staircase?

I have analyzed this question in previous chapters. If you don’t understand, you can read what I wrote before: Recursion and Dynamic Programming—Basic Chapter 1

Method 1:: Violent recursion

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

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

The time complexity of this approach is very high, exponential. But if you luckily pass after submitting, and then you move on to the next question, then you need to think about it carefully.

Method 2: Exchange space for time

To strive for perfection, we can consider exchanging space for time: If you think about this question carefully, you will find that many of it are repeated. So you can take the following approach:

//Use a HashMap to save the calculated state 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 it has been calculated if(map.containsKey(n)){ return map.get(n); }else{ int m = solve(n-1) + solve(n-2); map.put(n, m); return m; } } }

In this way, the time can be greatly shortened. In other words, after you solve a problem and find that the time complexity is very high, you can consider whether there is a better method and whether you can trade space for time.

Method 3: Fibonacci Sequence

In fact, we can make the space complexity even smaller and don’t need a HashMap to save the 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; }

I am showing you this question not to teach you how to do it, but for the following purposes:

1. When answering questions, we must strive for perfection.

2. I can’t think of these methods, what should I do? Then you can look at what others have done. Later, when you encounter similar problems, you will have more ideas and know which direction to think in.

3. You can start with simple violence to solve a problem, and optimize it bit by bit while considering the measurement between space and time.

Recommend some question brushing websites I usually study questions on Leetcode and Niuke.com, and they feel pretty good. The questions are not very difficult.

On Niuke.com, I mainly studied Jianzhi Offer, but there is also an online program called Leetcode, but the number of questions in it is relatively small. A very convenient place to solve questions on Niuke.com is the discussion area. There will be many big guys sharing their problem-solving methods, so we don’t have to go to Baidu to find the solution. So after you finish it and you really can’t think of anything else, you can easily go and see how others did it.

As for leetcode, most of the questions have official answers, and it is also a good website for brushing up on questions. You can pick one of the two, or do both.

Of course, there are other websites that brush the questions, but since I haven’t brushed the other websites, I don’t know how to clear them.

Let’s talk about data structure Earlier I mainly talked about how I usually learn algorithms. In terms of data structure methods, I just listed that you must learn linked lists and trees (binary heaps), but these are the most basic and must be mastered before answering questions. For data structures, I will list some of the more important ones:

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

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

3. Graph (such as several algorithms for shortest paths).

4. Queue, stack, matrix.

For these, you must implement it yourself. You can read books or watch videos. Newbies can watch videos first, but you can watch videos in the early stage. After that, I suggest you must read books.

I have recommended videos and books before: Algorithm and data structure books and video benefits

For example, for the balanced tree, you may forget it after a while after following the code in the book, but it doesn’t matter. Although you have forgotten it, if you have implemented it with code before and understood it, then when you see it again, you will quickly remember it and understand the idea quickly, and your abstraction ability will be improved unconsciously. Later, if you learn about red-black trees and other data structures, you will learn them very quickly.

The most important Do it, do it, do it. Say important things three times.

Don’t find a bunch of resources, make a study plan, and leave it until a certain day to do it…

Don’t do this, but when your passion comes, do it immediately. Don’t leave it until a holiday or whatever. Many people who think like this will end up doing nothing.

Don’t feel like there is so much to learn and you don’t know where to start. As I said above, you can learn the most basic ones first, and then study the questions. Studying the questions is a matter that requires long-term persistence, one year or two years. In the process of solving the questions, you can intersperse learning of other data structures.