Stysta óflokkaða samfellda undirfylki LeetCode lausn

Vandamálsyfirlýsing Shortest Unsorted Continuous Subarray LeetCode Lausnin segir að - Gefið heiltölu fylki num, þú verður að finna eina samfellda undirfylki sem ef þú flokkar aðeins þessa undirfylki í hækkandi röð, þá verður allt fylkið raðað í hækkandi röð. Skilaðu lengd stystu undirfylkis. Dæmi 1: …

Lesa meira

Afkóða streng Leetcode lausn

Vandamálsyfirlýsing Afkóðastrengurinn LeetCode Lausnin – „Afkóðastrengur“ biður þig um að umbreyta kóðaða strengnum í afkóðaðan streng. Kóðunarreglan er k[kóðaður_strengur], þar sem kóðaði_strengurinn innan hornklofa er endurtekinn nákvæmlega k sinnum þar sem k er jákvæð heil tala. Dæmi: Inntak: s = ”3[a]2[bc]” Úttak: “aaabcbc” …

Lesa meira

Flettu tvöfalda tré við tengda lista LeetCode lausn

Flettu tvöfalda tré við tengda lista LeetCode lausn segir að - Í ljósi þess root af tvíundartré, flettu tréð út í „tengdan lista“:

  • „Tengdi listinn“ ætti að nota það sama TreeNode bekk þar sem right barnabendill bendir á næsta hnút á listanum og left barn bendill er alltaf null.
  • „Tengdi listinn“ ætti að vera í sömu röð og a Pre-röð yfirferð af tvíundartrénu.

 

Dæmi 1:

Flettu tvöfalda tré við tengda lista LeetCode lausninntak:

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

Output:

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

Dæmi 2:

inntak:

 root = []

Output:

 []

Dæmi 3:

inntak:

 root = [0]

Output:

 [0]

 

ALGÓRITIMA -

HUGMYND -

  • Til þess að fletja út tvöfalda tré, finnum við fyrst hægra megin í vinstra undirtrénu og eftir að við höfum náð hæsta stakinu munum við tengja hægri bendilinn þess hnúts við hægri undirtré tiltekins trés.
  • Í skrefi 2 munum við tengja hægri bendilinn á rótarhnútnum við vinstri undirtréð og stilla vinstri undirtréð sem núll.
  • Í skrefi 3 er nú rótarhnúturinn okkar hægri undirtréshnútur, sama ferli mun gerast með þessum hnút og ferlið heldur áfram þar til allir vinstri hlutar verða að engu.

Aðferð til að fletja tvöfalda tré við Leetcode lausn á tengdum lista -

– Í fyrstu mun ég keyra lykkju þ.e. while(rót != null) þá mun ég taka tvær breytur og geyma vinstri undirtréð.

– mun þá athuga hvort hnúturinn sé lengst til hægri í vinstri undirtré með því að nota while(k.left != null) og mun tengja þann hnút við hægri undirtré með því að nota (k.right = root.right).

– tengdu síðan hægri bendilinn á rótarhnút við vinstri undirtré (root.right = vinstri) og stilltu vinstri bendilinn á rótarhnút sem null(root.left=null) og mun uppfæra með (rót = root.right ) þannig að nú er rót rétt undirtré hnút.

– þetta ferli mun halda áfram þar til allir vinstri undirtré hlutar verða hægri undirtré. Þess vegna mun tvíundartréð fletjast út.

 

Flettu tvöfalda tré við tengda lista LeetCode lausn

Flettu tvöfalda tré við tengda lista LeetCode lausn

Python lausn:

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 lausn:

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

Tímaflæki: O(N)

Rýmisflókið: O (1)

Þar sem við höfum farið aðeins einu sinni yfir verður tímaflækjustigið o(n).

og þar sem við höfum ekki tekið neitt aukapláss verður flókið rými o(1) stöðugt aukarými.

Svipuð spurning - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Að raða mynt Leetcode lausn

Vandamálayfirlýsing LeetCode Lausnin – „Að raða mynt“ biður þig um að byggja stiga með þessum myntum. Stiginn samanstendur af k röðum, þar sem röðin samanstendur af nákvæmlega i mynt. Það getur verið að síðasta röð stigans sé ekki fullbúin. Fyrir uppgefið magn af myntum, skilaðu...

Lesa meira

Daglegt hitastig Leetcode lausn

Vandamálsskýring Dagleg hitastig Leetcode Lausn: segir að gefið fylki heiltalna hitastig táknar daglegt hitastig, skilaðu fylkissvari þannig að svar[i] er fjöldi daga sem þú þarft að bíða eftir ída degi til að fá hlýrra hitastig. Ef það er enginn framtíðardagur sem þetta er mögulegt fyrir skaltu halda svari[i] == 0 í staðinn. …

Lesa meira

LRU Cache Leetcode lausn

Vandamálsyfirlýsing LRU Cache LeetCode Lausnin – „LRU Cache“ biður þig um að hanna gagnaskipulag sem fylgir Least Recently Used (LRU) Cache Við þurfum að innleiða LRUCache flokk sem hefur eftirfarandi aðgerðir: LRUCache(int getu): Frumstillir LRU skyndiminni. með jákvæða stærðargetu. int get(int lykill): Skilaðu gildinu …

Lesa meira

Lágmarksfjarlægja til að gera gildar sviga LeetCode lausn

Vandamálsyfirlýsing Lágmarksfjarlægja til að gera gildan sviga LeetCode Lausn – Þú færð streng með '(', ')' og lágstöfum enskum stöfum. Verkefni þitt er að fjarlægja lágmarksfjölda sviga ( '(' eða ')', í hvaða stöðum sem er) þannig að svigastrengurinn sem myndast sé …

Lesa meira

Lengsti undirstrengur án þess að endurtaka stafi Leetcode lausn

Vandamálsyfirlýsing Lengsti undirstrengurinn án þess að endurtaka stafi LeetCode Lausn – segir að miðað við strenginn s. Við þurfum að finna lengsta undirstrenginn án þess að endurtaka stafi. Dæmi: Inntak: s = ”abcabcbb” Úttak: 3 Skýring: Lengsti undirstrengurinn þar sem engir stafir eru endurteknir er af lengd 3. Strengurinn er: “abc”. Inntak: s = ”bbbbb” …

Lesa meira

Klóna graf LeetCode lausn

Vandamálsyfirlýsing Klónagraf LeetCode Lausn – Okkur er gefið tilvísun í hnút í tengdu óstýrðu línuriti og erum beðin um að skila djúpu afriti af línuritinu. Djúpt afrit er í grundvallaratriðum klón þar sem enginn hnútur í djúpu afritinu ætti að hafa tilvísunina ...

Lesa meira

Gildir sviga Leetcode lausn

Vandamálsyfirlýsing Gildir sviga LeetCode Lausn – “Gildir sviga” segir að þú færð streng sem inniheldur bara stafina '(', ')', '{', '}', '[' og ']'. Við þurfum að ákvarða hvort inntaksstrengurinn sé gildur strengur eða ekki. Sagt er að strengur sé gildur strengur ef opnum sviga verður að loka …

Lesa meira

Translate »