โซลูชัน LeetCode Subarray ต่อเนื่องที่ไม่ได้เรียงลำดับที่สั้นที่สุด

คำชี้แจงปัญหา Shortest Unsorted Continuous Subarray LeetCode Solution กล่าวว่า – จากจำนวนอาร์เรย์ที่เป็นจำนวนเต็ม คุณต้องค้นหาอาร์เรย์ย่อยแบบต่อเนื่องหนึ่งรายการซึ่งหากคุณจัดเรียงเฉพาะอาร์เรย์ย่อยนี้ในลำดับจากน้อยไปมาก อาร์เรย์ทั้งหมดจะถูกเรียงลำดับจากน้อยไปมาก ส่งกลับความยาวของอาร์เรย์ย่อยที่สั้นที่สุด ตัวอย่างที่ 1: …

อ่านเพิ่มเติม

ถอดรหัสสตริง Leetcode Solution

คำชี้แจงปัญหา สตริงถอดรหัส โซลูชัน LeetCode – “ถอดรหัสสตริง” ขอให้คุณแปลงสตริงที่เข้ารหัสเป็นสตริงที่ถอดรหัส กฎการเข้ารหัสคือ k[encoded_string] โดยที่ encoded_string ในวงเล็บเหลี่ยมจะถูกทำซ้ำทุกประการ k ครั้งโดยที่ k เป็นจำนวนเต็มบวก ตัวอย่าง: อินพุต: s = ”3[a]2[bc]” เอาต์พุต: “aaabcbc” …

อ่านเพิ่มเติม

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution กล่าวว่า - ให้ root ของไบนารีทรี แผ่ต้นไม้ให้เป็น "รายการที่เชื่อมโยง":

  • “รายการที่เชื่อมโยง” ควรใช้เหมือนกัน TreeNode ชั้นที่ right ตัวชี้ลูกชี้ไปที่โหนดถัดไปในรายการและ left ตัวชี้ลูกอยู่เสมอ null.
  • “รายการที่เชื่อมโยง” ควรอยู่ในลำดับเดียวกับ a สั่งซื้อล่วงหน้า ข้ามผ่าน ของต้นไม้ไบนารี

 

1 ตัวอย่าง:

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode SolutionInput:

 root = [1,2,5,3,4,null,6]

Output:

 [1,null,2,null,3,null,4,null,5,null,6]

2 ตัวอย่าง:

Input:

 root = []

Output:

 []

3 ตัวอย่าง:

Input:

 root = [0]

Output:

 [0]

 

อัลกอริทึม –

ความคิด -

  • ในการทำให้ไบนารีทรีแบนราบ ก่อนอื่นเราจะหาองค์ประกอบขวาสุดของทรีย่อยทางซ้าย และหลังจากที่เราได้องค์ประกอบทางขวาสุดแล้ว เราจะเชื่อมโยงตัวชี้ทางขวาของโหนดนั้นกับทรีย่อยทางขวาของทรีย่อยที่กำหนด
  • ในขั้นตอนที่ 2 เราจะเชื่อมโยงตัวชี้ทางขวาของโหนดรูทกับทรีย่อยทางซ้าย และตั้งค่าทรีย่อยทางซ้ายเป็นโมฆะ
  • ในขั้นตอนที่ 3 ตอนนี้โหนดรูทของเราเป็นโหนดทรีย่อยด้านขวา กระบวนการเดียวกันกับที่จะเกิดขึ้นกับโหนดนี้ และกระบวนการจะดำเนินต่อไปจนกว่าส่วนด้านซ้ายทั้งหมดจะกลายเป็นโมฆะ

แนวทางสำหรับ Flatten Binary Tree เพื่อเชื่อมโยงรายการ Leetcode Solution –

– ในตอนแรก ฉันจะเรียกใช้ลูปเช่น while(root != null) จากนั้นจะรับสองตัวแปรและเก็บทรีย่อยทางซ้าย

– จากนั้นจะตรวจสอบโหนดขวาสุดของทรีย่อยซ้ายโดยใช้ while(k.left != null) และจะเชื่อมโยงโหนดนั้นกับทรีย่อยทางขวาโดยใช้ (k.right = root.right)

– จากนั้นเชื่อมโยงตัวชี้ขวาของโหนดรูทกับทรีย่อยทางซ้าย (root.right = left) และตั้งค่าตัวชี้ซ้ายของโหนดรูทเป็น null(root.left=null) และจะอัปเดตโดย ( root = root.right ) ดังนั้นตอนนี้ root ถูกต้อง โหนดย่อย

– กระบวนการนี้จะดำเนินต่อไปจนกว่าส่วนทรีย่อยด้านซ้ายทั้งหมดจะกลายเป็นทรีย่อยด้านขวา ดังนั้นไบนารีทรีจะแบนราบ

 

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution

โซลูชันหลาม:

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

คำชี้แจงปัญหา การจัดเรียงเหรียญ โซลูชัน LeetCode – “การจัดเรียงเหรียญ” ขอให้คุณสร้างบันไดด้วยเหรียญเหล่านี้ บันไดประกอบด้วย k แถว โดยที่แถวนั้นประกอบด้วยเหรียญ i บันไดแถวสุดท้ายอาจไม่สมบูรณ์ สำหรับจำนวนเหรียญที่กำหนด ให้คืน ...

อ่านเพิ่มเติม

โซลูชัน Leetcode อุณหภูมิรายวัน

คำชี้แจงปัญหา The Daily Temperatures Leetcode Solution: ระบุว่าให้อาร์เรย์ของอุณหภูมิจำนวนเต็มแสดงถึงอุณหภูมิรายวัน ให้ส่งคืนคำตอบอาร์เรย์ โดยที่คำตอบ[i] คือจำนวนวันที่คุณต้องรอหลังจากวันที่ ith เพื่อให้อุณหภูมิอุ่นขึ้น หากไม่มีวันเป็นไปได้ ให้เก็บ answer[i] == 0 ไว้แทน …

อ่านเพิ่มเติม

LRU Cache Leetcode Solution

คำชี้แจงปัญหา แคช LRU โซลูชัน LeetCode – “แคช LRU” ขอให้คุณออกแบบโครงสร้างข้อมูลตามแคชที่ใช้ล่าสุด (LRU) น้อยที่สุด เราจำเป็นต้องใช้คลาส LRUCache ที่มีฟังก์ชันต่อไปนี้: LRUCache(ความจุ int): เตรียมใช้งานแคช LRU ด้วยความจุขนาดบวก int get(int key): ส่งคืนค่า …

อ่านเพิ่มเติม

ลบขั้นต่ำเพื่อสร้างวงเล็บที่ถูกต้อง LeetCode Solution

คำชี้แจงปัญหา การลบขั้นต่ำเพื่อสร้างวงเล็บที่ถูกต้อง โซลูชัน LeetCode – คุณจะได้รับสตริงของ '(', ')' และอักขระภาษาอังกฤษตัวพิมพ์เล็ก งานของคุณคือการลบจำนวนวงเล็บขั้นต่ำ ( '(' หรือ ')' ในตำแหน่งใดๆ ) เพื่อให้สตริงที่เป็นผลลัพธ์เป็น ...

อ่านเพิ่มเติม

สตริงย่อยที่ยาวที่สุดโดยไม่ใช้อักขระซ้ำ Leetcode Solution

คำชี้แจงปัญหา สตริงย่อยที่ยาวที่สุดโดยไม่มีอักขระซ้ำ โซลูชัน LeetCode – ระบุว่าให้สตริง s เราจำเป็นต้องค้นหาสตริงย่อยที่ยาวที่สุดโดยไม่ใช้อักขระซ้ำ ตัวอย่าง: อินพุต: s = ”abcabcbb” เอาต์พุต: 3 คำอธิบาย: สตริงย่อยที่ยาวที่สุดที่ไม่มีอักขระซ้ำคือความยาว 3 สตริงคือ: “abc” อินพุต: s = ”bbbbb” …

อ่านเพิ่มเติม

โคลนกราฟ โซลูชัน LeetCode

คำชี้แจงปัญหา กราฟโคลน โซลูชัน LeetCode - เราได้รับการอ้างอิงของโหนดในกราฟที่ไม่ระบุทิศทางที่เชื่อมต่อ และถูกขอให้ส่งคืนสำเนาของกราฟแบบลึก สำเนาลึกนั้นเป็นโคลนที่ไม่มีโหนดในสำเนาลึกควรมีการอ้างอิง ...

อ่านเพิ่มเติม

วงเล็บที่ถูกต้อง โซลูชัน Leetcode

คำชี้แจงปัญหา วงเล็บที่ถูกต้อง โซลูชัน LeetCode – “วงเล็บที่ถูกต้อง” ระบุว่าคุณได้รับสตริงที่มีเพียงอักขระ '(', ')', '{', '}', '[' และ ']' เราจำเป็นต้องตรวจสอบว่าสตริงอินพุตเป็นสตริงที่ถูกต้องหรือไม่ สตริงถูกกล่าวว่าเป็นสตริงที่ถูกต้องหากต้องปิดวงเล็บเปิด ...

อ่านเพิ่มเติม

Translate »