Python程序：计算行走过程中被覆盖k次的方块数量

假设我们有两个列表，分别称为walks和target。一开始我们在一个一维线上的位置0。|walks[i]|表示已行走步数。walk[i]为正表示向右走，为负表示向左走。行走时，我们移动一个方块，即下一个或上一个整数位置。我们需要找到至少被行走target次以上的方块数量。

例如，如果输入为walks = [3, -7, 2]，target = 2，则输出为5。如下图所示，[0, 1]、[1, 2]、[2, 3]、[-4, -3]、[-3, -2]被覆盖了k = 2次。

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

  • pos := 0
  • jumps := 一个哈希映射，当键不存在时，默认值为0
  • 对于walks中的每个dist，执行：
    • 如果dist > 0，则jumps[pos] := jumps[pos] + 1，否则jumps[pos] := jumps[pos] -1
    • 如果dist > 0，则jumps[pos + dist] := jumps[pos + dist] - 1，否则jumps[pos + dist] := jumps[pos + dist] + 1
    • pos := pos + dist
  • lastpos := 0
  • level := 0
  • total := 0
  • 对于jumps排序后的键值对中的每个位置pos和值val，执行：
    • 如果level >= target，则
      • total := total + pos - lastpos
    • level := level + val
    • lastpos := pos
  • 返回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))

输入

[3, -7, 2], 2

输出

5

更新于：2021年10月18日

251 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告