Skóre řešení LeetCode závorek

Problémové prohlášení Skóre Parenthesis LeetCode Solution říká – Při vyvážených závorkách řetězec s a vrátí maximální skóre. Skóre řetězce vyvážených závorek je založeno na následujících pravidlech: „()“ má skóre 1. AB má skóre A + B, kde A a B jsou řetězce vyvážených závorek. (A) má skóre 2 * A, kde A je …

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

Řešení Decode String Leetcode

Prohlášení o problému The Decode String LeetCode Solution – „Decode String“ vás požádá o převod zakódovaného řetězce na dekódovaný řetězec. Kódovací pravidlo je k[encoded_string], kde kódovaný_řetězec uvnitř hranatých závorek se opakuje přesně kkrát, kde k je kladné celé číslo. Příklad: Vstup: s = ”3[a]2[bc]” Výstup: “aaabcbc” …

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

Přidejte řešení Leetcode Two Numbers II

Prohlášení o problému Řešení LeetCode Add Two Numbers II – „Add Two Numbers II“ uvádí, že dva neprázdné spojené seznamy představují dvě nezáporná celá čísla, kde nejvýznamnější číslice je na prvním místě a každý uzel obsahuje právě jednu číslici. Musíme sečíst dvě čísla a vrátit součet jako…

Dozvědět se více

Denní teploty Řešení Leetcode

Prohlášení o problému The Daily Temperatures Leetcode Solution: uvádí, že dané pole celočíselných teplot představuje denní teploty, vrátí odpověď pole tak, že odpověď[i] je počet dní, které musíte čekat po tém dni, abyste získali vyšší teplotu. Pokud neexistuje žádný budoucí den, pro který by to bylo možné, ponechte místo toho odpověď[i] == 0. …

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

Řešení Leetcode pro zachycení dešťové vody

Prohlášení o problému Řešení LeetCode Trapping Rain Water – „Zachycování dešťové vody“ uvádí, že dané pole výšek představuje výškovou mapu, kde šířka každého sloupce je 1. Musíme najít množství vody zachycené po dešti. Příklad: Vstup: výška = [0,1,0,2,1,0,1,3,2,1,2,1] Výstup: 6 Vysvětlení: Zkontrolujte …

Dozvědět se více

Platné řešení Leetcode se závorkami

Prohlášení o problému Platné závorky řešení LeetCode – „Platné závorky“ uvádí, že jste dostali řetězec obsahující pouze znaky '(', ')', '{', '}', '[' a ']'. Musíme určit, zda je vstupní řetězec platným řetězcem nebo ne. Řetězec je považován za platný řetězec, pokud musí být otevřené závorky uzavřeny…

Dozvědět se více

Řešení Leetcode pro maximální frekvenční zásobník

Prohlášení o problému The Maximum Frequency Stack LeetCode Solution – „Maximum Frequency Stack“ vás žádá, abyste navrhli frekvenční zásobník, ve kterém kdykoli vyjmeme prvek ze zásobníku, měl by vrátit nejčastější prvek přítomný v zásobníku. Implementujte třídu FreqStack: FreqStack() vytvoří prázdný zásobník frekvencí. void push (int val) pushs…

Dozvědět se více

Translate »