Giả sử chúng ta có hai danh sách được gọi là đi bộ và mục tiêu. Lúc đầu, chúng ta đang ở vị trí 0 trên đường một chiều. Bây giờ | đi [i] | đại diện cho số bước đã được đi bộ. Và khi đi bộ [i] là dương thì biểu thị đi bên phải và âm cho bên trái. Khi chúng ta đi bộ, chúng ta di chuyển một khối, đó là vị trí số nguyên tiếp theo hoặc trước đó. Chúng tôi phải tìm số khối đã được đi trên ít nhất số lần mục tiêu.
Vì vậy, nếu đầu vào giống như walk =[3, -7, 2] target =2, thì đầu ra sẽ là 5, từ hình sau, chúng ta có thể thấy [0, 1], [1, 2], [2 , 3], [-4, -3], [-3, -2] được bao phủ k =2 lần.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- pos:=0
- jumps:=một bản đồ băm, trong đó giá trị mặc định là 0 khi không có khóa
- đối với mỗi lần đi bộ, thực hiện
- jumps [pos]:=jumps [pos] + 1 nếu dist> 0 nếu không -1
- jumps [pos + dist]:=jumps [pos + dist] - 1 nếu dist> 0 nếu không -1
- pos:=pos + dist
- lastpos:=0
- cấp độ:=0
- tổng số:=0
- đối với mỗi vị trí pos và giá trị val trong các cặp bước nhảy khóa-giá trị đã được sắp xếp, hãy thực hiện
- if level> =target, then
- tổng số:=total + pos - lastpos
- level:=level + val
- lastpos:=pos
- if level> =target, then
- tổng trả lại
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[3, -7, 2], 2
Đầu ra
5