Najděte vítěze kruhové hry řešení LeetCode

Problémové prohlášení Najděte vítěze kruhové hry Řešení LeetCode – Existuje n přátel, kteří hrají hru. Přátelé sedí v kruhu a jsou očíslováni od 1 do n ve směru hodinových ručiček. Formálněji, pohybem ve směru hodinových ručiček od i. přítele se dostanete do…

Dozvědět se více

Binární strom Inorder Traversal řešení LeetCode

Příkaz problému: Binary Tree Inorder Traversal LeetCode solution Daný kořen binárního stromu vraťte inorder traversal hodnot jeho uzlů. Příklad 1: Vstup: root = [1,null,2,3] Výstup: [1,3,2] Příklad 2: Vstup: root = [] Výstup: [] Příklad 3: Vstup: root = [1] Výstup: [1] Omezení: Počet uzlů v …

Dozvědět se více

Minimální součet cesty Leetcode řešení

Prohlášení o problému The Minimum Path Sum LeetCode Solution – „Minimum Path Sum“ říká, že daná anxm mřížka se skládá z nezáporných celých čísel a my potřebujeme najít cestu zleva shora dolů, která minimalizuje součet všech čísel na cestě. . Můžeme se jen pohybovat…

Dozvědět se více

Minimální náklady na lezení po schodech Řešení LeetCode

Prohlášení o problému Minimální náklady na lezení po schodech Řešení LeetCode – Je uvedena cena celého pole, kde cost[i] je cena i-tého kroku na schodišti. Jakmile zaplatíte náklady, můžete vystoupat jeden nebo dva schody. Můžete začít buď od kroku s indexem 0, nebo od kroku s…

Dozvědět se více

Srovnat binární strom do propojeného seznamu řešení LeetCode

Srovnat binární strom do propojeného seznamu řešení LeetCode říká, že – Vzhledem k root binárního stromu, srovnejte strom do „propojeného seznamu“:

  • „Propojený seznam“ by měl používat totéž TreeNode třída, kde right podřízený ukazatel ukazuje na další uzel v seznamu a left dětský ukazatel je vždy null.
  • „Propojený seznam“ by měl být ve stejném pořadí jako a pre-order traverz binárního stromu.

 

Příklad 1:

Srovnat binární strom do propojeného seznamu řešení LeetCodeVstup:

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

Výstup:

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

Příklad 2:

Vstup:

 root = []

Výstup:

 []

Příklad 3:

Vstup:

 root = [0]

Výstup:

 [0]

 

ALGORITHM –

IDEA -

  • Abychom binární strom srovnali, nejprve najdeme prvek levého podstromu nejvíce vpravo a poté, co získáme prvek nejvíce vpravo, spojíme pravý ukazatel tohoto uzlu s pravým podstromem daného stromu.
  • V kroku 2 propojíme pravý ukazatel kořenového uzlu s levým podstromem a levý podstrom nastavíme jako null.
  • V kroku 3 je nyní náš kořenový uzel uzlem pravého podstromu stejný proces se stane s tímto uzlem a proces bude stále pokračovat, dokud se všechny levé části nestanou nulovými.

Přístup pro Flatten Binary Tree to Linked List Leetcode Solution –

– Nejprve spustím smyčku, tj. while(root != null), poté vezmu dvě proměnné a uložím levý podstrom.

– poté zkontroluje kontrolu pravého uzlu levého podstromu pomocí while(k.left != null) a propojí tento uzel s pravým podstromem pomocí (k.right = root.right).

– poté propojte pravý ukazatel kořenového uzlu s levým podstromem (root.right = left) a nastavte levý ukazatel kořenového uzlu jako null (root.left=null) a aktualizuje se o ( root = root.right ), takže nyní je root pravý uzel podstromu.

– tento proces bude pokračovat, dokud se všechny části levého podstromu nestanou pravým podstromem. Binární strom se tedy zplošťuje.

 

Srovnat binární strom do propojeného seznamu řešení LeetCode

Srovnat binární strom do propojeného seznamu řešení LeetCode

Řešení 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 řešení:

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á složitost: O(N)

Složitost prostoru: O (1)

Protože jsme prošli pouze jednou, časová složitost bude o(n).

a protože jsme nevzali žádný prostor navíc, složitost prostoru bude o (1) konstantní prostor navíc.

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

Vložit Delete GetRandom O(1) Leetcode Solution

Prohlášení o problému Řešení LeetCode Insert Delete GetRandom O(1) – „Insert Delete GetRandom O(1)“ vás žádá o implementaci těchto čtyř funkcí v časové složitosti O(1). insert(val): Vloží hodnotu do randomizované sady a vrátí hodnotu true, pokud prvek v sadě původně chybí. Vrací false, když…

Dozvědět se více

Řešení LRU Cache Leetcode

Prohlášení o problému Řešení LRU Cache LeetCode – „LRU Cache“ vás žádá o návrh datové struktury, která se řídí mezipamětí nejméně nedávno použitých (LRU) Potřebujeme implementovat třídu LRUCache, která má následující funkce: LRUCache(int capacity): Inicializuje mezipaměť LRU s kladnou velikostní kapacitou. int get (klíč int): Vrátí hodnotu …

Dozvědět se více

Minimální odstranění, aby byly závorky platné řešení LeetCode

Prohlášení o problému Minimální odstranění, aby byly závorky platné Řešení LeetCode – Je vám přidělen řetězec '(', ')' a malá písmena v angličtině. Vaším úkolem je odstranit minimální počet závorek ( '(' nebo ')', na libovolné pozici), aby výsledný řetězec závorek byl …

Dozvědět se více

Nejdelší podřetězec bez opakujících se znaků Řešení Leetcode

Problémové prohlášení Nejdelší podřetězec bez opakujících se znaků Řešení LeetCode – uvádí, že daný řetězec s. Musíme najít nejdelší podřetězec bez opakování znaků. Příklad: Vstup: s = ”abcabcbb” Výstup: 3 Vysvětlení: Nejdelší podřetězec bez opakujících se znaků má délku 3. Řetězec je: “abc”. Vstup: s = "bbbbb" …

Dozvědět se více

Řešení Fibonacciho čísla LeetCode

Problémové prohlášení Fibonacciho číslo LeetCode Solution – „Fibonacciho číslo“ uvádí, že Fibonacciho čísla, běžně označovaná F(n) tvoří posloupnost, nazývanou Fibonacciho posloupnost, takže každé číslo je součtem dvou předchozích, počínaje 0 a 1 To znamená, že F(0) = 0, F(1) = 1 F(n) = F(n – 1) + F(n …

Dozvědět se více

Translate »