ข้อ 4 · LC605 Can Place Flowers 🟡
มีแปลงดอกไม้ flowerbed (0 = ว่าง, 1 = มีดอก) ห้ามปลูกติดกัน — ถามว่าปลูกเพิ่มได้อีก n ต้นไหม
มีแปลงดอกไม้ที่แบ่งเป็นช่องเรียงกันเป็นแถวเดียว ให้เป็นลิสต์ชื่อ flowerbed โดย 0 คือช่องว่าง และ 1 คือช่องที่มีดอกไม้ปลูกอยู่แล้ว
กติกามีข้อเดียว: ดอกไม้สองต้นห้ามอยู่ในช่องที่ติดกัน
จงตอบว่าปลูกเพิ่มอีก n ดอกโดยไม่ผิดกติกาได้หรือไม่ ตอบเป็น true หรือ false
โจทย์รับประกันว่า flowerbed ที่ส่งมาไม่ผิดกติกาอยู่ก่อนแล้ว
- Input:
- flowerbed = [1,0,0,0,1], n = 1
- Output:
- true
- Explanation:
- ช่อง index 1 ปลูกไม่ได้เพราะซ้ายมือมีดอกอยู่ (index 0 เป็น 1) ช่อง index 3 ก็ปลูกไม่ได้เพราะขวามือมีดอกอยู่ (index 4 เป็น 1)
เหลือ index 2 ช่องเดียวที่ทั้งซ้ายและขวาว่าง ปลูกได้พอดี 1 ดอก แปลงกลายเป็น [1,0,1,0,1] ซึ่งขอมา 1 ก็พอดี
- Input:
- flowerbed = [1,0,0,0,1], n = 2
- Output:
- false
- Explanation:
- แปลงเดียวกันเป๊ะ แต่คราวนี้ขอ 2 ดอก
จากเหตุผลข้างบน แปลงนี้รับได้มากสุดจริง ๆ แค่ 1 ดอก ไม่ว่าจะเลือกปลูกยังไงก็ตาม จึงตอบ false
- Input:
- flowerbed = [0], n = 1
- Output:
- true
- Explanation:
- ช่องเดียวโดด ๆ ไม่มีเพื่อนบ้านทั้งซ้ายและขวา จึงไม่มีทางผิดกติกา ปลูกได้เลย
นี่คือเคสที่โค้ดของคนส่วนใหญ่พังในรอบแรก เพราะเผลอไปอ่านช่องข้าง ๆ ที่ไม่มีอยู่จริง
- Input:
- flowerbed = [0,0,1,0,0], n = 2
- Output:
- true
- Explanation:
- ปลูกที่ index 0 ได้ (ไม่มีเพื่อนบ้านซ้าย ส่วนขวาคือ index 1 ว่าง) และปลูกที่ index 4 ได้ (ไม่มีเพื่อนบ้านขวา ส่วนซ้ายคือ index 3 ว่าง)
ได้ครบ 2 ดอกจากขอบแปลงล้วน ๆ กลายเป็น [1,0,1,0,1] — เคสนี้บอกว่าขอบแปลงไม่ใช่แค่กับดัก แต่เป็นโอกาสด้วย
- Input:
- flowerbed = [1,0,0,0,0,1], n = 2
- Output:
- false
- Explanation:
- ตรงกลางมีช่องว่างติดกัน 4 ช่อง (index 1 ถึง 4) ดูเหมือนน่าจะปลูกได้ 2 ดอก แต่ index 1 ติดดอกทางซ้าย และ index 4 ติดดอกทางขวา
เหลือใช้ได้จริงแค่ index 2 กับ 3 ซึ่งอยู่ติดกัน จึงปลูกได้แค่ 1 ดอก — จำนวนช่องว่างกับจำนวนดอกที่ปลูกได้ไม่ได้แปรผันตรงกันแบบง่าย ๆ
- 1 <= flowerbed.length <= 2 × 10^4
- flowerbed[i] เป็น 0 หรือ 1 เท่านั้น
- flowerbed ที่ให้มาไม่มี 1 สองตัวติดกัน
- 0 <= n <= flowerbed.length
ข้อนี้ดูง่ายแต่มีเคสขอบที่ทำให้คนตกเยอะมาก ก่อนเขียนโค้ด ให้ลองไล่ด้วยมือกับแปลงสั้น ๆ อย่าง [0] และ [0,0,1] ก่อน สองเคสนี้จะบอกเองว่าต้องระวังอะไร
💡 ใบ้ขั้นที่ 1 — ช่องหนึ่งปลูกได้เมื่อไหร่
ช่องหนึ่งปลูกได้ต้องครบสามเงื่อนไข: ตัวมันเองว่าง และเพื่อนบ้านซ้ายว่าง และเพื่อนบ้านขวาว่าง
คำถามที่ต้องตอบต่อคือ ช่องแรกสุดกับช่องท้ายสุดมีเพื่อนบ้านครบสองข้างไหม
💡 ใบ้ขั้นที่ 2 — เขียนเงื่อนไขเพื่อนบ้านให้ปลอดภัย
อย่าเขียน flowerbed[i-1] ตรง ๆ เพราะตอน i เป็น 0 ค่า i-1 จะเป็น -1 ซึ่ง Python ไม่ error แต่ไปอ่านช่องสุดท้ายของแถวแทน
left = (i == 0) or (flowerbed[i-1] == 0) # ไม่มีเพื่อนบ้านซ้าย ถือว่าว่าง
right = (i == len(flowerbed)-1) or (flowerbed[i+1] == 0)💡 ใบ้ขั้นที่ 3 — ปลูกเลยหรือรอ
พอเจอช่องที่ปลูกได้ ให้ปลูกทันทีแล้วนับเพิ่ม อย่าเก็บไว้คิดทีหลัง และต้องเขียน 1 ลงช่องนั้นจริงเพื่อให้ช่องถัดไปรู้ว่าซ้ายมือมีดอกแล้ว
นับได้ครบ n เมื่อไหร่ก็ตอบ true ได้เลย ไม่ต้องกวาดต่อจนจบแถว
🧭 กล่องสอน — ไล่ตั้งแต่ศูนย์ทีละขั้น (เปิดเมื่อพร้อม)
ขั้นที่ 1 · โจทย์นี้ขออะไรจริง ๆ
โจทย์ไม่ได้ถามว่าปลูกได้มากที่สุดกี่ดอก แต่ถามแค่ว่าปลูกได้ถึง n ดอกไหม ซึ่งเป็นคำถามที่ตอบง่ายกว่า
และมีของแถมสำคัญคือโจทย์รับประกันว่าแปลงที่ให้มาไม่ผิดกติกาอยู่แล้ว เราจึงไม่ต้องเสียเวลาตรวจข้อมูลตั้งต้น สนใจแค่ดอกที่เราจะเติมเอง
ความยาวแปลงถึง 20,000 ช่อง จึงลองทุกความเป็นไปได้ไม่ได้ ต้องกวาดรอบเดียวแล้วตัดสินใจทันที
ขั้นที่ 2 · ลองทำด้วยมือก่อนเขียนโค้ด
ใช้เคส [1,0,0,0,1] ที่ขอปลูก 1 ดอก ลองไล่ทีละช่องแล้วดูว่าช่องไหนปลูกได้
def can_place(bed, n):
bed = bed[:]
count = 0
for i in range(len(bed)):
left = (i == 0) or (bed[i-1] == 0)
right = (i == len(bed)-1) or (bed[i+1] == 0)
if bed[i] == 0 and left and right:
bed[i] = 1
count += 1
print(f" i={i}: ว่าง+ซ้ายว่าง+ขวาว่าง -> ปลูก! ได้ {count} ดอก | แปลง={bed}")
else:
why = "มีดอกอยู่แล้ว" if bed[i] == 1 else ("ซ้ายติดดอก" if not left else "ขวาติดดอก")
print(f" i={i}: ปลูกไม่ได้ ({why})")
print(f" ปลูกได้จริง {count} ดอก | ขอ {n} ดอก -> {count >= n}")
return count >= n
print("flowerbed=[1,0,0,0,1], n=1 ->", can_place([1,0,0,0,1], 1)) i=0: ปลูกไม่ได้ (มีดอกอยู่แล้ว)
i=1: ปลูกไม่ได้ (ซ้ายติดดอก)
i=2: ว่าง+ซ้ายว่าง+ขวาว่าง -> ปลูก! ได้ 1 ดอก | แปลง=[1, 0, 1, 0, 1]
i=3: ปลูกไม่ได้ (ซ้ายติดดอก)
i=4: ปลูกไม่ได้ (มีดอกอยู่แล้ว)
ปลูกได้จริง 1 ดอก | ขอ 1 ดอก -> True
flowerbed=[1,0,0,0,1], n=1 -> Trueสังเกตว่าแปลงนี้มีช่องว่างติดกัน 3 ช่อง แต่ปลูกได้แค่ 1 ดอก เพราะสองช่องริมติดดอกเดิม จำนวนช่องว่างกับจำนวนดอกที่ปลูกได้จึงไม่แปรผันตรงกันแบบง่าย ๆ
def can_place(bed, n):
bed = bed[:]
count = 0
for i in range(len(bed)):
left = (i == 0) or (bed[i-1] == 0)
right = (i == len(bed)-1) or (bed[i+1] == 0)
if bed[i] == 0 and left and right:
bed[i] = 1
count += 1
print(f" i={i}: ว่าง+ซ้ายว่าง+ขวาว่าง -> ปลูก! ได้ {count} ดอก | แปลง={bed}")
else:
why = "มีดอกอยู่แล้ว" if bed[i] == 1 else ("ซ้ายติดดอก" if not left else "ขวาติดดอก")
print(f" i={i}: ปลูกไม่ได้ ({why})")
print(f" ปลูกได้จริง {count} ดอก | ขอ {n} ดอก -> {count >= n}")
return count >= n
print("flowerbed=[0,0,1,0,0], n=2 ->", can_place([0,0,1,0,0], 2)) i=0: ว่าง+ซ้ายว่าง+ขวาว่าง -> ปลูก! ได้ 1 ดอก | แปลง=[1, 0, 1, 0, 0]
i=1: ปลูกไม่ได้ (ซ้ายติดดอก)
i=2: ปลูกไม่ได้ (มีดอกอยู่แล้ว)
i=3: ปลูกไม่ได้ (ซ้ายติดดอก)
i=4: ว่าง+ซ้ายว่าง+ขวาว่าง -> ปลูก! ได้ 2 ดอก | แปลง=[1, 0, 1, 0, 1]
ปลูกได้จริง 2 ดอก | ขอ 2 ดอก -> True
flowerbed=[0,0,1,0,0], n=2 -> Trueเคสนี้บอกว่าขอบแปลงไม่ใช่แค่กับดัก แต่เป็นโอกาส เพราะช่องริมมีเพื่อนบ้านข้างเดียว จึงปลูกง่ายกว่าช่องกลาง
ขั้นที่ 3 · กับดักใหญ่ที่สุดของข้อนี้
หลายคนเขียนเงื่อนไขเพื่อนบ้านตรง ๆ เป็น bed[i-1] == 0 ซึ่งดูสมเหตุสมผล แต่พังเงียบ ๆ
เพราะตอน i เป็น 0 ค่า i-1 กลายเป็น -1 และ Python ไม่ error แต่ตีความว่าเป็นช่องสุดท้ายของแถวแทน
def wrong(bed):
bed = bed[:]; count = 0
for i in range(len(bed)):
# ตอน i=0 ค่า i-1 กลายเป็น -1 ซึ่ง Python อ่านเป็น "ช่องสุดท้ายของแถว"
if bed[i] == 0 and bed[i-1] == 0 and (i == len(bed)-1 or bed[i+1] == 0):
bed[i] = 1; count += 1
return count
def right(bed):
bed = bed[:]; count = 0
for i in range(len(bed)):
left = (i == 0) or (bed[i-1] == 0)
rgt = (i == len(bed)-1) or (bed[i+1] == 0)
if bed[i] == 0 and left and rgt:
bed[i] = 1; count += 1
return count
for bed in [[0,0,1], [0,1], [0,0,0,1], [1,0,0,0,1]]:
w, r = wrong(bed), right(bed)
mark = "" if w == r else " <- ปลูกได้น้อยกว่าที่ควร!"
print(f"bed={bed} | อ่าน bed[i-1] ตรง ๆ ปลูกได้ {w} | เช็คขอบให้ถูก ปลูกได้ {r}{mark}")
bed = [0, 0, 1]
print()
print(f"สาเหตุ: bed = {bed} -> bed[-1] = {bed[-1]} (ช่องสุดท้าย ไม่ใช่ 'ไม่มีช่อง')")bed=[0, 0, 1] | อ่าน bed[i-1] ตรง ๆ ปลูกได้ 0 | เช็คขอบให้ถูก ปลูกได้ 1 <- ปลูกได้น้อยกว่าที่ควร!
bed=[0, 1] | อ่าน bed[i-1] ตรง ๆ ปลูกได้ 0 | เช็คขอบให้ถูก ปลูกได้ 0
bed=[0, 0, 0, 1] | อ่าน bed[i-1] ตรง ๆ ปลูกได้ 1 | เช็คขอบให้ถูก ปลูกได้ 1
bed=[1, 0, 0, 0, 1] | อ่าน bed[i-1] ตรง ๆ ปลูกได้ 1 | เช็คขอบให้ถูก ปลูกได้ 1
สาเหตุ: bed = [0, 0, 1] -> bed[-1] = 1 (ช่องสุดท้าย ไม่ใช่ 'ไม่มีช่อง')สังเกตว่าสามเคสท้ายให้ผลตรงกัน มีแค่เคสแรกที่ต่าง นี่คือเหตุผลที่บั๊กแบบนี้รอดการเทสต์ได้ง่าย
ให้ตีความว่า ไม่มีเพื่อนบ้าน เท่ากับ เพื่อนบ้านว่าง เพราะช่องที่ไม่มีอยู่ย่อมไม่มีดอกไม้ เขียนเป็นโค้ดคือเช็ค i == 0 ก่อนแล้วค่อยอ่าน bed[i-1] โดยใช้ or ซึ่ง Python จะข้ามการอ่านทันทีถ้าเงื่อนไขแรกจริงแล้ว
ขั้นที่ 4 · ทำไมปลูกทันทีที่เจอถึงไม่พลาด
คำถามที่ควรถามคือ ถ้าเว้นช่องนี้ไว้แล้วไปปลูกช่องถัดไป จะได้ดอกไม้มากกว่าไหม
คำตอบคือไม่ เพราะตอนเราเดินมาถึงช่องนี้ ฝั่งซ้ายของมันถูกตัดสินไปแล้วและเปลี่ยนไม่ได้ ถ้าตอนนี้ปลูกได้แล้วไม่ปลูก ช่องนี้ก็เสียไปเปล่า ๆ
การปลูกอาจปิดโอกาสของช่องขวาถัดไปหนึ่งช่อง แต่เราก็ได้ดอกไม้มาแล้วหนึ่งดอก จึงไม่ขาดทุน แย่ที่สุดคือเสมอ
และต้องเขียน 1 ลงช่องนั้นจริง ไม่ใช่แค่นับ เพราะช่องถัดไปต้องมองเห็นว่าซ้ายมือมีดอกแล้ว
ขั้นที่ 5 · ปรับให้ออกเร็วขึ้น
โจทย์ถามแค่ว่าถึง n ไหม ดังนั้นพอนับครบ n เราตอบ true ได้เลยไม่ต้องกวาดต่อ
และมีอีกจุดที่ควรระวัง คือถ้าเขียน bed = flowerbed[:] เพื่อไม่แก้ของเดิม นั่นเป็นนิสัยที่ดี แต่กินหน่วยความจำเพิ่มหนึ่งเท่า ถ้าโจทย์ยอมให้แก้ในที่เดิมก็แก้ได้เลย
🔓 เฉลยเต็ม พร้อมอธิบายทีละบรรทัด (ลองเองก่อนนะ)พับไว้ด้านใน — คลิกเมื่อพร้อมดู
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True # ไม่ต้องปลูกอะไรเลย ก็ถือว่าได้
count = 0
for i in range(len(flowerbed)):
if flowerbed[i] != 0:
continue # ช่องนี้มีดอกอยู่แล้ว ข้ามไป
# "ไม่มีเพื่อนบ้าน" ถือว่า "เพื่อนบ้านว่าง"
# or จะข้ามการอ่าน index ทันทีถ้าเงื่อนไขแรกจริงแล้ว จึงไม่มีทางอ่านเกินขอบ
left_ok = (i == 0) or (flowerbed[i - 1] == 0)
right_ok = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
if left_ok and right_ok:
flowerbed[i] = 1 # ต้องเขียนจริง เพื่อให้ช่องถัดไปเห็น
count += 1
if count >= n:
return True # ครบแล้วออกได้เลย ไม่ต้องกวาดต่อ
return count >= nอ่านโค้ดทีละส่วน
- เช็ค n == 0 ก่อน เพราะโจทย์ยอมให้ n เป็น 0 ซึ่งแปลว่าไม่ต้องปลูกอะไรเลย
- ถ้าช่องนี้ไม่ว่างก็ข้ามทันที ลดเงื่อนไขที่ต้องคิดในบรรทัดถัดไป
- left_ok และ right_ok ใช้ or นำหน้าเพื่อกันการอ่านตำแหน่งเกินขอบแถว
- flowerbed[i] = 1 ต้องเขียนจริง ไม่ใช่แค่ count += 1 เพราะช่องถัดไปต้องเห็นว่าซ้ายมือมีดอกแล้ว
- return True ทันทีที่ครบ n เพื่อไม่กวาดต่อโดยไม่จำเป็น
ต้นทุน
เวลา O(n) กวาดแปลงรอบเดียว · หน่วยความจำ O(1) เพราะใช้ตัวแปรนับตัวเดียวและแก้ในแถวเดิม
โค้ดข้างบนแก้ flowerbed ที่รับเข้ามาจริง ซึ่ง LeetCode ยอมรับ แต่ถ้าอยู่ในโค้ดจริงและไม่ต้องการให้ค่าของผู้เรียกเปลี่ยน ให้ทำสำเนาด้วย flowerbed = flowerbed[:] ตอนต้นฟังก์ชัน แลกกับหน่วยความจำ O(n)
เช็คลิสต์ก่อนกดส่ง
- ทดสอบ [0] กับ n=1 ต้องได้ true (ช่องเดียวโดด ๆ ไม่มีเพื่อนบ้านเลย)
- ทดสอบ [0,0,1] ซึ่งเป็นเคสที่จับบั๊ก bed[i-1] ตอน i=0
- ทดสอบ [1,0,0,0,1] กับ n=2 ต้องได้ false
- เช็คว่าเขียน 1 ลงช่องที่ปลูกจริง ไม่ใช่แค่เพิ่มตัวนับ
- เช็คว่ารองรับ n = 0