用 Python 编写程序来计算步行走过 k 次的块数

pythonserver side programmingprogramming更新于 2026/1/20 6:04:17

假设我们有两个列表，分别称为 walks 和 target。一开始，我们在一条一维线中的位置 0。现在 |walks[i]| 表示已经走过的步数。当 walk[i] 为正时，表示向右行走，为负时表示向左行走。当我们行走时，我们移动一个块，即下一个或上一个整数位置。我们必须找到至少被走过目标次数的块数。

因此，如果输入为 walks = [3, -7, 2] target = 2，则输出将为 5，从下图中，我们可以看到 [0, 1], [1, 2], [2, 3], [-4, -3], [-3, -2] 被覆盖了 k = 2 次。

为了解决这个问题，我们将遵循以下步骤 −

pos := 0
jumps := a hash map，其中当 key 不存在时默认值为 0
对于 walks 中的每个 dist，执行
- jumps[pos] := jumps[pos] + 1 如果 dist > 0 否则 -1
- jumps[pos + dist] := jumps[pos + dist] - 1 如果 dist > 0 否则 -1
- pos := pos + dist
lastpos := 0
level := 0
total := 0
对于 jumps 的排序键值对中的每个位置 pos 和值 val，执行
- 如果 level >= target，则
  - total := total + pos - lastpos
- level := level + val
- lastpos := pos
return total

示例

让我们看看下面的实现以便更好地理解 −

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))