โปรแกรมสร้างอาร์เรย์โดยการต่อย่อยอาร์เรย์ของอีกอาร์เรย์หนึ่งใน Python

ปัญหา

สมมติว่ามีอาร์เรย์ 2 มิติชื่อ groups และอีกอาร์เรย์หนึ่งชื่อ nums เราต้องตรวจสอบว่าเราสามารถเลือก n ย่อยอาร์เรย์ที่ไม่ทับซ้อนกันจาก nums ได้หรือไม่ โดยที่ย่อยอาร์เรย์ตัวที่ i ต้องเท่ากับ groups[i] (ดัชนีเริ่มจาก 0) และถ้า i > 0 ย่อยอาร์เรย์ตัวที่ (i-1) จะต้องปรากฏก่อนย่อยอาร์เรย์ตัวที่ i ใน nums

ตัวอย่าง

ถ้าอินพุตเป็น groups = [[2,-2,-2],[4,-3,0]] และ nums = [1,-1,0,2,-2,-2,4,-3,0] ผลลัพธ์จะเป็น true เพราะ group[0] อยู่ที่ดัชนี 3 ถึง 5 ของ nums และ group[1] อยู่ที่ดัชนี 6 ถึง 8

ขั้นตอนการแก้ปัญหา

1. กำหนด i := 0
2. สำหรับแต่ละ grp ใน groups:
   • วนลูป j จาก i ถึงขนาดของ nums - 1:
     • ถ้าย่อยอาร์เรย์ของ nums จากดัชนี j ถึง j + ขนาดของ grp เท่ากับ grp:
       • อัปเดต i := j + ขนาดของ grp
       • ออกจากลูปใน
     • มิฉะนั้น คืนค่า False
3. คืนค่า True

การนำไปใช้งาน (Python)

def solve(groups, nums):
    i = 0
    for grp in groups:
        for j in range(i, len(nums)):
            if nums[j:j+len(grp)] == grp:
                i = j + len(grp)
                break
        else:
            return False
    return True

groups = [[2,-2,-2],[4,-3,0]]
nums = [1,-1,0,2,-2,-2,4,-3,0]
print(solve(groups, nums))

อินพุต

[[2,-2,-2],[4,-3,0]], [1,-1,0,2,-2,-2,4,-3,0]

เอาต์พุต

True