Pythonで歩くことによってk回カバーされるブロックの数を数えるプログラム

ウォークとターゲットという2つのリストがあるとします。最初は、1次元の線の位置0にいます。今|歩く[i]|歩いた歩数を表します。そして、walk [i]が正の場合、右に歩いたことを示し、左に負の場合を示します。歩くとき、1つのブロック、つまり次または前の整数位置を移動します。少なくとも目標回数だけ歩いたブロックの数を見つける必要があります。

したがって、入力がwalks =[3、-7、2] target =2の場合、出力は5になります。次の図から、[0、1]、[1、2]、[2 、3]、[-4、-3]、[-3、-2]はk=2回カバーされます。

これを解決するには、次の手順に従います-

• pos：=0
• ジャンプ：=ハッシュマップ。キーが存在しない場合、デフォルト値は0です。
• 散歩の距離ごとに、
  • ジャンプ[pos]：=ジャンプ[pos] + 1（dist> 0の場合）それ以外の場合-1
  • jumps [pos + dist]：=jumps [pos +dist]-dist>0の場合は1、それ以外の場合は-1
  • pos：=pos + dist
• lastpos：=0
• レベル：=0
• 合計：=0
• 各位置pos、およびソートされたキーと値のジャンプのペアの値valについて、実行します
  • レベル>=ターゲットの場合、
    • 合計：=合計+位置-最後の位置
  • level：=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))

入力

[3, -7, 2], 2

出力

5