สมมติว่าเรามีสองรายการที่เรียกว่าการเดินและเป้าหมาย ที่จุดเริ่มต้น เราอยู่ที่ตำแหน่ง 0 ในเส้นหนึ่งมิติ ตอนนี้ |เดิน[i]| แสดงถึงจำนวนก้าวที่เดิน และเมื่อเดิน[i] เป็นบวก แสดงว่าเดินถูกต้อง และลบไปทางซ้าย เมื่อเราเดิน เราจะย้ายหนึ่งช่วงตึก นั่นคือตำแหน่งจำนวนเต็มถัดไปหรือก่อนหน้า เราต้องหาจำนวนบล็อกที่เดินตามจำนวนเป้าหมายเป็นอย่างน้อย
ดังนั้น ถ้า input เหมือนกับ walks =[3, -7, 2] target =2 แล้ว output จะเป็น 5 จากรูปต่อไปนี้ เราจะเห็น [0, 1], [1, 2], [2 , 3], [-4, -3], [-3, -2] ครอบคลุม k =2 ครั้ง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตำแหน่ง :=0
- กระโดด :=แผนที่แฮช โดยที่ค่าเริ่มต้นคือ 0 เมื่อไม่มีคีย์
- สำหรับการเดินแต่ละเขต ให้ทำ
- jumps[pos] :=jumps[pos] + 1 if dist> 0 มิฉะนั้น -1
- กระโดด[pos + dist] :=กระโดด[pos + dist] - 1 ถ้า dist> 0 มิฉะนั้น -1
- pos :=pos + dist
- lastpos :=0
- ระดับ :=0
- รวม :=0
- สำหรับแต่ละตำแหน่ง pos และค่า 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))
อินพุต
[3, -7, 2], 2
ผลลัพธ์
5
