Жарамды үшбұрыш саны LeetCode шешімі

Мәселе туралы мәлімдеме: Жарамды үшбұрыш саны LeetCode Шешімі былай дейді: Бүтін массив сандары берілген болса, үшбұрыштың қабырғаларының ұзындығы ретінде алсақ, үшбұрыш жасай алатын массивтен таңдалған үштіктер санын қайтарыңыз. 1-мысал: Енгізу: сандар = [2,2,3,4] Шығару: 3 Түсіндіру: Жарамды комбинациялар: 2,3,4 (…

Ары қарай оқу

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

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

Ары қарай оқу

Тіктөртбұрыш қабаттасуы LeetCode шешімі

Мәселе туралы мәлімдеме: Тіктөртбұрыштың қабаттасуы LeetCode шешімі – ось бойынша тураланған тіктөртбұрыш тізім ретінде ұсынылатынын айтады, [x1, y1, x2, y2], мұндағы (x1, y1) оның төменгі сол жақ бұрышының координатасы және (x2) , y2) оның жоғарғы оң жақ бұрышының координатасы. Оның үстіңгі және төменгі жиектері X осіне параллель, ал сол жақ …

Ары қарай оқу

График екі жақты ма? LeetCode шешімі

Мәселе мәлімдемесі – екі жақты LeetCode шешімі – n түйіні бар бағытталмаған график бар, мұнда әрбір түйін 0 және n – 1 аралығында нөмірленеді. Сізге 2D жиым графигі берілген, мұндағы graph[u] – u түйінін түйіндейтін түйіндердің жиымы. іргелес орналасқан. Ресми түрде, [u] графындағы әрбір v үшін u түйіні мен v түйіні арасында бағытталмаған жиек бар. Графикте ...

Ары қарай оқу

Жобалау Сөздерді қосу және іздеу деректер құрылымы LeetCode шешімі

Мәселе туралы мәлімдеме: Сөздерді қосу және іздеу деректер құрылымын жобалау LeetCode шешімі былай дейді: Жаңа сөздерді қосуды және жолдың бұрын қосылған кез келген жолға сәйкес келетінін анықтауды қолдайтын деректер құрылымын құрастырыңыз. WordDictionary класын іске асыру: WordDictionary() Нысанды инициализациялайды. void addWord(word) Деректер құрылымына сөз қосады, оны кейінірек сәйкестендіруге болады. bool іздеу(сөз) егер бар болса, шын мәнін қайтарады ...

Ары қарай оқу

Минималды жол сомасының Leetcode шешімі

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

Ары қарай оқу

Баспалдақпен өрмелеудің минималды құны LeetCode шешімі

Мәселе туралы мәлімдеме Баспалдақпен көтерілудің минималды құны LeetCode шешімі – бүтін массив құны берілген, мұнда құны [i] – баспалдақтағы i-ші қадамның құны. Құнды төлегеннен кейін сіз бір немесе екі сатыға көтеріле аласыз. Сіз 0 индексі бар қадамнан немесе ... бар қадамнан бастай аласыз.

Ары қарай оқу

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

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

Ары қарай оқу

Берілген қосынды шарты LeetCode шешімін қанағаттандыратын ішкі реттіліктер саны

Мәселе мәлімдемесі Берілген қосынды шартын қанағаттандыратын бағыныңқы қатарлар саны LeetCode шешімі – бүтін сандар массиві сандар мен бүтін мақсат берілгенін айтады. Ондағы ең аз және ең үлкен элементтің қосындысы мақсаттан аз немесе тең болатындай бос емес ішкі реттік сандар санын қайтарыңыз. Өйткені жауап тым болуы мүмкін ...

Ары қарай оқу

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

Translate »