Адзнака рашэння LeetCode у дужках

Пастаноўка праблемы Ацэнка дужкі LeetCode Solution кажа – Улічваючы збалансаваны радок у дужках і вяртанне максімальнага бала. Ацэнка збалансаванага радка ў дужках грунтуецца на наступных правілах: «()» мае 1 бал. AB мае адзнаку A + B, дзе A і B з'яўляюцца збалансаванымі радкамі ў дужках. (A) мае 2 * A, дзе A - гэта ...

больш падрабязна

Двайковае дрэва Inorder Traversal LeetCode Рашэнне

Пастаноўка праблемы: абход двайковага дрэва па парадку. Рашэнне LeetCode Улічваючы корань двайковага дрэва, вярніце абход значэнняў яго вузлоў у парадку. Прыклад 1: Увод: root = [1,null,2,3] Выхад: [1,3,2] Прыклад 2: Увод: root = [] Выхад: [] Прыклад 3: Увод: root = [1] Выхад: [1] Абмежаванні: колькасць вузлоў у ...

больш падрабязна

Рашэнне расшыфроўкі радка Leetcode

Пастаноўка праблемы Рашэнне Decode String LeetCode - «Decode String» просіць вас пераўтварыць закадаваную радок у дэкадаваную радок. Правілам кадавання з'яўляецца k[encoded_string], дзе encoded_string у квадратных дужках паўтараецца роўна k разоў, дзе k - дадатнае цэлае лік. Прыклад: Увод: s = ”3[a]2[bc]” Выхад: “aaabcbc” ...

больш падрабязна

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution кажа, што – Улічваючы root двайковага дрэва, зраўняйце дрэва ў «звязаны спіс»:

  • «Звязаны спіс» павінен выкарыстоўваць тое ж самае TreeNode клас, дзе right даччыны паказальнік паказвае на наступны вузел у спісе і left даччыны паказальнік заўсёды null.
  • «Звязаны спіс» павінен быць у тым жа парадку, што і a Папярэдні заказ абход бінарнага дрэва.

 

Прыклад 1:

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode SolutionУваход:

 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]

 

АЛГАРЫТМ -

ІДЭЯ -

  • Каб зраўнаваць двайковае дрэва, мы спачатку знойдзем крайні правы элемент левага паддрэва, а пасля таго, як атрымаем самы правы элемент, звяжам правы паказальнік гэтага вузла з правым паддрэвам дадзенага дрэва.
  • На этапе 2 мы звяжам правы паказальнік каранёвага вузла з левым паддрэвам і ўсталюем левае паддрэва як нуль.
  • На этапе 3 наш каранёвы вузел з'яўляецца вузлом правага паддрэва. Такі ж працэс будзе адбывацца і з гэтым вузлом, і працэс будзе працягвацца, пакуль усе левыя часткі не стануць нулевымі.

Падыход да выраўноўвання двайковага дрэва ў звязаны спіс рашэння Leetcode -

– Спачатку я запускаю цыкл, г.зн. while(root != null), затым возьму дзве зменныя і захаваю левае паддрэва.

– затым правярае праверку крайняга правага вузла левага паддрэва з дапамогай while(k.left != null) і звязвае гэты вузел з правым паддрэвам, выкарыстоўваючы (k.right = root.right).

– затым звязаць правы паказальнік каранёвага вузла з левым паддрэвам (root.right = left) і ўсталяваць левы паказальнік каранёвага вузла як null(root.left=null) і будзе абнаўляцца на ( root = root.right ), так што цяпер корань правы вузел паддрэва.

– гэты працэс будзе працягвацца да таго часу, пакуль усе часткі левага паддрэва не стануць правым паддрэвам. Такім чынам, двайковае дрэва будзе сплюшчаным.

 

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution

Рашэнне 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:

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

Дадаць два лічбы II Leetcode Рашэнне

Пастаноўка задачы. Рашэнне LeetCode Add Two Numbers II – «Дадаць два лічбы II» сцвярджае, што два непустыя звязаныя спісы ўяўляюць сабой два неадмоўныя цэлыя лічбы, дзе найбольш значная лічба ідзе першай, і кожны вузел змяшчае роўна адну лічбу. Нам трэба скласці дзве лічбы і вярнуць суму як ...

больш падрабязна

Сутачная тэмпература Leetcode Solution

Пастаноўка праблемы Літкод па сутачных тэмпературах: сцвярджае, што дадзены масіў цэлых лікаў тэмператур прадстаўляе дзённыя тэмпературы, вяртайце адказ масіва такім чынам, што answer[i] - гэта колькасць дзён, якія вы павінны чакаць пасля i-га дня, каб атрымаць больш цёплую тэмпературу. Калі няма наступнага дня, на які гэта магчыма, трымайце answer[i] == 0 замест гэтага. …

больш падрабязна

Мінімальнае выдаленне, каб зрабіць правільныя дужкі LeetCode Solution

Пастаноўка праблемы Мінімальнае выдаленне, каб зрабіць сапраўдныя дужкі Рашэнне LeetCode – Вам даецца радок з '(', ')' і малыя англійскія сімвалы. Ваша задача - выдаліць мінімальную колькасць дужак ( '(' або ')', у любых пазіцыях), каб выніковы радок дужак быў ...

больш падрабязна

Рашэнне для захопу дажджавой вады Leetcode

Пастаноўка праблемы Рашэнне LeetCode для ўлоўлівання дажджавой вады – «Улоў дажджавой вады» сцвярджае, што дадзены масіў вышынь, які прадстаўляе карту вышынь, дзе шырыня кожнага палоска роўная 1. Нам трэба знайсці колькасць вады, якая засталася пасля дажджу. Прыклад: Увод: вышыня = [0,1,0,2,1,0,1,3,2,1,2,1] Выхад: 6 Тлумачэнне: Праверце ...

больш падрабязна

Дапушчальныя дужкі Рашэнне Leetcode

Пастаноўка праблемы Дапушчальныя дужкі Рашэнне LeetCode – «Дзейнічаючыя дужкі» сцвярджаюць, што вам дадзены радок, які змяшчае толькі сімвалы '(', ')', '{', '}', '[' і ']'. Нам трэба вызначыць, ці з'яўляецца ўваходны радок сапраўднай радком ці не. Радок называецца сапраўдным радком, калі адкрытыя дужкі павінны быць зачыненыя ...

больш падрабязна

Рашэнне Leetcode для стэка максімальнай частоты

Пастаноўка праблемы Рашэнне LeetCode для стэка максімальнай частоты - «Стэк максімальнай частоты» прапануе вам распрацаваць стэк частот, у якім кожны раз, калі мы выцягваем элемент са стэка, ён павінен вяртаць найбольш часты элемент, які прысутнічае ў стэку. Рэалізаваць клас FreqStack: FreqStack() стварае пусты стэк частот. void push(int val) штурхае ...

больш падрабязна

Translate »