First understanding of the idea of partition and rule (notes of runners)

Shuwen's future goal: enter the big factory~ ðŸĪŠ. Let my family relax and try to make life better, okay!
Shu Wen's current situation: big dish chicken, from food to code, has made many learning friends (great) 👍)
Blog purpose: writing a blog is to record your learning path It's also to brighten the interviewer's eyes, and then pretend to be forced
Little recommendation: I created and managed a community with my friends in CSDN. If you are interested, you can come and have a look 👉 Non Coban transcoding community).👈
(Shu Wen will answer questions and punch in the community. Let's join this big family 😍)
Objective at this stage: learn basic knowledge and know more about the computer industry Keep good health, make more friends, make more mistakes and learn from them 😍.
In the last issue, I introduced the upgrade of heap sorting and the TOPK problem 👉 Upgrading of binary tree sorting & TOPK problem

preface

Today's divide and conquer idea is an idea that I use in the traversal of pre order, middle order and post order and some later topics when learning trees. It seems that there is another sort that also needs to use this divide and conquer idea. Therefore, Shu Wen wants to work hard to understand this idea and provide a reference for you This time mainly focuses on a large number of topics, so you don't have to worry about a large number of theoretical things

text

The basic idea of divide and conquer

Divide and conquer, divide and conquer. When we encounter a problem that cannot or is difficult to get the answer directly through thinking, we can divide the big problem into several similar sub problems, then solve the sub problems many times, and then merge them to finally get the answer we want

Divide and conquer thought

The basic idea of divide and conquer

Divide the big problem into several similar sub problems, and then solve the sub problems many times, and then combine them to get the answer we want

It should be noted that our sub problems are independent and cannot affect each other, otherwise we will not be able to use the idea of partition and rule

Example explanation

Example 1 < same tree >

Same tree

We can explain this problem with the idea of divide and conquer

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
   
    if(p == NULL && q == NULL)//It is also true when both subproblems are empty
        return true;
    if(p == NULL)//Like the following if conditional sentence, P and Q cannot be empty at the same time after the previous but not returned
        return false;
    if(q == NULL)
        return false;
    if(p->val != q->val)//When this condition is established, we need all to be true
    {
        return false;
    }
    return isSameTree(p->right,q->right) && isSameTree(p->left,q->left);//Using & & will make a false all false. You can also use * instead
}

Let's explain it through the example of [1,2,3] [1,2,3] above

We treat each node as a sub problem So we need to analyze the types of subproblems

Four types

  1. p. When q is both NULL and empty, pq is also equal and returns true
  2. If p is empty and q is not empty, false is returned
  3. q is empty, p is not empty, return false
  4. Both are not empty, but if the val of p and q are different, false should also be returned

There are only so many types of subproblems. Finally, when we return, we need to synthesize all the subproblems

Because our trees are different when either right or left is false, we use & & to make the false false false

Example 2 < symmetric binary tree >

101. Symmetric binary tree LeetCode (LeetCode CN. Com)

Mirror symmetry, so we can directly ignore our root node. We just need to see whether the left and right nodes can be mirror symmetrical, so we need to get the addresses of the left and right nodes and put them in the same function for recursive comparison So we can open up another function to achieve this goal

as follows

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode* p,struct TreeNode* q)//Our own function
{
    if(p==NULL&&q==NULL)//Both NULL and
        return true;
    else if(p==NULL||q==NULL)//One is empty and the other is not empty
        return false;
    if(p->val!=q->val)//We divide the subproblem into a single node problem for recursive adjustment
        return false;
    return _isSymmetric(p->left,q->right)&&_isSymmetric(p->right,q->left);//Adjust by recursion
}
bool isSymmetric(struct TreeNode* root)
{
    return _isSymmetric(root->right,root->left);//The root node is meaningless and can be omitted directly
}

When we use the idea of divide and conquer, we should consider the problems brought by each sub problem and consider the results we want to get. In the combination part, we should also adjust according to the conditions

Example 3 < preorder traversal of binary tree >

144. Preorder traversal of binary tree LeetCode (LeetCode CN. Com)

We need to return the array of values obtained by previous traversal. The array needs to get space through malloc

Let's look at the code first:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int Bsize(struct TreeNode* root)
 {
    if(root==NULL)
        return 0;
    return Bsize(root->left)+Bsize(root->right)+1;//The idea of partition is still used
 }
 void _preorderTraversal(struct TreeNode* root,int *arr,int* pi)
 {
    if(root == NULL)//End the process directly when it is empty
        return;
    //The following root cannot be empty
    arr[*pi] = root->val;//Get the value of the root first
    (*pi)++;
    _preorderTraversal(root->left,arr,pi);//The first order is left
    _preorderTraversal(root->right,arr,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = Bsize(root);
    int *arr = (int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    _preorderTraversal(root,arr,&i);//i is passed to record subscripts during recursion
    return arr;
}

In fact, the explanation is almost the same. When we get the size, we also use the idea of divide and conquer. We treat each node as a sub problem, and then add ourselves to operate from left to right

Tags: C Algorithm data structure Dynamic Programming

Posted by califdon on Sat, 16 Apr 2022 01:35:25 +0300