資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：找出跑酷運動員所能到達的最遠建築物
假設有n棟不同高度的房屋，一位跑酷運動員想要藉助磚塊和梯子從一棟房屋移動到另一棟房屋。房屋的高度以陣列的形式給出。每個磚塊的高度為一個單位長度，我們有少量磚塊。我們只能使用一次梯子和磚塊。我們必須找出跑酷運動員所能到達的最遠建築物。
因此，如果輸入類似於heights = [5, 8, 7, 6, 2, 3, 1, 4]，bricks = 3，ladders = 2，則輸出將為7。
運動員從建築物0開始。
他藉助3塊磚塊到達建築物1。
由於後續建築物比之前的建築物矮，他跳到建築物2、3、4。
他使用梯子從建築物4到達建築物5。
由於建築物6比建築物5矮，他從建築物5跳到建築物6。
他使用最後一個梯子到達建築物7。
為了解決這個問題，我們將遵循以下步驟：
temp := 新建一個堆
for i in range 1 to size of heights, do
dist := heights[i] - heights[i - 1]
if dist > 0, then
bricks := bricks - dist
將值 -dist 推入堆temp
if bricks < 0, then
ladders := ladders - 1
bricks := bricks - 從堆temp中移除的最小元素
if bricks < 0 or ladders < 0, then
return i - 1
return size of heights - 1
示例
讓我們看看下面的實現，以便更好地理解：
from heapq import heappush, heappop
def solve(heights, bricks, ladders):
temp = []
for i in range(1, len(heights)):
dist = heights[i] - heights[i - 1]
if dist > 0:
bricks -= dist
heappush(temp, -dist)
if bricks < 0:
ladders -= 1
bricks -= heappop(temp)
if bricks < 0 or ladders < 0:
return i - 1
return len(heights) - 1
print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))輸入
[5, 8, 7, 6, 2, 3, 1, 4], 3, 2
輸出
7
更新於：2021年10月6日
瀏覽量：134
廣告