ค้นหาผู้ชนะของเกม Circular โซลูชัน LeetCode

คำชี้แจงปัญหา ค้นหาผู้ชนะของเกมวงกลม โซลูชัน LeetCode – มีเพื่อน n คนที่กำลังเล่นเกมอยู่ เพื่อน ๆ นั่งเป็นวงกลมและเรียงลำดับจาก 1 ถึง n ตามเข็มนาฬิกา อย่างเป็นทางการมากขึ้น การย้ายตามเข็มนาฬิกาจากเพื่อน ith นำคุณไปที่ ...

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

Binary Tree Inorder Traversal โซลูชัน LeetCode

คำชี้แจงปัญหา: Binary Tree Inorder Traversal โซลูชัน LeetCode จากรากของต้นไม้ไบนารี ให้คืนค่าการข้ามผ่านที่ไม่เป็นระเบียบของค่าโหนด ตัวอย่างที่ 1: อินพุต: รูท = [1,null,2,3] เอาต์พุต: [1,3,2] ตัวอย่างที่ 2: อินพุต: รูท = [] เอาต์พุต: [] ตัวอย่างที่ 3: อินพุต: รูท = [1] เอาต์พุต: [1] ข้อจำกัด: จำนวนโหนดใน …

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

โซลูชัน Leetcode รวมเส้นทางขั้นต่ำ

คำชี้แจงปัญหา ผลรวมเส้นทางขั้นต่ำ โซลูชัน LeetCode – “ผลรวมเส้นทางขั้นต่ำ” ระบุว่าตาราง anxm ที่ประกอบด้วยจำนวนเต็มที่ไม่เป็นลบ และเราจำเป็นต้องค้นหาเส้นทางจากบนซ้ายไปล่างขวา ซึ่งจะลดผลรวมของตัวเลขทั้งหมดตามเส้นทาง . เราทำได้แค่ขยับ…

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

ต้นทุนขั้นต่ำปีนบันได LeetCode Solution

คำชี้แจงปัญหา ต้นทุนขั้นต่ำ ปีนบันได โซลูชัน LeetCode – กำหนดต้นทุนอาร์เรย์จำนวนเต็ม โดยที่ cost[i] คือต้นทุนของขั้นตอน ith บนบันได เมื่อคุณชำระค่าใช้จ่ายแล้ว คุณสามารถเดินขึ้นได้หนึ่งหรือสองขั้น คุณสามารถเริ่มจากขั้นตอนที่มีดัชนี 0 หรือขั้นตอนด้วย ...

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

แผ่ 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

แทรก ลบ GetRandom O(1) Leetcode Solution

คำชี้แจงปัญหา The Insert Delete GetRandom O(1) LeetCode Solution – “Insert Delete GetRandom O(1)” ขอให้คุณนำฟังก์ชันทั้งสี่นี้ไปใช้ในความซับซ้อนของเวลา O(1) insert(val): ใส่ค่า val ลงในชุดสุ่มและคืนค่า จริง หากองค์ประกอบนั้นไม่มีอยู่ในชุดในตอนแรก มันคืนค่าเท็จเมื่อ ...

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

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

คำชี้แจงปัญหา หมายเลข Fibonacci โซลูชัน LeetCode – "หมายเลข Fibonacci" ระบุว่าหมายเลข Fibonacci ซึ่งใช้แทนค่า F(n) โดยทั่วไปเรียกว่าลำดับ Fibonacci โดยที่แต่ละหมายเลขเป็นผลรวมของสองตัวก่อนหน้า โดยเริ่มจาก 0 และ 1 นั่นคือ F(0) = 0, F(1) = 1 F(n) = F(n – 1) + F(n …

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

Translate »