ንዑስ ደሴቶች LeetCode መፍትሄ ይቁጠሩ

የችግር መግለጫ ብዛት ንዑስ ደሴቶች LeetCode Solution ይላል ግሪድ1 እና ግሪድ2 0 ብቻ (ውሃ የሚወክል) እና 1 (መሬትን የሚወክል) ይይዛሉ። ደሴቱ ማለት የ 1 ዎቹ ቡድን 4 በአቅጣጫ የተገናኘ ማለት ነው. በፍርግርግ 2 ውስጥ ያለ ደሴት በፍርግርግ 1 ውስጥ ሁሉንም የሚሰሩ ሴሎችን የያዘ ደሴት ካለ እንደ ንዑስ ደሴት ይቆጠራል።

ተጨማሪ ያንብቡ

የሁለትዮሽ ዛፍ LeetCode መፍትሄ አቀባዊ ቅደም ተከተል መሻገር

የችግር መግለጫ አቀባዊ ቅደም ተከተል የሁለትዮሽ ዛፍን መሻገር LeetCode መፍትሄ ይላል - የሁለትዮሽ ዛፍ ሥር ከተሰጠ ፣ የሁለትዮሽ ዛፍን ቀጥ ያለ ቅደም ተከተል አስላ። ለእያንዳንዱ መስቀለኛ መንገድ (ረድፍ ፣ ኮል) ፣ ግራ እና ቀኝ ልጆቹ በቦታዎች (ረድፍ + 1 ፣ ኮላ - 1) እና (ረድፍ + 1 ፣ ኮል + 1) በቅደም ተከተል ይሆናሉ። …

ተጨማሪ ያንብቡ

ድምር ስርወ ወደ ቅጠል ቁጥሮች LeetCode መፍትሄ

የችግር መግለጫ ድምር ስርወ ወደ ቅጠል ቁጥሮች LeetCode መፍትሄ እንዲህ ይላል - ከ 0 እስከ 9 አሃዞችን ብቻ የያዘ የሁለትዮሽ ዛፍ ስር ይሰጥዎታል። በዛፉ ውስጥ ያለው እያንዳንዱ ሥር-ወደ-ቅጠል መንገድ ቁጥርን ይወክላል. ለምሳሌ ከስር-ወደ-ቅጠል መንገድ 1 -> 2 -> 3 ቁጥርን ይወክላል 123. የሁሉም ስር-ወደ-ቅጠል ቁጥሮች ድምርን ይመልሱ። ሙከራ…

ተጨማሪ ያንብቡ

ሁለትዮሽ ዛፍ Inorder Traversal LeetCode መፍትሔ

የችግር መግለጫ፡- የሁለትዮሽ ዛፍ ቅደም ተከተል መሻገሪያ የሊትኮድ መፍትሄ የሁለትዮሽ ዛፍ ሥር ከተሰጠን፣ የአንጓዎቹን እሴቶቹን ቅደም ተከተል መተላለፍን ይመልሱ። ምሳሌ 1፡ ግብዓት፡ ስርወ = [1,null,2,3] ውጤት፡ [1,3,2፣2፣3] ምሳሌ 1፡ ግቤት፡ ስር = [] ውጤት፡ [] ምሳሌ 1፡ ግቤት፡ ስር = [XNUMX] ውጤት፡ [XNUMX] ገደቦች፡ በ ውስጥ ያሉት የአንጓዎች ብዛት…

ተጨማሪ ያንብቡ

ግራፍ Bipartite ነው? LeetCode መፍትሔ

የችግር መግለጫ ግራፍ ቢፓርት ሊትኮድ መፍትሄ ነው- n ኖዶች ያለው ያልተመራ ግራፍ አለ፣ እያንዳንዱ መስቀለኛ መንገድ በ 0 እና n መካከል የተቆጠረበት - 1. ባለ 2D ድርድር ግራፍ ይሰጥዎታል፣ ግራፍ[u] መስቀለኛ መንገድ የሆነ የአንጓዎች ድርድር ነው። አጠገብ ነው. በይበልጥ፣ በግራፍ[u] ውስጥ ላለው እያንዳንዱ v፣ በኖድ u እና node v መካከል ያልተመራ ጠርዝ አለ። ግራፉ አለው…

ተጨማሪ ያንብቡ

የቃላት አክል እና ፈልግ የውሂብ መዋቅር LeetCode መፍትሔ

የችግር መግለጫ፡ የንድፍ አክል እና ቃላትን ፈልግ የውሂብ መዋቅር LeetCode Solution ይላል - አዲስ ቃላትን መጨመር እና ሕብረቁምፊው ከዚህ ቀደም ከተጨመረው ሕብረቁምፊ ጋር የሚዛመድ መሆኑን ለማወቅ የሚያስችል የውሂብ መዋቅር ይንደፉ። የዎርድዲክሽነሪ ክፍልን ይተግብሩ፡ WordDictionary() ነገሩን ያስጀምራል። void addWord(ቃል) በመረጃ አወቃቀሩ ላይ ቃልን ይጨምራል፣ በኋላ ሊዛመድ ይችላል። ቡል ፍለጋ(ቃል) ካለ እውነት ይመለሳል…

ተጨማሪ ያንብቡ

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ ይላል - የተሰጠው root የሁለትዮሽ ዛፍ ፣ ዛፉን ወደ “የተገናኘ ዝርዝር” ጠፍጣፋ ያድርጉት።

  • "የተገናኘው ዝርዝር" ተመሳሳይ መጠቀም አለበት TreeNode ክፍል የት right የህጻን ጠቋሚ በዝርዝሩ ውስጥ ወደሚቀጥለው መስቀለኛ መንገድ እና የ left የልጅ ጠቋሚ ሁልጊዜ ነው null.
  • "የተገናኘው ዝርዝር" በተመሳሳይ ቅደም ተከተል መሆን አለበት ሀ የቅድሚያ ትእዛዝ መተላለፍ የሁለትዮሽ ዛፍ.

 

ምሳሌ 1:

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄግቤት

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

ውጤት

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

ምሳሌ 2:

ግቤት

 root = []

ውጤት

 []

ምሳሌ 3:

ግቤት

 root = [0]

ውጤት

 [0]

 

አልጎሪዝም -

IDEA -

  • ሁለትዮሽ ዛፍን ለማንጠፍለቅ በመጀመሪያ የግራውን ንዑስ ዛፍ ትክክለኛውን አካል እናገኛለን እና ትክክለኛውን ንጥረ ነገር ካገኘን በኋላ የዚያን መስቀለኛ መንገድ የቀኝ ጠቋሚን ከተሰጠ የዛፍ ቀኝ ንዑስ ዛፍ ጋር እናገናኘዋለን።
  • ደረጃ 2 ላይ የስር መስቀለኛ መንገድ የቀኝ ጠቋሚን ከግራ-ንዑስ ዛፍ ጋር እናገናኘዋለን እና የግራ-ንዑስ ዛፍ ባዶ እናስቀምጣለን።
  • በደረጃ 3 ላይ አሁን የእኛ ስርወ ኖድ የቀኝ-ንዑስ መስቀለኛ መንገድ ነው ተመሳሳይ ሂደት በዚህ መስቀለኛ መንገድ ይከሰታል እና ሁሉም የግራ ክፍሎች ባዶ እስኪሆኑ ድረስ ሂደቱ ይቀጥላል።

የጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር Leetcode መፍትሄ ጋር አቀራረብ -

- መጀመሪያ ላይ አንድ loop እሮጣለሁ (ሥር ! = null) ከዚያ ሁለት ተለዋዋጮችን ወስጄ የግራ-ንዑስ ዛፍን አከማችታለሁ።

- ከዚያም (k.left != null) በመጠቀም በቀኝ በኩል ያለውን የግራ-ንዑስ ዛፍ ኖድ ይፈትሹ እና ያንን መስቀለኛ መንገድ ከቀኝ ንዑስ ዛፍ ጋር ያገናኘዋል (k.right = root.right)።

- በመቀጠል የቀኝ ጠቋሚውን የስር ኖድ በግራ ንዑስ ዛፍ (root.right = ግራ) ያገናኙ እና የግራ ጠቋሚውን ባዶ (root.left=null) አድርገው ያስቀምጡ እና በ ( root = root.right ) ይሻሻላል ስለዚህ አሁን ስርወ ትክክል ነው የከርሰ ምድር መስቀለኛ መንገድ.

- ሁሉም የግራ-ንዑስ ክፍሎች ትክክለኛ ንዑስ ክፍል እስኪሆኑ ድረስ ይህ ሂደት ይቀጥላል። ስለዚህ, የሁለትዮሽ ዛፉ ጠፍጣፋ ይሆናል.

 

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ

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

የጃቫ መፍትሄ፡-

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

የጊዜ ውስብስብነት፡ O(N)

የቦታ ውስብስብነት: - O (1)

አንድ ጊዜ ብቻ እንደተጓዝን፣ የጊዜ ውስብስብነት o(n) ይሆናል።

እና ምንም ተጨማሪ ቦታ ስላልወሰድን የቦታ ውስብስብነት o(1) የማያቋርጥ ተጨማሪ ቦታ ይሆናል።

ተመሳሳይ ጥያቄ- https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

የ N-Ary Tree LeetCode መፍትሄ ዲያሜትር

የችግር መግለጫ የ N-Ary Tree LeetCode መፍትሄ ዲያሜትር - የ N-ary ዛፍ ሥር ከተሰጠው በኋላ የዛፉን ዲያሜትር ርዝመት ማስላት ያስፈልግዎታል. የ N-ary ዛፍ ዲያሜትር በዛፉ ውስጥ ባሉ ሁለት አንጓዎች መካከል ያለው ረጅሙ መንገድ ርዝመት ነው። ይህ መንገድ ሊሆንም ላይሆንም ይችላል…

ተጨማሪ ያንብቡ

የሁለትዮሽ ዛፍ Leetcode መፍትሄ ዝቅተኛው የጋራ ቅድመ አያት።

የችግር መግለጫ የሁለትዮሽ ዛፍ ሌትኮድ መፍትሄ ዝቅተኛው የጋራ ቅድመ አያት - "የሁለትዮሽ ዛፍ ዝቅተኛው የጋራ ቅድመ አያት" የሚለው የሁለትዮሽ ዛፍ ሥር እና የዛፉን ሁለት አንጓዎች እንደሰጠ ይናገራል። የእነዚህ ሁለት አንጓዎች ዝቅተኛውን የጋራ ቅድመ አያት ማግኘት አለብን. በጣም ዝቅተኛው የጋራ…

ተጨማሪ ያንብቡ

በእያንዳንዱ መስቀለኛ መንገድ Leetcode መፍትሄ ቀጣይ የቀኝ ጠቋሚዎችን ማብዛት።

የችግር መግለጫ በእያንዳንዱ መስቀለኛ መንገድ ላይ ያለው ቀጣይ የቀኝ ጠቋሚዎች ሊትኮድ መፍትሄ - "በእያንዳንዱ መስቀለኛ መንገድ ቀጣይ የቀኝ ጠቋሚዎችን ማብዛት" የሚለው የፍፁም የሁለትዮሽ ዛፍ ስር እንደ ሆነ እና እያንዳንዱን ቀጣይ የመስቀለኛ መንገድ ጠቋሚ ወደ ቀጣዩ የቀኝ መስቀለኛ መንገድ መሙላት አለብን። ቀጣይ ከሌለ…

ተጨማሪ ያንብቡ

Translate »