Skóre riešenia LeetCode v zátvorkách

Vyhlásenie o probléme Skóre riešenia Parenthesis LeetCode hovorí – Pri vyrovnaných zátvorkách reťazec s a vráti maximálne skóre. Skóre reťazca vyvážených zátvoriek je založené na nasledujúcich pravidlách: „()“ má skóre 1. AB má skóre A + B, kde A a B sú reťazce vyvážených zátvoriek. (A) má skóre 2 * A, kde A je …

Čítaj viac

Binárne Tree Inorder Traversal LeetCode riešenie

Problém: Binary Tree Inorder Traversal LeetCode riešenie Vzhľadom na koreň binárneho stromu vráťte inorder traversal hodnôt jeho uzlov. Príklad 1: Vstup: root = [1,null,2,3] Výstup: [1,3,2] Príklad 2: Vstup: root = [] Výstup: [] Príklad 3: Vstup: root = [1] Výstup: [1] Obmedzenia: Počet uzlov v…

Čítaj viac

Riešenie Decode String Leetcode

Vyhlásenie o probléme The Decode String LeetCode Solution – „Decode String“ vás žiada, aby ste skonvertovali zakódovaný reťazec na dekódovaný reťazec. Kódovacie pravidlo je k[encoded_string], kde kódovaný_reťazec v hranatých zátvorkách sa opakuje presne k-krát, kde k je kladné celé číslo. Príklad: Vstup: s = ”3[a]2[bc]” Výstup: “aaabcbc” …

Čítaj viac

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode hovorí, že – Vzhľadom na root binárneho stromu, vyrovnajte strom do „prepojeného zoznamu“:

  • „Prepojený zoznam“ by mal používať to isté TreeNode trieda, kde right podriadený ukazovateľ ukazuje na nasledujúci uzol v zozname a left dieťa ukazovateľ je vždy null.
  • „Prepojený zoznam“ by mal byť v rovnakom poradí ako a pre-order priechod binárneho stromu.

 

Príklad 1:

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCodevstup:

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

Výkon:

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

Príklad 2:

vstup:

 root = []

Výkon:

 []

Príklad 3:

vstup:

 root = [0]

Výkon:

 [0]

 

ALGORITHM –

NÁPAD -

  • Aby sme sploštili binárny strom, najskôr nájdeme prvok ľavého podstromu úplne vpravo a potom, čo dostaneme prvok úplne vpravo, spojíme pravý ukazovateľ tohto uzla s pravým podstromom daného stromu.
  • V kroku 2 prepojíme pravý ukazovateľ koreňového uzla s ľavým podstromom a ľavý podstrom nastavíme na hodnotu null.
  • V kroku 3 je teraz náš koreňový uzol uzol pravého podstromu rovnaký proces sa stane s týmto uzlom a proces bude pokračovať, kým sa všetky ľavé časti nestanú nulovými.

Prístup k vyrovnávaniu binárneho stromu k riešeniu prepojeného zoznamu Leetcode –

– Najprv spustím cyklus, tj while(root != null), potom vezmem dve premenné a uložím ľavý podstrom.

– potom pomocou while(k.left != null) skontroluje uzol ľavého podstromu úplne vpravo a pomocou (k.right = root.right) prepojí tento uzol s pravým podstromom.

– potom prepojte pravý ukazovateľ koreňového uzla s ľavým podstromom (root.right = vľavo) a nastavte ľavý ukazovateľ koreňového uzla ako null (root.left=null) a aktualizuje sa o ( root = root.right ), takže teraz má root pravdu uzol podstromu.

– tento proces bude pokračovať, kým sa všetky časti ľavého podstromu nestanú pravým podstromom. Preto sa binárny strom sploští.

 

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode

Vyrovnajte binárny strom do prepojeného zoznamu riešenia LeetCode

Riešenie 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

Java riešenie:

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

Časová zložitosť: O(N)

Zložitosť vesmíru: O (1)

Keďže sme prešli iba raz, časová zložitosť bude o(n).

a keďže sme nezobrali žiadny priestor navyše, zložitosť priestoru bude o (1) konštantný priestor navyše.

Podobná otázka - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Pridajte riešenie Leetcode dvoch čísel II

Vyhlásenie o probléme Riešenie LeetCode Add Two Numbers II – „Add Two Numbers II“ uvádza, že dva neprázdne spojené zoznamy predstavujú dve nezáporné celé čísla, kde najvýznamnejšia číslica je na prvom mieste a každý uzol obsahuje práve jednu číslicu. Potrebujeme sčítať dve čísla a vrátiť súčet ako ...

Čítaj viac

Denné teploty Riešenie Leetcode

Vyhlásenie o probléme The Daily Temperatures Leetcode Solution: uvádza, že dané pole celých teplôt predstavuje denné teploty, vráťte odpoveď poľa tak, že odpoveď[i] je počet dní, ktoré musíte čakať po tom dni, aby ste získali vyššiu teplotu. Ak neexistuje žiadny budúci deň, pre ktorý by to bolo možné, ponechajte namiesto toho odpoveď[i] == 0. …

Čítaj viac

Minimálne odstránenie, aby bolo riešenie LeetCode platné v zátvorkách

Vyhlásenie o probléme Minimálne odstránenie, aby boli zátvorky platné Riešenie LeetCode – Dostali ste reťazec s '(', ')' a malé anglické znaky. Vašou úlohou je odstrániť minimálny počet zátvoriek ( '(' alebo ')', na ľubovoľných pozíciách), aby výsledný reťazec zátvoriek bol …

Čítaj viac

Riešenie Leetcode na zachytávanie dažďovej vody

Vyhlásenie o probléme Riešenie LeetCode Trapping Rain Water – „Zachytenie dažďovej vody“ uvádza, že dané pole výšok, ktoré predstavuje výškovú mapu, kde šírka každého stĺpca je 1. Musíme nájsť množstvo vody zachytenej po daždi. Príklad: Vstup: výška = [0,1,0,2,1,0,1,3,2,1,2,1] Výstup: 6 Vysvetlenie: Skontrolujte …

Čítaj viac

Platné riešenie Leetcode so zátvorkami

Vyhlásenie o probléme Riešenie LeetCode s platnými zátvorkami – „Platné zátvorky“ uvádza, že ste dostali reťazec obsahujúci iba znaky '(', ')', '{', '}', '[' a ']'. Musíme určiť, či je vstupný reťazec platným reťazcom alebo nie. Reťazec sa považuje za platný reťazec, ak musia byť otvorené zátvorky uzavreté ...

Čítaj viac

Riešenie Leetcode na stohovanie maximálnej frekvencie

Vyhlásenie o probléme Zásobník maximálnej frekvencie Riešenie LeetCode – „Zásobník maximálnej frekvencie“ vás žiada, aby ste navrhli frekvenčný zásobník, v ktorom vždy, keď vyberieme prvok zo zásobníka, mal by vrátiť najčastejší prvok prítomný v zásobníku. Implementujte triedu FreqStack: FreqStack() vytvorí prázdny frekvenčný zásobník. void push (int val) pushs…

Čítaj viac

Translate »