د پلرني صف څخه د عمومي ونې لوړوالی


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي د ګوګل پیرو یو Qualcomm سپرینکلر über
لومړی پراخه پلټنه متحرک برنامې ګراف په ليکه کې ونې

ستونزه بیان

"د والدین سرنی څخه د عمومي ونې لوړوالی" ستونزه په ګوته کوي چې تاسو ته د سرنی پار په توګه د n عمودی سره یوه ونه درکول کیږي [0… n-1]. دلته هر انډیکس i په مساوی توګه [] د نوډ استازیتوب کوي او زه یې ارزښت د دې نوډ سمدستي والدین استازیتوب کوم. د مور او پلار پرته د روټ نوډ لپاره ، د دې په مساوي [] سرنی کې به ارزښت -1 وي. اوس موږ اړتیا لرو د ونې اوږدوالی ومومئ چې اصلي اړیکې ورکړل شوي.

لاندې ورکړل شوي برخې ته پام وکړئ []

د پلرني صف څخه د عمومي ونې لوړوالی

هغه ونې چې د دې پار [] سرې اړیکې په کارولو سره جوړیږي لاندې ورکړل شوي دي:

د پلرني صف څخه د عمومي ونې لوړوالی

نوټ: د ونې اوږدوالی له 100 واحدونو څخه ډیر نشي.

د پلرني صف څخه د عمومي ونې لوړوالی

بېلګه

[-1 0 0 1 2 2 4]
3

توضیحي: په اوږده لاره کې د څنډو شمیره 3 ده.

[-1 0 0 1 1 2 2 3 3 4 7]
4

توضیحي: په اوږده لاره کې د څنډو شمیره (0-> 1-> 3-> 7-> 10) 4 دی.

د حل ډولونه

  1. د لومړي نه لومړۍ پلټنه
  2. متحرک برنامې

د لومړي نه لومړۍ پلټنه

د والدین له صف څخه د عمومي ونې لوړوالي موندلو لپاره لاره

د دې ستونزې حل کولو لپاره موږ به ورکړل شوي پار [] سرنی په کارولو سره د ونې (ګراف ډیټا جوړښت) جوړ کړو. اوس موږ BFS ترسره کوو چې د ریښې نوډ څخه پیل کیږي او د ونې د لارې اوږدو کې ترټولو اوږده لاره (یا ترټولو لرې واټکی) ومومئ. نو ، د دې فاصلو ارزښت پخپله د ونې لوړوالی ویل کیږي. BFS د ګراف ټریورسل الګوریتم پرته بل څه ندي چې ټوله ګراف تعقیبوي. د لومړي نه لومړۍ پلټنه داسې کار کوي چې نوډونه چې اوسني نوډ ته نږدې وي د نوډونو دمخه لا ډیر واټن لري تعقیب شوي. پدې توګه موږ وړ یو چې د ریښې څخه د هر نوډ فاصله ومومئ. او نوډ د لوی فاصله سره ویل کیږي د ونې لوړوالی کې نوډ دی.

الګوریتم

1. Construct the directed graph using the par[] array values.
2. The edges in graph should be directed from node par[i] to i. i.e, par[i] --> i.
3. The root node has no parent and hence, no incoming edge.
4. Now starting from the root node, perform BFS, and calculate distance of each of the nodes in the tree from the root node itself.
5. The largest distance value is the height of the tree.

 

الګوریتم لاندې ښودل شوی:

د پلرني صف څخه د عمومي ونې لوړوالی

د پلرني صف څخه د عمومي ونې لوړوالی

د BFS په کارولو سره د عامې ونې لوړوالی

کوډ

C ++ برنامه د پلرني صف څخه د عمومي ونې لوړوالی موندلو لپاره

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

// perform BFS to calculate Height
int BFS(vector <int> par)
{
    int root;
    int n = par.size();
    vector <int> graph[n];
    
    // construct graph from given parent array
    for(int i=0;i<n;i++)
    {
        if(par[i] != -1)
        graph[par[i]].push_back(i);    
        
        else
        root = i;
    }
    
    // to store distance of each node from the root
    vector <int> distance(n,0);
    
    // create BFS queue
    queue <int> q;
    // insert the root node
    q.push(root);
    
    // Begin BFS & calculate distance of each node from root
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        
        for(auto i : graph[front])
        {
            distance[i] = distance[front] + 1;
            q.push(i);
        }
    }
    
    // return height of the Tree
    return *max_element(distance.begin(),distance.end());
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<BFS(par)<<endl;
    return 0;
}
Height of the Tree : 3

د جاوا برنامه د اصلي سرنې څخه د عمومي ونې لوړوالی موندلو لپاره

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // perform BFS to calculate Height
    static int BFS(int [] par)
    {
        int root = 0;
        int n = par.length;
        ArrayList <ArrayList <Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        // construct graph from given parent array
        for(int i=0;i<n;i++)
        {
            graph.add(new ArrayList<Integer>());
            
            if(par[i] != -1)
            graph.get(par[i]).add(i);    
            
            else
            root = i;
        }
        
        // to store distance of each node from the root
        int distance[] = new int[n];
        
        // create BFS queue
        Queue <Integer> q = new LinkedList<>();
        // insert the root node
        q.add(root);
        
        // Begin BFS & calculate distance of each node from root
        while(!q.isEmpty())
        {
            int front = q.poll();
            
            Iterator itr = graph.get(front).iterator();
            
            while(itr.hasNext())
            {
                int i = (Integer)itr.next();
                distance[i] = distance[front] + 1;
                q.add(i);
            }
        }
        
        // return height of the Tree
        int height = 0;
        for(int i=0;i<distance.length;i++)
        height = Math.max(height,distance[i]);
        
        return height;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+BFS(par));
    }
}
Height of the Tree : 3

د پیچلتیا تحلیل

د وخت پیچلتیا

T (n) = O (V + E) = O (2V-1) = O (V). دلته موږ د لومړي لمبر لټون ترسره کړی چې دا به ټول ونې پوښلي پدې توګه به د ټول عمودی څوکې پوښلي. پدې توګه موږ ته د خطي وخت پیچلتیا راکول.

د ځای پیچلتیا

A (n) = O (V)، د BFS قطار او ګراف ونې لپاره رامینځته شوی. په بدترین حالت کې ، موږ کولی شو د سټار ونې ولرو ، چیرې چې ټول نوډونه د ریښې پرته نور ورته والدین لري. پدې توګه پدې حالت کې ، د بدترین ځای پیچلتیا به ترلاسه شي کوم چې به O (V) وي.

چیرې ،

V = په ونه کې د څوکو شمیر.

E = په ونې کې د څنډو شمیره = V-1

متحرک برنامې

د والدین له صف څخه د عمومي ونې لوړوالي موندلو لپاره لاره

په یوه ونې د N نوډونو څخه ، هر نوډ ته له 0 څخه تر N-1 پورې په مراجعه وکړئ. د هرې نوډ محاسبه لپاره دا د فنکشن په کارولو سره قد دی موندنه () (د نوډ لوړوالی د هغه ځانګړي نوډ او د ریښې نوډ ترمینځ د څنډو شمیره ده).

مخکې لدې چې د نوډ لوړوالی محاسبه کړئ ، د دې ټولو پلرونو نوډونو اوږدوالی باید په تکراري ډول محاسبه شي. د موندنه () دا دنده په مکرر ډول ترسره کوي. وروسته په ونه کې د نوډ لوړوالی محاسبه. دا باید د لیدل شوي په توګه نښه شي (لیدنه [] صف د دې مقصد لپاره کارول کیږي).

الګوریتم

1. Define two functions findDistance( ) & findHeight( ) for calculating height of each node in the tree.
2. Visit each node iteratively in order from 0 to V-1 (where V = number of vertices).
3. For a particular node, calculate heights of all it's ancestors recursively before the calculating height of the node itself, this is done using findDistance() recursive function.
4. every ancestor node visited should be marked as visited (using visited[ ] array).
5. Return the maximum value in the height[ ].
6. steps 1 to 5 are encapsulated in findHeight( ) function.

 

د متحرک پروګرام کولو په کارولو سره د ونې لوړوالی

 

کوډ

C ++ برنامه د پلرونکي صف څخه د عمومي ونې لوړوالی موندلو لپاره

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

// function to find height of node - i from tree root
int findDistance(vector <int> par, int i, vector <bool> &visited, vector <int> &height)
{
    // if root node is encountered
    if(par[i] == -1)
    {
        visited[i] = true;
        return 0;
    }
    
    // if node is already visited
    // return it's calculated height
    if(visited[i])
    return height[i];
    
    // if a node is not visited
    // below steps are executed
    
    // mark node visited
    visited[i] = true;
    // calculate height of node
    height[i] = 1+findDistance(par,par[i],visited,height);
    // return height after calculation    
    return height[i];
}

// function to calculate maximum height
int findHeight(vector <int> par)
{
    int maxHeight = 0;
    
    int n = par.size();
    
    // visited array is used to check if a node is visited
    vector <bool> visited(n,false);
    // calculate height of each node in the tree
    vector <int> height(n,0);
    
    // traverse each node of the tree
    // evaluate height of each node & store maximum of all heights 
    for(int i=0;i<n;i++)
    {
        height[i] = findDistance(par,i,visited,height);
        maxHeight = max(maxHeight,height[i]);
    }
    
    // return maximum of all heights
    return maxHeight;
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<findHeight(par)<<endl;
    return 0;
}
Height of the Tree : 3

د جاوا برنامه د اصلي سرنې څخه د عمومي ونې لوړوالی موندلو لپاره

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // function to find height of node - i from tree root
    static int findDistance(int [] par, int i, boolean [] visited, int [] height)
    {
        // if root node is encountered
        if(par[i] == -1)
        {
            visited[i] = true;
            return 0;
        }
        
        // if node is already visited
        // return it's calculated height
        if(visited[i] == true)
        return height[i];
        
        // if a node is not visited
        // below steps are executed
        
        // mark node visited
        visited[i] = true;
        // calculate height of node
        height[i] = 1+findDistance(par,par[i],visited,height);
        // return height after calculation    
        return height[i];
    }

    // function to calculate maximum height
    static int findHeight(int [] par)
    {
        int maxHeight = 0;
        
        int n = par.length;
        
        // visited array is used to check if a node is visited
        boolean [] visited = new boolean[n];
        // calculate height of each node in the tree
        int [] height = new int[n];
        
        // traverse each node of the tree
        // evaluate height of each node & store maximum of all heights 
        for(int i=0;i<n;i++)
        {
            height[i] = findDistance(par,i,visited,height);
            maxHeight = Math.max(maxHeight,height[i]);
        }
        
        // return maximum of all heights
        return maxHeight;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+findHeight(par));
    }
}
Height of the Tree : 3

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N) ،  ځکه چې دلته به موږ د ونې ټول نوډونه تیروو. ځکه چې موږ به د ونې ټول نوډونه تیروو. د دې له امله ، موږ د خط وخت پیچلتیا ترلاسه کړه O (N) چیرې چې N په ونه کې د نوډونو شمیر منع کړی.

د ځای پیچلتیا

O (N) ، موږ اړتیا لرو د هر یو نوډونو لپاره لوړوالي ذخیره کړو. ځکه چې دا به وکارول شي کله چې د اوسني نوډ ماشومانو لخوا. پدې توګه الګوریتم د خطي خلا پیچلتیا لري.