Модны навчны шийдлийн хамгийн дээд гүн


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Google-ийн Microsoft-
Өргөн уудам хайлт Гүнзгий анхны хайлт N-ary-мод

Энэ асуудалд бидэнд N-ary мод, өөрөөр хэлбэл зангилаа нь 2-оос дээш хүүхэд төрүүлэх боломжийг олгодог мод юм. Бид модны үндэснээс хамгийн хол навчны гүнийг олох хэрэгтэй. Үүнийг хамгийн их гүн гэж нэрлэдэг. Замын гүн нь түүн дээрх зангилааны тоо болохыг анхаарна уу.

Жишээ нь

       2

  /    |    \

3      4      6

                \
           
                  9
3

Тайлбар: 9-р утгатай навч нь үндэснээс хамгийн хол, гүн нь юм 3. Тиймээс бид 3-ийг хэвлэв.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

Тайлбар: 4,7 ба 9 гэсэн утгатай навчнууд нь үндэснээс хамгийн хол, гүн нь юм 3. Тиймээс бид 3-ийг хэвлэв.

Хандалт (Рекурсив)

Хоёртын модны хамгийн их гүнийг аливаа зангилааны зүүн ба баруун хүүхдүүдийн рекурсив функцийг дуудаж тооцдог. Үүнтэй адил N-ary модны хувьд бид аль ч зангилааны бүх хүүхдүүдэд рекурсив функцийг дуудаж хамгийн их гүнийг тооцоолж болно. Энэ арга нь рекурсив шинжтэй бөгөөд модны зөвхөн нэг дамжуулалт шаардагдана.

Модны навчны шийдлийн хамгийн дээд гүн

Алгоритм

  1. Функц үүсгэх maxDepth () модны хамгийн их гүнийг буцааж өгөх эх түүнд дамжуулагдана
  2. If эх хүчингүй байна:
    • буцах 0
  3. Хувьсагчийг эхлүүлэх хамгийн их Гүн N-ary модны хамгийн их гүнийг хадгалах
  4. Бүх зүйлд Хүүхэд одоогийн язгуурын хүүхдийн жагсаалтад:
    • багц maximumDepth = max (maxDepth (root.left), maxDepth (root.right))
  5. буцах хамгийн их Гүн + 1

Модон модны Leetcode шийдлийн хамгийн дээд гүнийг хэрэгжүүлэх

C ++ програм

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0;
    for(Node* &child : root->children)
        maximumDepth = max(maximumDepth , maxDepth(child));
    return maximumDepth + 1;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

Java програм

import java.lang.Math;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        int maximumDepth = 0;
        for(int i = 0 ; i < root.children.length ; i++)
            maximumDepth = Math.max(maximumDepth , maxDepth(root.children[i]));
        return maximumDepth + 1;
    }
}
3

Модны Leetcode уусмалын хамгийн их гүний нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), N = бүх модыг нэг удаа туулахдаа N-ary модны хэмжээ.

Сансрын нарийн төвөгтэй байдал

O (N) рекурсив дуудлагад зориулж стекийн жаазыг санах ойд хадгалдаг тул.

Хандалт (Давтамж)

Бид зангилаа болон тэдгээрийн гүнийг үндэснээс хадгалахын тулд стек эсвэл дарааллын аль нэгийг ашиглан давтан байдлаар дээрх процессыг хийж болно. Хамгийн их гүн нь энэ процессоос олж авсан бүх үндэсүүдийн хамгийн их гүн байх болно. Бид энэ зорилгоор дарааллыг ашиглаж, модны бүх элементүүдийг үндэс рүү гүний хамт дараалалд оруулна. Бид зангилаа бүрийн гүнийг хамгийн их гүнтэй харьцуулж шинэчилдэг.

Алгоритм

  1. Функцийг бий болгох maxDepth () Дээрх хандлагын талаар ярилцсантай ижил төстэй
  2. If эх is хүчингүй:
    • буцах 0
  3. Эхлэл хамгийн их Гүн бидний үр дүнг хадгалах
  4. Дарааллыг эхлүүлэх Элемент модны зангилаа ба тэдгээрийн гүнийг агуулдаг
  5. түлхэх эх ба түүний гүн 1 дараалалд орно
  6. Хэдийгээр Элемент хоосон биш:
    • Урд зангилаа ба түүний өндрийг авчир frontNode болон frontNodeDepth
    • Дараалалгүй байгаа зүйлийг хасах
    • If frontNodeDepth is илүү их илүү хамгийн их Гүн
      1. шинэчлэх maximumDepth = frontNodeDepth
    • If frontNode is тэг биш:
      1. Бүх хүүхдүүдээ дарааллаар нь гүн рүү нь оруул frontNodeDepth + 1
  7. буцах хамгийн их Гүн
  8. Үр дүнг хэвлэ

Модон модны Leetcode шийдлийн хамгийн дээд гүнийг хэрэгжүүлэх

C ++ програм

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0 , frontNodeDepth;

    queue <pair <Node* , int> > elements;
    elements.push({root , 1});
    Node* frontNode;
    while(!elements.empty())
    {
        frontNode = elements.front().first;
        frontNodeDepth = elements.front().second;
        elements.pop();
        if(frontNodeDepth > maximumDepth)
            maximumDepth = frontNodeDepth;

        if(frontNode != NULL)
        {
            for(Node* &child : frontNode->children)
                elements.push({child , frontNodeDepth + 1});
        }
    }

    return maximumDepth;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

Java програм

import java.lang.Math;
import java.util.*;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class Pair
{
    Node key;
    int value;
    Pair(Node root , int val)
    {
        key = root;
        value = val;
    }
}

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> elements = new LinkedList <>();
        elements.add(new Pair(root , 1));
        Node frontNode;
        int maximumDepth = 0 , frontNodeDepth;

        while(elements.size() > 0)
        {
            frontNode = elements.peek().key;
            frontNodeDepth = elements.peek().value;
            elements.remove();
            if(frontNodeDepth > maximumDepth)
                maximumDepth = frontNodeDepth;

            if(frontNode != null)
            {
                for(int i = 0 ; i < frontNode.children.length ; i++)
                    elements.add(new Pair(frontNode.children[i] , frontNodeDepth + 1));
            }
        }
        return maximumDepth;
    }
}
3

Модны Leetcode уусмалын хамгийн их гүний нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) Бид дахин бүхэл бүтэн модыг дайран өнгөрөхдөө. N = модны хэмжээ

Сансрын нарийн төвөгтэй байдал

O (N) модонд байгаа бүх зангилааны гүнийг хадгалахын тулд бид дарааллыг ашигладаг.