Count Sub Islands Zgjidhja LeetCode

Deklarata e problemit Count Sub Islands Solution LeetCode thotë se grid1 dhe grid2 përmbajnë vetëm 0 (që përfaqëson ujin) dhe 1 (që përfaqëson tokën). Ishulli nënkupton grupin e 1-ve të lidhur me 4 drejtim. Një ishull në grid2 konsiderohet një nënishull nëse ka një ishull në grid1 që përmban të gjitha qelizat që bëjnë…

Lexo më shumë

Përshkimi i rendit vertikal i zgjidhjes LeetCode të Pemës Binare

Paraqitja e problemit Përshkimi i rendit vertikal i pemës binare Zgjidhja e LeetCode thotë – Duke pasur parasysh rrënjën e një peme binare, llogaritni përshkimin e rendit vertikal të pemës binare. Për secilën nyje në pozicion (rresht, kolonë), fëmijët e saj majtas dhe djathtas do të jenë përkatësisht në pozicionet (rresht + 1, kolon - 1) dhe (rresht + 1, kolon + 1). …

Lexo më shumë

Shuma e numrave të rrënjës në gjethe Zgjidhje LeetCode

Deklarata e problemit Shuma nga rrënja te numrat e gjetheve LeetCode Solution thotë – Ju jepet rrënja e një peme binare që përmban vetëm shifra nga 0 në 9. Çdo shteg rrënjë-gjethe në pemë përfaqëson një numër. Për shembull, shtegu rrënjë me fletë 1 -> 2 -> 3 përfaqëson numrin 123. Ktheni shumën totale të të gjithë numrave rrënjë më fletë. Test…

Lexo më shumë

Zgjidhja e LeetCode për kalimin e renditjes së pemës binare

Paraqitja e problemit: Përshkimi i renditjes së pemës binare Zgjidhja e LeetCode Duke pasur parasysh rrënjën e një peme binare, ktheni kalimin e rendit të vlerave të nyjeve të saj. Shembulli 1: Hyrja: rrënjë = [1,null,2,3] Dalja: [1,3,2] Shembulli 2: Hyrja: rrënjë = [] Dalja: [] Shembulli 3: Hyrja: rrënja = [1] Dalja: [1] Kufizimet: Numri i nyjeve në…

Lexo më shumë

A është Grafiku Bipartit? Zgjidhja LeetCode

Deklarata e problemit është Grafik Bipartit LeetCode Zgjidhja- Ekziston një graf i padrejtuar me n nyje, ku secila nyje numërohet ndërmjet 0 dhe n – 1. Ju jepet një grafik vargu 2D, ku grafi[u] është një grup nyjesh që nyja u është ngjitur me. Më formalisht, për çdo v në grafik[u], ka një skaj të padrejtuar ndërmjet nyjes u dhe nyjes v. Grafiku ka…

Lexo më shumë

Dizajnoni Shtoni dhe Kërkoni Fjalët Struktura e të Dhënave Zgjidhja LeetCode

Deklarata e problemit: Dizajnoni Strukturën e të Dhënave të Shto dhe Kërkoni Fjalët LeetCode Solution thotë – Dizajnoni një strukturë të dhënash që mbështet shtimin e fjalëve të reja dhe gjetjen nëse një varg përputhet me ndonjë varg të shtuar më parë. Zbatoni klasën WordDictionary: WordDictionary() Inicializon objektin. void addWord(word) Shton fjalë në strukturën e të dhënave, ajo mund të përputhet më vonë. bool search(fjala) Kthehet e vërtetë nëse ka…

Lexo më shumë

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur thotë se – Duke pasur parasysh root të një peme binare, rrafshoni pemën në një "listë të lidhur":

  • "Lista e lidhur" duhet të përdorë të njëjtën gjë TreeNode klasa ku right treguesi i fëmijës tregon në nyjen tjetër në listë dhe left treguesi i fëmijës është gjithmonë null.
  • "Lista e lidhur" duhet të jetë në të njëjtin rend si a para-qëllim përshkimi të pemës binare.

 

1 Shembull:

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhurinput:

 root = [1,2,5,3,4,null,6]

output:

 [1,null,2,null,3,null,4,null,5,null,6]

2 Shembull:

input:

 root = []

output:

 []

3 Shembull:

input:

 root = [0]

output:

 [0]

 

ALGORITMI -

IDE -

  • Për të rrafshuar një pemë binare, fillimisht do të gjejmë elementin më të djathtë të nënpemës së majtë dhe pasi të kemi marrë elementin më të djathtë, do të lidhim treguesin e djathtë të asaj nyje me një nënpemë të djathtë të një peme të caktuar.
  • Në hapin 2 ne do të lidhim treguesin e djathtë të nyjës rrënjë me nënpemën e majtë dhe do ta vendosim nënpemën e majtë si null.
  • Në hapin 3 tani nyja jonë rrënjë është një nyje e nënpemës së djathtë i njëjti proces do të ndodhë me këtë nyje dhe procesi do të vazhdojë akoma derisa të gjitha pjesët e majta të bëhen të pavlefshme.

Qasje për rrafshimin e pemës binare me zgjidhjen e kodit Leetcode të listës së lidhur -

– Në fillim, do të ekzekutoj një lak, dmth while(root != null) më pas do të marr dy variabla dhe do të ruaj nënpemën e majtë.

– pastaj do të kontrollojë kontrollin për nyjen më të djathtë të nënpemës së majtë duke përdorur while(k.left != null) dhe do ta lidhë atë nyje me nënpemën e djathtë duke përdorur (k.right = root.right).

– më pas lidhni treguesin e djathtë të nyjës rrënjë me nënpemën e majtë (root.djathtas = majtas) dhe vendosni treguesin e majtë të nyjes rrënjë si null (root.left=null) dhe do të përditësohet me (rrënjë = rrënjë.djathtas) kështu që tani rrënja është e drejtë nyja e nënpemës.

– ky proces do të vazhdojë derisa të gjitha pjesët e nënpemës së majtë të bëhen nënpema e djathtë. Prandaj, pema binare do të rrafshohet.

 

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur

Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur

Zgjidhja e Python:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

Zgjidhja Java:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

Kompleksiteti kohor: O(N)

Kompleksiteti i hapësirës: O (1)

Meqë kemi përshkuar vetëm një herë, kompleksiteti kohor do të jetë o(n).

dhe meqenëse nuk kemi zënë hapësirë ​​shtesë, kompleksiteti i hapësirës do të jetë o(1) hapësirë ​​shtesë konstante.

Pyetje e ngjashme - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Paraardhësi më i ulët i zakonshëm i zgjidhjes së kodit Leetcode të Pemës Binare

Deklarata e problemit Paraardhësi më i ulët i zakonshëm i një peme binare Zgjidhja LeetCode – “Paraardhësi më i ulët i zakonshëm i një peme binare” thotë se duke pasur parasysh rrënjën e pemës binare dhe dy nyjet e pemës. Ne duhet të gjejmë paraardhësin më të ulët të përbashkët të këtyre dy nyjeve. Më e ulëta e zakonshme…

Lexo më shumë

Popullimi i treguesve të ardhshëm djathtas në zgjidhjen e kodit Leetcode të çdo nyje

Deklarata e problemit Popullimi i treguesve të ardhshëm djathtas në çdo nyje Zgjidhja e LeetCode – “Popullimi i treguesve të ardhshëm djathtas në çdo nyje” thotë se duke pasur parasysh rrënjën e pemës së përsosur binare dhe ne duhet të plotësojmë çdo tregues tjetër të nyjës në nyjen tjetër të djathtë. Nëse nuk ka tjetër…

Lexo më shumë

Translate »