2022 / 7 / 1 Résumé de l'étude

Un.、102. Traversée séquentielle de l'arbre binaire - Boucle de force（LeetCode）

Description du sujet

Voici le noeud racine de l'arbre binaire root ,Renvoie sa valeur de noeud Traversée séquentielle . （C'est - à - dire couche par couche,Accédez à tous les noeuds de gauche à droite）.

Exemple 1：

Entrée：root = [3,9,20,null,null,15,7]
Produits：[[3],[9,20],[15,7]]
Exemple 2：

Entrée：root = [1]
Produits：[[1]]
Exemple 3：

Entrée：root = []
Produits：[]
 

Conseils：

Le nombre de noeuds dans l'arbre est dans la plage [0, 2000] Intérieur
-1000 <= Node.val <= 1000

Idées

Processus de traversée des séquences,En fait, c'est de haut en bas.,Mettez chaque numéro dans la file d'attente de gauche à droite,L'impression séquentielle est le résultat souhaité.

Mise en œuvre du Code

/**
 * 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)//Noeud racinaire
        {
            q.push(root);
        }
        while(!q.empty())
        {
            vector<int> b;
            int size=q.size();
            while(size--)
            {
            	// Après avoir traversé les sous - noeuds gauche et droit de ce noeud , Sortez le noeud de la file d'attente 
                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;
    }
};

2.、20. Parenthèses valides - Boucle de force（LeetCode）

Description du sujet

L'un d'eux ne comprend que '(',')','{','}','[',']' La chaîne de s ,Déterminer si la chaîne est valide.

Une chaîne valide doit satisfaire à：

La parenthèse gauche doit être fermée avec le même type de parenthèse droite.
La parenthèse gauche doit être fermée dans le bon ordre.
 

Exemple 1：

Entrée：s = "()"
Produits：true
Exemple 2：

Entrée：s = "()[]{}"
Produits：true
Exemple 3：

Entrée：s = "(]"
Produits：false
Exemple 4：

Entrée：s = "([)]"
Produits：false
Exemple 5：

Entrée：s = "{[]}"
Produits：true
 

Conseils：

1 <= s.length <= 104
s Uniquement entre parenthèses '()[]{}' Composition

Idées

C'est un simple titre sur la pile . Si vous rencontrez le support gauche ,Dans la pile. Si vous rencontrez la moitié droite de la parenthèse , Prenez l'élément supérieur de la pile et comparez - le , Si les deux correspondent ,Je sors de la pile.,Sinon,Chaîne invalide. Si ça ne tourne pas mal , Vérifiez enfin si la pile est vide ,Si non vide, Cette chaîne n'est pas valide .

Mise en œuvre du Code

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;
        }
    }
};

Trois、121. Le meilleur moment pour acheter et vendre des actions - Boucle de force（LeetCode）

Description du sujet

Compte tenu d'un tableau prices ,Son i Éléments prices[i] Représente un stock donné de i Prix par jour.

Tu ne peux choisir que Un jour Acheter cette action,Et choisissez de Un autre jour dans le futur Vendre les actions.Concevoir un algorithme pour calculer le maximum de profit que vous pouvez.

Retour au plus grand profit que vous pouvez tirer de cette transaction.Si vous ne pouvez pas faire de profit,Retour 0 .

Exemple 1：

Entrée：[7,1,5,3,6,4]
Produits：5
Explication：En 2 Oh, mon Dieu.（Cours des actions = 1）Acheter quand,En 5 Oh, mon Dieu.（Cours des actions = 6）Vendu quand,Bénéfice maximal = 6-1 = 5 .
     Notez que le profit ne peut pas être 7-1 = 6, Parce que le prix de vente doit être supérieur au prix d'achat;En même temps,Vous ne pouvez pas vendre des actions avant d'acheter.
Exemple 2：

Entrée：prices = [7,6,4,3,1]
Produits：0
Explication：Dans ce cas,, Pas d'accord conclu, Donc le bénéfice maximum est 0.
 

Conseils：

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

Idées

Parce que s'il n'y a pas de bon prix , Pas de transaction ,Le bénéfice est0, Donc, la date de vente a préséance , Trouver le prix d'achat minimum avant la date de vente , Pour trouver le plus grand profit possible à chaque date de vente .

Mise en œuvre du Code

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)// Prix d'achat minimal avant cette date 
            {
                min=prices[i];
            }
            dp[i]=prices[i]-min;
            if(max<dp[i])
            {
                max=dp[i];
            }
        }
        return max;
    }
};