2022/7/1 learning summary

One 、102. Sequence traversal of binary tree - Power button （LeetCode）

Title Description

Give you the root node of the binary tree root , Returns the Sequence traversal . （ That is, layer by layer , Access all nodes from left to right ）.

Example 1：

Input ：root = [3,9,20,null,null,15,7]
Output ：[[3],[9,20],[15,7]]
Example 2：

Input ：root = [1]
Output ：[[1]]
Example 3：

Input ：root = []
Output ：[]
 

Tips ：

The number of nodes in the tree is in the range [0, 2000] Inside
-1000 <= Node.val <= 1000

Ideas

Sequence traversal process , It's actually from top to bottom , Put each number in the queue from left to right , Then print in order, which is the desired result .

Code implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> a;
        queue<TreeNode*> q;
        if(root!=NULL)// Root node 
        {
            q.push(root);
        }
        while(!q.empty())
        {
            vector<int> b;
            int size=q.size();
            while(size--)
            {
            	// After traversing the left and right child nodes of this node , Take the node out of the queue 
                if(q.front()->left)
                {
                    q.push(q.front()->left);
                }
                if(q.front()->right)
                {
                    q.push(q.front()->right);
                }
                b.push_back(q.front()->val);
                q.pop();
            }
            a.push_back(b);
        }
        return a;
    }
};

Two 、20. Valid parenthesis - Power button （LeetCode）

Title Description

Given one only includes '(',')','{','}','[',']'  String s , Determines whether the string is valid .

Valid string needs to meet ：

Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .
 

Example 1：

Input ：s = "()"
Output ：true
Example  2：

Input ：s = "()[]{}"
Output ：true
Example  3：

Input ：s = "(]"
Output ：false
Example  4：

Input ：s = "([)]"
Output ：false
Example  5：

Input ：s = "{[]}"
Output ：true
 

Tips ：

1 <= s.length <= 104
s Brackets only '()[]{}' form

Ideas

This is a simple topic about stack . If you encounter the left bracket , It into the stack . If you encounter the right bracket , Take the top element of the stack and compare it , If the two match , Out of the stack , otherwise , Invalid string . If there is no problem with the previous step , Finally, check whether the stack is empty , If it is not empty , That string is invalid .

Code implementation

class Solution {
public:
    bool isValid(string s) {
        char a[10001];
        int top=0;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='('||s[i]=='['||s[i]=='{')
            {
                a[top++]=s[i];
            }
            else
            {
                if(s[i]==')')
                {
                    if(top>0&&a[top-1]=='(')
                    {
                        top--;
                    }
                    else
                    {
                        return false;
                    }
                }
                if(s[i]=='}')
                {
                    if(top>0&&a[top-1]=='{')
                    {
                        top--;
                    }
                    else
                    {
                        return false;
                    }
                }
                if(s[i]==']')
                {
                    if(top>0&&a[top-1]=='[')
                    {
                        top--;
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }
        if(top==0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

3、 ... and 、121. The best time to buy and sell stocks - Power button （LeetCode）

Title Description

Given an array prices , It's the first  i Elements  prices[i] Represents the number of shares in a given stock i Sky price .

You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

Example 1：

Input ：[7,1,5,3,6,4]
Output ：5
explain ： In the 2 God （ Stock price = 1） Buy when , In the 5 God （ Stock price = 6） Sell when , Maximum profit = 6-1 = 5 .
      Note that profit cannot be 7-1 = 6, Because the selling price needs to be higher than the buying price ; meanwhile , You can't sell stocks before you buy them .
Example 2：

Input ：prices = [7,6,4,3,1]
Output ：0
explain ： under these circumstances , No deal is done , So the biggest profit is 0.
 

Tips ：

1 <= prices.length <= 105
0 <= prices[i] <= 104

Ideas

Because if there is no suitable price , Do not trade , Profit is 0, Therefore, the date of sale shall prevail , Find the minimum buying price before the selling date , So as to find the maximum profit that can be obtained on each selling date .

Code implementation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max,min=prices[0],dp[prices.size()];
        dp[0]=0;
        max=dp[0];
        for(int i=1;i<prices.size();i++)
        {
            if(prices[i]<min)// The minimum buying price before that day 
            {
                min=prices[i];
            }
            dp[i]=prices[i]-min;
            if(max<dp[i])
            {
                max=dp[i];
            }
        }
        return max;
    }
};