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

Rješenje za slaganje kovanica Leetcode

Izjava o problemu Raspored kovanica LeetCode Rješenje – “Uređenje kovanica” traži od vas da napravite stubište s ovim novčićima. Stubište se sastoji od k redova, pri čemu se i-ti red sastoji od točno i novčića. Posljednji red stubišta možda neće biti potpun. Za zadanu količinu novčića vratite…

Č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

LRU Cache Leetcode Rješenje

Izjava o problemu LRU Cache LeetCode Rješenje – “LRU Cache” traži od vas da dizajnirate strukturu podataka koja slijedi Least Recently Used (LRU) Cache Moramo implementirati klasu LRUCache koja ima sljedeće funkcije: LRUCache(int kapacitet): Inicijalizira LRU predmemoriju s kapacitetom pozitivne veličine. int get(int ključ): Vrati vrijednost...

Čitaj više

Minimalno uklanjanje za izradu valjanih zagrada LeetCode rješenje

Izjava o problemu Minimalno uklanjanje za izradu valjanih zagrada LeetCode Rješenje – Dobivate niz s '(', ')' i mala slova engleskog jezika. Vaš je zadatak ukloniti minimalni broj zagrada ( '(' ili ')', na bilo kojoj poziciji) tako da rezultirajući niz zagrada bude ...

Čitaj više

Najduži podniz bez ponavljanja znakova Leetcode Rješenje

Izjava problema Najduži podniz bez ponavljanja znakova LeetCode Rješenje – navodi da je s obzirom na niz s. Moramo pronaći najduži podniz bez ponavljanja znakova. Primjer: Ulaz: s = ”abcabcbb” Izlaz: 3 Objašnjenje: Najduži podniz bez ponavljanja znakova je duljine 3. Niz je: “abc”. Unos: s = ”bbbbb”…

Čitaj više

Clone Graph LeetCode Rješenje

Izjava problema Clone Graph LeetCode Rješenje – Dobivamo referencu čvora u povezanom neusmjerenom grafu i od nas se traži da vratimo duboku kopiju grafa. Duboka kopija je u osnovi klon gdje nijedan čvor prisutan u dubokoj kopiji ne bi trebao imati referencu...

Čitaj više

Važeće zagrade Leetcode Rješenje

Iskaz problema Rješenje valjanih zagrada LeetCode – “Važeće zagrade” navodi da ste dobili niz koji sadrži samo znakove '(', ')', '{', '}', '[' i ']'. Moramo utvrditi je li ulazni niz valjan ili ne. Za niz se kaže da je važeći niz ako se otvorene zagrade moraju zatvoriti...

Čitaj više

Prvi jedinstveni znak u rješenju String LeetCode

Iskaz problema Prvi jedinstveni znak u nizu LeetCode Rješenje – Zadan niz s, pronađite prvi znak koji se ne ponavlja u njemu i vratite njegov indeks. Ako ne postoji, vratite -1. Primjer testnog slučaja 1: Ulaz: s = “leetcode” Izlaz: 0 Testni slučaj 2: Ulaz: s = “aabb” Izlaz: -1 Objašnjenje …

Čitaj više

Translate »