องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่
นับเกาะและกำกับป้ายให้แต่ละภูมิภาค
องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
องค์ประกอบเชื่อมต่อคืออะไร
องค์ประกอบเชื่อมต่อคือกลุ่มโหนดที่แต่ละโหนดสามารถไปถึงโหนดอื่นในกลุ่มได้ กราฟหนึ่งกราฟอาจมีกลุ่มที่แยกจากกันหลายกลุ่ม 🧩
นับองค์ประกอบเชื่อมต่อ
หากต้องการนับองค์ประกอบเชื่อมต่อ ให้เริ่มการสำรวจจากโหนดทุกโหนดที่ยังไม่เคยเยี่ยมชม จุดเริ่มต้นใหม่แต่ละจุดจะทำเครื่องหมายกลุ่มใหม่ทั้งกลุ่มหนึ่งกลุ่ม
วนดูโหนดทั้งหมด
ไล่ดูโหนดตั้งแต่ 1 ถึง n เมื่อพบโหนดที่ยังไม่เคยเยี่ยมชม แสดงว่าคุณค้นพบองค์ประกอบเชื่อมต่อใหม่ที่ต้องสำรวจ
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1การสำรวจหนึ่งครั้งต่อหนึ่งกลุ่ม
BFS หรือ DFS ภายในจะทำเครื่องหมายองค์ประกอบเชื่อมต่อทั้งหมดว่าเยี่ยมชมแล้ว ดังนั้นลูปภายนอกจะข้ามกลุ่มนั้นในรอบถัดไป
กริดก็เป็นกราฟเช่นกัน
กริดสองมิติคือกราฟที่ซ่อนอยู่ โดยแต่ละช่องเป็นโหนดที่เชื่อมกับเพื่อนบ้าน แนวคิดนี้นำไปสู่แนวคิดเติมพื้นที่แบบคลาสสิก 🗺️
สี่ทิศทาง
จากช่องหนึ่ง โดยทั่วไปคุณจะเคลื่อนที่ขึ้น ลง ซ้าย และขวา เก็บการเคลื่อนที่เหล่านี้เป็นเวกเตอร์ทิศทางเพื่อให้โค้ดเป็นระเบียบ
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]อยู่ภายในตาราง
ก่อนขยับ ให้ตรวจสอบว่าแถวและคอลัมน์ใหม่อยู่ในขอบเขต การข้ามการตรวจสอบนี้ทำให้เกิดข้อผิดพลาดของดัชนีหรือได้คำตอบผิด
if 0 <= nr < rows and 0 <= nc < cols:
passเติมสีหนึ่งบริเวณ
การเติมสีเริ่มจากช่องหนึ่งแล้วแผ่ไปยังทุกช่องประเภทเดียวกันที่เชื่อมต่อกัน คล้ายกับเครื่องมือถังสี
นับจำนวนเกาะ
หากต้องการนับเกาะ ให้สแกนทั่วทั้งตาราง เมื่อพบช่องแผ่นดินใหม่ ให้เติมสีทั่วทั้งเกาะแล้วเพิ่มตัวนับขึ้นหนึ่ง
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1กำกับป้ายบริเวณ
คุณสามารถเก็บป้ายกำกับไว้ให้แต่ละช่องระหว่างการเติมสีได้ ภายหลังจึงทราบได้ทันทีว่าช่องใดอยู่ในบริเวณใด
เชิงเส้นตามขนาดตาราง
แต่ละช่องจะถูกเยี่ยมชมครั้งเดียว ดังนั้นการเติมสีบนตารางจึงใช้เวลา O(จำนวนแถว คูณ จำนวนคอลัมน์) ซึ่งอยู่ภายในข้อจำกัดของการแข่งขันได้อย่างสบาย
ตรวจสอบสั้น ๆ
คุณจะนับส่วนประกอบที่เชื่อมต่อกันได้อย่างไร
ทบทวน
คุณนับส่วนประกอบโดยเดินสำรวจจากโหนดที่ยังไม่เคยเยี่ยมชมแต่ละโหนด และใช้การเติมสีบนตารางเพื่อกำกับป้ายบริเวณและนับเกาะ 🎉
คำถามที่พบบ่อย
บทเรียน “องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่”
นับเกาะและกำกับป้ายให้แต่ละภูมิภาค คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สร้างรายการประชิดจากข้อมูลเข้า
- BFS สำหรับพาธสั้นที่สุดแบบไม่มีน้ำหนัก
- DFS การเรียกซ้ำ และสแตกแบบวนซ้ำ
- องค์ประกอบที่เชื่อมต่อกันและการเติมพื้นที่