ข้อ 3 · LC1431 Kids With the Greatest Number of Candies 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

สำหรับเด็กแต่ละคน ถ้าได้ลูกอมพิเศษ extraCandies ทั้งหมดคนเดียว จะมีลูกอมมากที่สุดในกลุ่มหรือไม่

มีเด็กยืนเรียงกันอยู่ n คน เด็กคนที่ i ถือลูกอมอยู่ candies[i] เม็ด และเรามีลูกอมพิเศษอีกก้อนหนึ่งจำนวน extraCandies เม็ด

จงตอบทีละคนว่า ถ้ายกลูกอมพิเศษก้อนนี้ให้เด็กคนนั้นไปทั้งก้อน เขาจะมีลูกอมมากที่สุดในกลุ่มหรือไม่ (นับว่าเท่ากับคนที่มากที่สุดก็ถือว่าใช่)

คำตอบเป็นลิสต์ของ true/false ที่ยาวเท่ากับจำนวนเด็ก

Example 1

Input:: candies = [2,3,5,1,3], extraCandies = 3
Output:: [true,true,true,false,true]
Explanation:: คนที่ถือเยอะสุดตอนนี้คือ 5 เม็ด ทุกคนจึงต้องไปให้ถึงเลข 5 นี้
เด็กคนที่ 0: 2+3 = 5 เท่ากับ 5 พอดี ซึ่งนับว่าถึงแล้ว จึงเป็น true
เด็กคนที่ 3: 1+3 = 4 ยังไม่ถึง 5 จึงเป็น false
สังเกตว่าเกณฑ์ยังเป็น 5 เท่าเดิมตอนตรวจเด็กคนที่ 3 แม้ว่าเด็กคนที่ 2 จะเพิ่งได้ 8 ไปก็ตาม เพราะแต่ละคำถามเป็นอิสระต่อกัน

Example 2

Input:: candies = [4,2,1,1,2], extraCandies = 1
Output:: [true,false,false,false,false]
Explanation:: เกณฑ์คือ 4 และลูกอมพิเศษมีแค่ 1 เม็ด คนที่ถือ 2 บวกแล้วได้ 3 ยังห่างเกณฑ์อยู่ 1 เม็ด จึงไม่มีใครถึงเลย เหลือแค่เจ้าของเกณฑ์เองที่ 4+1 = 5

Example 3

Input:: candies = [12,1,12], extraCandies = 10
Output:: [true,false,true]
Explanation:: เคสนี้มีคนถือ 12 เท่ากันสองคนตั้งแต่แรก ทั้งคู่บวก 10 แล้วได้ 22 ซึ่ง >= 12 จึงเป็น true ทั้งคู่
นี่คือเคสที่ยืนยันว่าคำว่า ที่หนึ่ง ในโจทย์นี้มีได้หลายคนพร้อมกัน

Constraints (ข้อจำกัด)

n == candies.length
2 <= n <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

⏸ ลองเองก่อน 5 นาที

ข้อนี้เป็นข้อง่าย ถ้าเขียนได้เลยก็ดีมาก แต่ขอให้เปิดกล่องสอนอ่านด้วย เพราะมีสองคำในโจทย์ที่ทำให้คนตอบผิดทั้งที่โค้ดดูถูก และมีนิสัยหนึ่งที่ควรฝึกตั้งแต่ข้อง่าย

💡 ใบ้ขั้นที่ 1 — เกณฑ์ที่ต้องเทียบคืออะไร

เด็กคนหนึ่งจะเป็นที่หนึ่งได้ ต้องเทียบกับใคร คำตอบคือเทียบกับคนที่ถือลูกอมมากที่สุดในกลุ่ม ณ ตอนเริ่ม

และเกณฑ์นี้เป็นค่าเดียวที่ใช้ได้กับเด็กทุกคน ไม่ต้องคำนวณใหม่ทีละคน

💡 ใบ้ขั้นที่ 2 — สองคำที่ทำให้ตอบผิด

คำแรก โจทย์บอกว่า มากที่สุด หรือ เท่ากับคนที่มากที่สุด แปลว่าต้องใช้เครื่องหมายไหน

คำที่สอง ลูกอมพิเศษถูกยกให้ลอง แยกกันทีละคน ไม่ได้ให้จริง เด็กคนอื่นจึงยังถือจำนวนเดิมตลอด เกณฑ์จึงไม่เปลี่ยนระหว่างวน

💡 ใบ้ขั้นที่ 3 — โครงทั้งหมด

python

best = ___(candies)                      # เกณฑ์ หาครั้งเดียวก่อนเข้าลูป
return [c + extraCandies ___ best for c in candies]   # ใช้เครื่องหมายอะไร

🧭 กล่องสอน — ไล่ตั้งแต่ศูนย์ทีละขั้น (เปิดเมื่อพร้อม)

ขั้นที่ 1 · โจทย์นี้ขออะไรจริง ๆ

ข้อนี้โค้ดสั้นมาก แต่มีสองคำในโจทย์ที่ถ้าอ่านผ่านจะตอบผิดทั้งที่โค้ดดูสวย

คำแรกคือคำว่า แยกกัน ลูกอมพิเศษก้อนเดียวนี้ถูกยกให้ลองกับเด็กทุกคนแบบเป็นเอกเทศ ไม่ได้แบ่งกัน และไม่ได้ให้จริง

แปลว่าตอนเราตรวจเด็กคนที่ 3 เด็กคนที่ 0 ถึง 2 ยังถือจำนวนเดิมเสมอ เกณฑ์จึงไม่ขยับเลยทั้งลูป

คำที่สองคือ มากที่สุด หรือ เท่ากับคนที่มากที่สุด ซึ่งเปิดช่องให้มีที่หนึ่งหลายคนพร้อมกันได้

ขั้นที่ 2 · ลองทำด้วยมือก่อนเขียนโค้ด

ใช้เคส candies = [2,3,5,1,3] และ extraCandies = 3 คนที่ถือเยอะสุดตอนนี้คือ 5 จึงเป็นเกณฑ์

ไล่ทีละคน เทียบกับเกณฑ์เดียวกันตลอดpython

candies, extra = [2,3,5,1,3], 3
best = max(candies)
print("คนที่ถือเยอะสุดตอนนี้ =", best)
res = []
for i, c in enumerate(candies):
    ok = c + extra >= best
    print(f"  เด็กคนที่ {i}: ถือ {c} + {extra} = {c+extra} เทียบเกณฑ์ {best} -> {ok}")
    res.append(ok)
print("คำตอบ:", res)

Output

คนที่ถือเยอะสุดตอนนี้ = 5
  เด็กคนที่ 0: ถือ 2 + 3 = 5 เทียบเกณฑ์ 5 -> True
  เด็กคนที่ 1: ถือ 3 + 3 = 6 เทียบเกณฑ์ 5 -> True
  เด็กคนที่ 2: ถือ 5 + 3 = 8 เทียบเกณฑ์ 5 -> True
  เด็กคนที่ 3: ถือ 1 + 3 = 4 เทียบเกณฑ์ 5 -> False
  เด็กคนที่ 4: ถือ 3 + 3 = 6 เทียบเกณฑ์ 5 -> True
คำตอบ: [True, True, True, False, True]

ดูเด็กคนที่ 0 ให้ดี เขาได้ 5 พอดี เท่ากับเกณฑ์ ซึ่งโจทย์นับว่าใช่ นี่คือจุดที่คำว่า เท่ากับ มีผลจริง

และสังเกตว่าตอนตรวจเด็กคนที่ 3 เกณฑ์ยังเป็น 5 เท่าเดิม แม้เด็กคนที่ 2 จะเพิ่งได้ 8 ไป เพราะแต่ละคำถามเป็นอิสระต่อกัน

ขั้นที่ 3 · กับดักที่ 1 — ใช้ > แทน >=

ถ้าอ่านโจทย์เร็วเกินไปจะเขียนเป็น มากกว่า ซึ่งตัดเคสเท่ากับออกไป ลองดูผลต่าง

เทียบ > กับ >=python

def wrong(candies, extra):
    best = max(candies)
    return [c + extra > best for c in candies]

def right(candies, extra):
    best = max(candies)
    return [c + extra >= best for c in candies]

for c, e in [([2,3,5,1,3],3), ([12,1,12],10)]:
    print(f"candies={c} extra={e}")
    print(f"   ใช้ >  -> {wrong(c,e)}")
    print(f"   ใช้ >= -> {right(c,e)}  <- ถูก")

Output

candies=[2, 3, 5, 1, 3] extra=3
   ใช้ >  -> [False, True, True, False, True]
   ใช้ >= -> [True, True, True, False, True]  <- ถูก
candies=[12, 1, 12] extra=10
   ใช้ >  -> [True, False, True]
   ใช้ >= -> [True, False, True]  <- ถูก

เคสที่สองให้ผลตรงกันทั้งสองแบบ ซึ่งเป็นกับดักซ้อนกับดัก คือถ้าเทสต์ด้วยเคสนี้เคสเดียวจะไม่เห็นบั๊กเลย

ขั้นที่ 4 · กับดักที่ 2 — เผลอแก้ลิสต์ต้นฉบับ

อีกกับดักที่เจอบ่อยคือเข้าใจว่า ให้จริง แล้วเขียนบวกลงลิสต์ตรง ๆ ซึ่งทำให้เกณฑ์เปลี่ยนไปเรื่อย และลิสต์ต้นฉบับพังไปด้วย

อาการเมื่อเผลอแก้ลิสต์ที่รับเข้ามาpython

def wrong2(candies, extra):
    out = []
    for i in range(len(candies)):
        candies[i] += extra          # เผลอแก้ลิสต์จริง
        out.append(candies[i] >= max(candies))
    return out

c = [2,3,5,1,3]
print("candies ก่อน:", c)
print("ผล:", wrong2(c, 3))
print("candies หลัง:", c, "<- ลิสต์ต้นฉบับถูกแก้ไปแล้ว")

Output

candies ก่อน: [2, 3, 5, 1, 3]
ผล: [True, True, True, False, False]
candies หลัง: [5, 6, 8, 4, 6] <- ลิสต์ต้นฉบับถูกแก้ไปแล้ว

คำตอบผิดสองตำแหน่ง และลิสต์ที่ผู้เรียกส่งมาก็เปลี่ยนไปด้วย นี่คือเรื่อง aliasing จากส่วนที่ 1 ของหน้าแนวคิดโดยตรง

นิสัยที่ควรติดตั้งแต่ข้อง่าย

ถ้าไม่จำเป็น อย่าแก้ลิสต์ที่รับเข้ามาเป็น argument เพราะผู้เรียกอาจยังต้องใช้ค่าเดิมอยู่ ข้อนี้ n แค่ 100 จะพลาดหรือไม่พลาดก็ผ่าน แต่นิสัยนี้จะช่วยชีวิตในข้อที่ซับซ้อนกว่า

ขั้นที่ 5 · ทำไมต้องหา max ก่อนเข้าลูป

ถ้าเขียน max(candies) ไว้ ข้างใน ลูป โปรแกรมจะไล่หาค่าสูงสุดใหม่ทุกรอบ ทั้งที่ค่านั้นไม่เคยเปลี่ยน

งานจึงกลายเป็น n คูณ n แทนที่จะเป็น n บวก n ข้อนี้ n เล็กจนไม่รู้สึก แต่เป็นนิสัยเดียวกับที่ทำให้ข้ออื่นรันไม่ทัน

หลักที่ใช้ได้ทั่วไปคือ ค่าที่ไม่เปลี่ยนระหว่างลูป ให้คำนวณครั้งเดียวก่อนเข้าลูป

🔓 เฉลยเต็ม พร้อมอธิบายทีละบรรทัด (ลองเองก่อนนะ)พับไว้ด้านใน — คลิกเมื่อพร้อมดู

คำตอบpython

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        best = max(candies)     # เกณฑ์ หาครั้งเดียวก่อนเข้าลูป เพราะไม่เคยเปลี่ยน

        # >= เพราะโจทย์นับ "เท่ากับคนที่มากที่สุด" ว่าใช่ด้วย
        # ไม่แก้ค่าใน candies เลย เพราะลูกอมพิเศษเป็นแค่การสมมติ
        return [c + extraCandies >= best for c in candies]

อ่านโค้ดทีละส่วน

max(candies) หาเกณฑ์ครั้งเดียว เพราะเด็กคนอื่นไม่เคยได้ลูกอมเพิ่มจริง เกณฑ์จึงคงที่
วนเทียบทีละคนด้วย c + extraCandies เป็นการสมมติว่าให้คนนี้ ไม่ได้เขียนกลับลงลิสต์
ใช้ >= ไม่ใช่ > เพราะเท่ากับคนที่มากที่สุดก็นับว่าใช่
เขียนเป็น list comprehension ได้เพราะแต่ละคำตอบไม่ขึ้นกับคำตอบของคนอื่น

ต้นทุน

เวลา O(n) คือกวาดหา max หนึ่งรอบ แล้ววนสร้างคำตอบอีกหนึ่งรอบ · หน่วยความจำ O(n) สำหรับลิสต์คำตอบ ซึ่งเลี่ยงไม่ได้เพราะโจทย์ขอลิสต์กลับมา

เช็คลิสต์ก่อนกดส่ง

ใช้ >= ไม่ใช่ >
หา max ไว้ก่อนเข้าลูป ไม่ใช่เรียกซ้ำในลูป
ไม่แก้ค่าใน candies ที่รับเข้ามา
ทดสอบเคสที่มีคนถือสูงสุดเท่ากันหลายคน เช่น [12,1,12] ต้องได้ true ทั้งสองคนนั้น