Punteġġ ta 'Parentesi Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema Il-punteġġ ta 'Parentesi Soluzzjoni LeetCode jgħid – Minħabba string bilanċjat parentesi s u rritorna l-punteġġ massimu. Il-punteġġ ta 'sekwenza ta' parentesi bilanċjata hija bbażata fuq ir-regoli li ġejjin: "()" għandha punteġġ 1. AB għandha punteġġ A + B, fejn A u B huma kordi ta 'parentesi bilanċjati. (A) għandu punteġġ 2 * A, fejn A huwa ...

Aqra iktar

Binary Tree Inorder Traversal Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema: Binary Tree Inorder Traversal Soluzzjoni LeetCode Minħabba l-għerq ta 'siġra binarja, ritorna l-inorder traversal tal-valuri tan-nodi tagħha. Eżempju 1: Input: root = [1,null,2,3] Output: [1,3,2] Eżempju 2: Input: root = [] Output: [] Eżempju 3: Input: root = [1] Output: [1] Limitazzjonijiet: In-numru ta' nodi fi...

Aqra iktar

Iddekodifika String Leetcode Soluzzjoni

Dikjarazzjoni tal-Problema Is-Soluzzjoni ta' Decode String LeetCode - "Decode String" titlobek tikkonverti s-sekwenza kodifikata f'sekwenza dekodifikata. Ir-regola tal-kodifikazzjoni hija k[encoded_string], fejn is-encoded_string ġewwa l-parentesi kwadri qed tiġi ripetuta eżattament k darbiet fejn k huwa numru sħiħ pożittiv. Eżempju: Input: s = ”3[a]2[bc]” Output: “aaabcbc”…

Aqra iktar

Flatten Binary Tree to Linked List Soluzzjoni LeetCode

Flatten Binary Tree to Linked List Soluzzjoni LeetCode jgħid li – Minħabba l- root ta’ siġra binarja, iċċattja s-siġra f’“lista marbuta”:

  • Il-“lista marbuta” għandha tuża l-istess TreeNode klassi fejn il right il-punter tat-tifel jindika n-nodu li jmiss fil-lista u l- left punter tat-tfal huwa dejjem null.
  • Il-“lista konnessa” għandha tkun fl-istess ordni bħal a qabel l-ordni traversal tas-siġra binarja.

 

Eżempju 1:

Flatten Binary Tree to Linked List Soluzzjoni LeetCodeinput:

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

Riżultat:

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

Eżempju 2:

input:

 root = []

Riżultat:

 []

Eżempju 3:

input:

 root = [0]

Riżultat:

 [0]

 

ALGORITMU -

IDEA -

  • Sabiex iċċattjaw siġra binarja, l-ewwel se nsibu l-element l-aktar tal-lemin tas-subsiġra tax-xellug u wara li ksibna l-element l-aktar tal-lemin aħna se torbot il-punter tal-lemin ta 'dak in-node ma' subtree tal-lemin ta 'siġra partikolari.
  • Fil-pass 2 aħna se torbot il-pointer tal-lemin tan-nodu għerq mas-subtree tax-xellug u nissettjaw is-subtree tax-xellug bħala null.
  • Fil-pass 3 issa node għerq tagħna huwa node subtree dritt istess proċess se jiġri ma 'dan in-node u l-proċess xorta se jkompli sakemm il-partijiet tax-xellug kollha jsiru nulli.

Approċċ għal Flatten Binary Tree to Linked List Soluzzjoni Leetcode -

– Għall-ewwel, i se tmexxi loop jiġifieri filwaqt (għerq != null) imbagħad se tieħu żewġ varjabbli u jaħżen is-subtree tax-xellug.

– imbagħad se tiċċekkja għan-node l-aktar tal-lemin tas-subtree tax-xellug billi tuża while(k.left != null) u se torbot dak in-node mas-subtree tal-lemin billi tuża (k.right = root.right).

– imbagħad għaqqad il-pointer tal-lemin tan-node tal-għeruq ma’ subtree tax-xellug (għerq.right = xellug) u ssettja l-pointer tax-xellug tan-nodu tal-għerq bħala null(għerq.xellug=null) u se taġġorna minn (għerq = għerq.lemin) għalhekk issa l-għerq huwa dritt subtree node.

– dan il-proċess se jkompli sakemm il-partijiet kollha tas-subtree tax-xellug isiru subtree tal-lemin. Għalhekk, is-siġra binarja se tiċċattja.

 

Flatten Binary Tree to Linked List Soluzzjoni LeetCode

Flatten Binary Tree to Linked List Soluzzjoni LeetCode

Soluzzjoni 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

Soluzzjoni Java:

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

Il-kumplessità tal-ħin: O(N)

Kumplessità Spazjali: O (1)

Peress li għaddejna darba biss, il-kumplessità tal-ħin se tkun o(n).

u peress li aħna ma ħadu ebda spazju żejjed, il-kumplessità tal-ispazju se tkun o(1) spazju żejjed kostanti.

Mistoqsija Simili - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Żid Żewġ Numri II Leetcode Soluzzjoni

Dikjarazzjoni tal-Problema Is-Soluzzjoni LeetCode Żid Żewġ Numri II - "Żid Żewġ Numri II" tiddikjara li żewġ listi konnessi mhux vojta jirrappreżentaw żewġ interi mhux negattivi fejn l-aktar ċifra sinifikanti tiġi l-ewwel u kull nodu fih eżattament ċifra waħda. Irridu nżidu ż-żewġ numri u nirritornaw is-somma bħala...

Aqra iktar

Temperaturi ta 'Kuljum Soluzzjoni Leetcode

Dikjarazzjoni tal-Problema Is-Soluzzjoni Leetcode tat-Temperaturi ta 'Kuljum: tiddikjara li minħabba firxa ta' temperaturi interi tirrappreżenta t-temperaturi ta 'kuljum, ritorna tweġiba ta' firxa b'tali mod li t-tweġiba[i] tkun in-numru ta 'ġranet li trid tistenna wara l-ith jum biex tikseb temperatura aktar sħuna. Jekk ma jkunx hemm jum futur li għalih dan huwa possibbli, żomm tweġiba[i] == 0 minflok. …

Aqra iktar

Minimu Neħħi biex tagħmel Parentesi Validu Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema Il-Neħħi Minimu biex Tagħmel Parentesi Validu Soluzzjoni LeetCode – Inti tingħata string s ta ''(', ')' u karattri Ingliżi żgħar. Il-kompitu tiegħek huwa li tneħħi n-numru minimu ta' parentesi ("(' jew ')', fi kwalunkwe pożizzjoni) sabiex is-sekwenza tal-parentesi li tirriżulta tkun...

Aqra iktar

Soluzzjoni Leetcode tal-Insib tal-Ilma tax-Xita

Dikjarazzjoni tal-Problema Is-Soluzzjoni ta 'Trapping Rain Water LeetCode - "Trapping Rain Water" tiddikjara li minħabba firxa ta' għoli li tirrappreżenta mappa ta 'elevazzjoni fejn il-wisa' ta 'kull bar hija 1. Għandna bżonn insibu l-ammont ta' ilma maqbud wara x-xita. Eżempju: Input: għoli = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Spjegazzjoni: Iċċekkja...

Aqra iktar

Parentesi Validu Soluzzjoni Leetcode

Dikjarazzjoni tal-Problema Is-Soluzzjoni LeetCode tal-Parentesi Validi – “Parentesi Validi” tgħid li qed tingħata string li fiha biss il-karattri '(', ')', '{', '}', '[' u ']'. Għandna bżonn niddeterminaw jekk is-sekwenza tad-dħul hijiex sekwenza valida jew le. Spag jingħad li huwa spag validu jekk il-parentesi miftuħa jridu jingħalqu...

Aqra iktar

Soluzzjoni ta' Leetcode Stack ta' Frekwenza Massima

Dikjarazzjoni tal-Problema Is-Soluzzjoni ta 'LeetCode tal-Munzell ta' Frekwenza Massima - "Munzell ta 'Frekwenza Massima" titlobek biex tiddisinja munzell ta' frekwenza li fiha kull meta npoġġu element mill-munzell, għandu jirritorna l-aktar element frekwenti preżenti fil-munzell. Implimenta l-klassi FreqStack: FreqStack() tibni munzell ta 'frekwenza vojta. void push(int val) pushes...

Aqra iktar

Translate »