โปรแกรมนับบล็อกที่ถูกครอบคลุม k ครั้งจากการเดินใน Python

ปัญหา

ให้รายการ walks และค่า target เริ่มที่ตำแหน่ง 0 บนเส้นจำนวน 1 มิติ |walks[i]| = จำนวนก้าว, ค่าบวก = เดินขวา, ค่าลบ = เดินซ้าย หาจำนวนบล็อก (ช่วงระหว่างจำนวนเต็มติดกัน) ที่ถูกเดินผ่านอย่างน้อย target ครั้ง

ตัวอย่าง

Input: walks = [3, -7, 2], target = 2
Output: 5

# บล็อกที่ถูกเดิน 2 ครั้ง: [0,1], [1,2], [2,3], [-4,-3], [-3,-2]

อัลกอริทึม: Sweep Line / Difference Array

1. pos = 0 ตำแหน่งปัจจุบัน
2. jumps = hash map (defaultdict) เก็บการเปลี่ยนแปลงจำนวนครั้งที่เดินผ่าน
   • เดินขวา (dist > 0): jumps[pos] += 1, jumps[pos+dist] -= 1
   • เดินซ้าย (dist < 0): jumps[pos] -= 1, jumps[pos+dist] += 1
3. pos += dist อัปเดตตำแหน่ง
4. วนลูปตาม key ที่เรียงแล้วของ jumps:
   • level = จำนวนครั้งสะสมที่เดินผ่าน
   • ถ้า level >= target บวก pos - lastpos เข้า total
   • อัปเดต level += val, lastpos = pos

ตัวอย่างโค้ด

from collections import defaultdict

def solve(walks, target):
    pos = 0
    jumps = defaultdict(int)
    
    for dist in walks:
        jumps[pos] += 1 if dist > 0 else -1
        jumps[pos + dist] -= 1 if dist > 0 else -1
        pos += dist
    
    lastpos = level = total = 0
    for pos, val in sorted(jumps.items()):
        if level >= target:
            total += pos - lastpos
        level += val
        lastpos = pos
    
    return total

walks = [3, -7, 2]
target = 2
print(solve(walks, target))  # Output: 5

ความซับซ้อน

• เวลา: O(n log n) จากการ sort keys (n = จำนวนจุดเปลี่ยนแปลง ≤ 2*len(walks))
• พื้นที่: O(n)
• ประสิทธิภาพดีกว่าการจำลองทุกก้าวเมื่อระยะทางใหญ่

อินพุต / เอาต์พุต

Input: [3, -7, 2], 2
Output: 5