LeetCode Шешім жақшасының ұпайы

Мәселе туралы мәлімдеме LeetCode Шешім жақшасының ұпайы былай дейді: Теңдестірілген жақшалар жолы берілген s және максималды ұпайды қайтарады. Теңгерілген жақша жолының ұпайы келесі ережелерге негізделген: «()» 1 ұпайға ие. AB ұпайы A + B ұпайына ие, мұнда A және B теңестірілген жақша жолдары. (A) 2 * A ұпайы бар, мұндағы А – …

Ары қарай оқу

Екілік ағаштың ретімен өтуі LeetCode шешімі

Мәселе туралы мәлімдеме: Екілік ағаштың ретімен өтуі LeetCode шешімі Екілік ағаштың түбірін ескере отырып, оның түйіндерінің мәндерінің ретімен өтуін қайтарыңыз. 1-мысал: Енгізу: root = [1,null,2,3] Шығару: [1,3,2] 2-мысал: Кіріс: root = [] Шығу: [] 3-мысал: Кіріс: root = [1] Шығыс: [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

Екі санды қосу II Leetcode шешімі

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

Ары қарай оқу

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

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

Ары қарай оқу

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

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

Ары қарай оқу

Жаңбыр суын ұстау 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 »