Rješenje za minimalnu sumu putanje Leetcode

Izjava problema Minimalni zbroj putanja LeetCode Rješenje – “Minimalni zbroj puta” kaže da je data anxm mreža koja se sastoji od nenegativnih cijelih brojeva i da moramo pronaći put od gornjeg lijevog do donjeg desnog, što minimizira zbroj svih brojeva duž putanje . Možemo se samo kretati…

Čitaj više

Rješenje za dekodiranje niza Leetcode

Izjava o problemu Decode String LeetCode Rješenje – “Decode String” traži od vas da pretvorite kodirani niz u dekodirani niz. Pravilo kodiranja je k[kodirani_niz], gdje se kodirani_string unutar uglastih zagrada ponavlja točno k puta pri čemu je k pozitivan cijeli broj. Primjer: Ulaz: s = ”3[a]2[bc]” Izlaz: “aaabcbc” …

Čitaj više

Poravnajte binarno stablo na povezani popis LeetCode rješenje

Poravnajte binarno stablo na povezani popis LeetCode rješenje kaže da – S obzirom na root binarnog stabla, poravnajte stablo u "povezani popis":

  • "Povezani popis" trebao bi koristiti isto TreeNode razred gdje se right dijete pokazivač pokazuje na sljedeći čvor na popisu i left dječji pokazivač je uvijek null.
  • "Povezani popis" trebao bi biti istim redoslijedom kao a unaprijed naručiti prijelaz binarnog stabla.

 

Primjer 1:

Poravnajte binarno stablo na povezani popis LeetCode rješenjeUlazni:

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

Izlaz:

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

Primjer 2:

Ulazni:

 root = []

Izlaz:

 []

Primjer 3:

Ulazni:

 root = [0]

Izlaz:

 [0]

 

ALGORITAM –

IDEJA –

  • Kako bismo izravnali binarno stablo, prvo ćemo pronaći krajnji desni element lijevog podstabla, a nakon što dobijemo krajnji desni element povezat ćemo desni pokazivač tog čvora s desnim podstablom danog stabla.
  • U koraku 2 povezat ćemo desni pokazivač korijenskog čvora s lijevim podstablom i postaviti lijevo podstablo kao null.
  • U koraku 3 sada je naš korijenski čvor čvor desnog podstabla, isti proces će se dogoditi s ovim čvorom i proces će se nastaviti sve dok svi lijevi dijelovi ne postanu nulti.

Pristup za izravnavanje binarnog stabla na povezanu listu Leetcode rješenje –

– Prvo ću pokrenuti petlju, tj. while(root != null), a zatim ću uzeti dvije varijable i pohraniti lijevo podstablo.

– zatim će provjeriti krajnji desni čvor lijevog podstabla korištenjem while(k.left != null) i povezati taj čvor s desnim podstablom koristeći (k.right = root.right).

– zatim povežite desni pokazivač korijenskog čvora s lijevim podstablom (root.right = lijevo) i postavite lijevi pokazivač korijenskog čvora kao null(root.left=null) i ažurirat će se za ( root = root.right ) tako da je sada root udesno čvor podstabla.

– ovaj proces će se nastaviti sve dok svi dijelovi lijevog podstabla ne postanu desno podstablo. Dakle, binarno stablo će se spljoštiti.

 

Poravnajte binarno stablo na povezani popis LeetCode rješenje

Poravnajte binarno stablo na povezani popis LeetCode rješenje

Python rješenje:

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

Java rješenje:

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

Vremenska složenost: O(N)

Složenost prostora: O (1)

Kako smo prošli samo jednom, složenost vremena bit će o(n).

a kako nismo uzeli nikakav dodatni prostor, složenost prostora bit će o(1) konstantni dodatni prostor.

Slično pitanje - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Umetanje Izbriši GetRandom O(1) Leetcode Rješenje

Iskaz problema Rješenje Insert Delete GetRandom O(1) LeetCode – “Insert Delete GetRandom O(1)” traži od vas da implementirate ove četiri funkcije u O(1) vremenskoj složenosti. insert(val): Umetnite val u randomizirani skup i vratite true ako je element u početku odsutan u skupu. Vraća se false kada…

Čitaj više

Neparni Parni povezani popis Leetcode Rješenje

Izjava problema Neparno-parni povezani popis LeetCode Rješenje – “Nepar-parni povezani popis” navodi da je zadan neprazan jednostruko povezan popis. Moramo grupirati sve čvorove s neparnim indeksima zajedno, a zatim čvorove s parnim indeksima i vratiti ponovno uređeni popis. Imajte na umu da je relativni poredak unutar oba …

Čitaj više

Dodaj dva broja II Leetcode rješenje

Izjava problema Rješenje LeetCode Add Two Numbers II – “Add Two Numbers II” navodi da dvije neprazne povezane liste predstavljaju dva nenegativna cijela broja gdje je najznačajnija znamenka prva i svaki čvor sadrži točno jednu znamenku. Trebamo zbrojiti dva broja i vratiti zbroj kao…

Čitaj više

Dizajnirajte Leetcode rješenje

Izjava problema Dizajn Leaderboard LeetCode Rješenje – “Dizajn ploče s najboljim rezultatima” traži od vas da ispunite 3 funkcije: addScore(playerId, score): Ažurirajte ploču s najboljim dodavanjem rezultata na rezultat danog igrača. Ako ne postoji igrač, dodajte takav ID na ploču s najboljim rezultatima. top(K): Vrati najveći zbroj …

Čitaj više

Podijelite dva cijela broja Leetcode Rješenje

Izjava problema Podijeli dva cijela broja Rješenje LeetCode – “Podijeli dva cijela broja” navodi da su vam dana dva cijela broja dividenda i djelitelj. Vratite kvocijent nakon dijeljenja dividende s djeliteljem. Imajte na umu da pretpostavljamo da imamo posla s okruženjem koje može pohraniti cijele brojeve unutar 32-bitnog cijelog broja s predznakom...

Čitaj više

K-ti faktor rješenja n Leetcode

Izjava problema K-ti faktor od n Leetcode Rješenje: navodi da su vam dana dva pozitivna cijela broja n i k. Faktor cijelog broja n definiran je kao cijeli broj i gdje je n % i == 0. Razmotrite popis svih faktora od n sortiranih uzlaznim redoslijedom, vratite k-ti faktor na ovom popisu ili vratite -1 ako n ima manje od k čimbenici. Primjer 1: Unos: …

Čitaj više

Dnevne temperature Leetcode Rješenje

Izjava problema Dnevne temperature Leetcode Rješenje: navodi da niz cijelih brojeva temperatura predstavlja dnevne temperature, vratite odgovor niza tako da je answer[i] broj dana koje morate čekati nakon i-tog dana da dobijete topliju temperaturu. Ako ne postoji budući dan za koji je to moguće, umjesto toga zadržite answer[i] == 0. …

Čitaj više

Translate »