資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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
- 如果level >= target，則
- 返回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 次瀏覽
廣告