Ең қысқа сұрыпталмаған үздіксіз бағыныңқы жиек LeetCode шешімі

Мәселе мәлімдемесі Ең қысқа сұрыпталмаған үздіксіз бағыныңқы жиым LeetCode Шешімі мынаны айтады: Бүтін массив сандары берілгенде, егер сіз тек осы ішкі жиымды тек өсу ретімен сұрыптасаңыз, онда бүкіл массив өсу ретімен сұрыпталатын бір үздіксіз ішкі жиымды табу керек. Ең қысқа ішкі жиымның ұзындығын қайтарыңыз. 1-мысал: …

Ары қарай оқу

Декодтау String Leetcode шешімі

Мәселе туралы мәлімдеме Decode String LeetCode шешімі – “Decode String” кодталған жолды декодталған жолға түрлендіруді сұрайды. Кодтау ережесі k[coded_string] болып табылады, мұнда төртбұрышты жақшалар ішіндегі кодталған_жол k рет қайталанады, мұнда k оң бүтін сан. Мысал: Кіріс: s = ”3[a]2[bc]” Шығыс: “aaabcbc” …

Ары қарай оқу

Екілік ағашты байланыстырылған тізімге тегістеңіз 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]

 

АЛГОРИТМ –

ИДЕЯ –

  • Екілік ағашты тегістеу үшін алдымен сол жақ ішкі ағаштың оң жақ элементін табамыз және ең оң жақ элементті алғаннан кейін сол түйіннің оң жақ көрсеткішін берілген ағаштың оң жақ ішкі ағашымен байланыстырамыз.
  • 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 шешімі

Екілік ағашты байланыстырылған тізімге тегістеңіз 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

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

Монеталарды ұйымдастыру Leetcode шешімі

Мәселе туралы мәлімдеме Монеталарды реттеу LeetCode шешімі – «Монеталарды реттеу» осы монеталар арқылы баспалдақ салуды сұрайды. Баспалдақ k қатардан тұрады, онда i-ші қатар дәл i тиындардан тұрады. Баспалдақтың соңғы қатары толық болмауы мүмкін. Берілген монета сомасы үшін қайтарыңыз ...

Ары қарай оқу

Күнделікті температуралар Leetcode шешімі

Мәселе туралы мәлімдеме Күнделікті температуралар Leetcode шешімі: берілген бүтін температуралар массиві тәуліктік температураларды көрсететінін айтады, жауап [i] жылырақ температураны алу үшін i-ші күннен кейін күту керек күндер саны болатындай массив жауабын қайтарады. Егер бұл мүмкін болатын болашақ күн болмаса, оның орнына [i] == 0 жауабын қалдырыңыз. …

Ары қарай оқу

LRU Cache Leetcode шешімі

Мәселе туралы мәлімдеме LRU кэшінің LeetCode шешімі – «LRU кэші» ең аз пайдаланылған (LRU) кэшінен кейінгі деректер құрылымын жобалауды сұрайды. Бізге келесі функциялары бар LRUCache сыныбын енгізу қажет: LRUCache(int сыйымдылығы): LRU кэшін инициализациялайды. оң өлшемді сыйымдылықпен. int get (int пернесі): мәнді қайтару ...

Ары қарай оқу

Жарамды жақшаларды жасау үшін ең аз жою LeetCode шешімі

Мәселе туралы мәлімдеме Жарамды жақшаларды жасау үшін ең аз жою LeetCode шешімі – Сізге '(', ')' және кіші әріпті ағылшын таңбаларынан тұратын s жолы беріледі. Сіздің міндетіңіз - жақшалардың ең аз санын (кез келген орындарда '(' немесе ')') алып тастау, осылайша алынған жақшалар жолы ...

Ары қарай оқу

Қайталанатын таңбаларсыз ең ұзын ішкі жол Leetcode шешімі

Мәселе мәлімдемесі Қайталанатын таңбаларсыз ең ұзын ішкі жол LeetCode шешімі – s жолының берілгенін айтады. Біз таңбаларды қайталамай ең ұзын ішкі жолды табуымыз керек. Мысал: Енгізу: s = ”abcabcbb” Шығару: 3 Түсіндірме: Қайталанбайтын таңбаларсыз ең ұзын ішкі жолдың ұзындығы 3. Жол: “abc”. Енгізу: s = “bbbbb”…

Ары қарай оқу

LeetCode шешімін клондау графигі

Проблемалық мәлімдеме Clone Graph LeetCode шешімі – Бізге жалғанған бағытталмаған графиктегі түйінге сілтеме беріледі және графиктің терең көшірмесін қайтару сұралады. Терең көшірме негізінен клон болып табылады, онда терең көшірмеде жоқ түйінде сілтеме болмауы керек ...

Ары қарай оқу

Жарамды жақша Leetcode шешімі

Мәселе туралы мәлімдеме Жарамды жақшалар LeetCode шешімі – «Жарамды жақшалар» сізге тек '(', ')', '{', '}', '[' және ']' таңбаларын қамтитын жол берілгенін айтады. Енгізілген жолдың жарамды жол екенін немесе жоқтығын анықтауымыз керек. Ашық жақшалар жабылуы керек болса, жол жарамды жол деп аталады ...

Ары қарай оқу

Translate »