امتیاز راه حل پرانتز LeetCode

بیان مسئله امتیاز راه حل LeetCode پرانتز می گوید - با توجه به یک رشته پرانتز متعادل s و حداکثر امتیاز را برمی گرداند. امتیاز یک رشته پرانتز متعادل بر اساس قوانین زیر است: "()" دارای امتیاز 1 است. AB دارای امتیاز A + B است که در آن A و B رشته های پرانتز متعادل هستند. (A) دارای امتیاز 2 * A است که در آن A یک …

ادامه مطلب

راه حل LeetCode پیمایش ترتیب درخت دودویی

بیان مسئله: پیمایش ترتیب درخت دودویی راه حل LeetCode با توجه به ریشه یک درخت باینری، پیمایش ترتیب مقادیر گره های آن را برگردانید. مثال 1: ورودی: ریشه = [1، تهی، 2,3،1,3,2] خروجی: [2،3،1] مثال 1: ورودی: ریشه = [] خروجی: [] مثال XNUMX: ورودی: ریشه = [XNUMX] خروجی: [XNUMX] محدودیت ها: تعداد گره ها در …

ادامه مطلب

رمزگشایی رشته Leetcode Solution

بیان مشکل رشته رمزگشایی راه‌حل LeetCode – «رشته رمزگشایی» از شما می‌خواهد رشته کدگذاری شده را به رشته رمزگشایی شده تبدیل کنید. قانون رمزگذاری k[encoded_string] است، که در آن رشته encoded_در داخل پرانتز مربع دقیقاً k بار تکرار می‌شود که k یک عدد صحیح مثبت است. مثال: ورودی: s = ”3[a]2[bc]” خروجی: “aaabcbc”…

ادامه مطلب

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode می گوید که - با توجه به root از یک درخت باینری، درخت را در یک "لیست پیوندی" صاف کنید:

  • «فهرست پیوندی» باید از همان استفاده کند TreeNode کلاسی که در آن right اشاره گر فرزند به گره بعدی در لیست اشاره می کند left نشانگر کودک همیشه است null.
  • "فهرست پیوندی" باید به ترتیب a باشد قبل از سفارش پیمایش از درخت دوتایی

 

به عنوان مثال 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 = چپ) پیوند دهید و نشانگر سمت چپ گره ریشه را به عنوان null (root.left=null) قرار دهید و با ( root = root.right ) به روز می شود، بنابراین اکنون root سمت راست است. گره زیر درخت

– این روند تا زمانی ادامه خواهد داشت که تمام قسمت های زیر درخت سمت چپ به زیردرخت سمت راست تبدیل شوند. بنابراین، درخت باینری صاف می شود.

 

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode

راه حل پایتون:

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

راه حل Leetcode Two Numbers II را اضافه کنید

بیان مسئله افزودن دو عدد II راه حل LeetCode – "افزودن دو عدد II" بیان می کند که دو لیست پیوندی غیر خالی نشان دهنده دو عدد صحیح غیر منفی هستند که در آن رقم مهم ترین رقم اول می آید و هر گره دقیقاً یک رقم را شامل می شود. باید دو عدد را جمع کنیم و حاصل جمع را به صورت …

ادامه مطلب

دمای روزانه راه حل Leetcode

بیان مسئله دمای روزانه راه حل Leetcode: بیان می کند که با توجه به یک آرایه از اعداد صحیح دما، دمای روزانه را نشان می دهد، یک پاسخ آرایه ای را برمی گرداند به طوری که پاسخ[i] تعداد روزهایی است که شما باید بعد از روز 0 منتظر بمانید تا دمای گرم تری بدست آورید. اگر هیچ روز آینده ای برای این امکان وجود ندارد، به جای آن پاسخ[i] == XNUMX را نگه دارید. …

ادامه مطلب

حداقل حذف برای ایجاد پرانتز معتبر راه حل LeetCode

بیان مسئله حداقل حذف برای ایجاد پرانتزهای معتبر راه حل LeetCode – به شما یک رشته از نویسه های انگلیسی «(»، «)» و حروف کوچک داده می شود. وظیفه شما این است که حداقل تعداد پرانتز ('(' یا ')'، در هر موقعیت) را حذف کنید تا رشته پرانتز حاصل …

ادامه مطلب

به دام انداختن راه حل لیتکد آب باران

بیان مسئله راه حل LeetCode Trapping Rain Water – «به دام انداختن آب باران» بیان می کند که با توجه به آرایه ای از ارتفاعات که نشان دهنده یک نقشه ارتفاعی است که در آن عرض هر نوار 1 است. ما باید مقدار آبی که پس از باران به دام افتاده است را پیدا کنیم. مثال: ورودی: ارتفاع = [0,1,0,2,1,0,1,3,2,1,2,1] خروجی: 6 توضیح: بررسی…

ادامه مطلب

راه حل Leetcode پرانتز معتبر

بیان مسئله پرانتزهای معتبر راه حل LeetCode – "پرانتز معتبر" بیان می کند که به شما یک رشته داده می شود که فقط شامل کاراکترهای '('، ')'، '{'، '}'، '[' و ']' است. باید تعیین کنیم که آیا رشته ورودی یک رشته معتبر است یا خیر. اگر پرانتزهای باز باید بسته شوند، به رشته ای گفته می شود که یک رشته معتبر است…

ادامه مطلب

حداکثر فرکانس پشته Leetcode راه حل

بیانیه مشکل حداکثر فرکانس پشته راه حل LeetCode - "Maximum Frequency Stack" از شما می خواهد یک پشته فرکانس طراحی کنید که در آن هر زمان که عنصری را از پشته بیرون می آوریم، باید متداول ترین عنصر موجود در پشته را برگرداند. کلاس FreqStack را پیاده سازی کنید: FreqStack() یک پشته فرکانس خالی می سازد. فشار خالی (int val) هل می دهد…

ادامه مطلب

Translate »