主題

LeetCode - 2079. Watering Plants 解題心得

Not In My Back Yard | 2022-05-16 12:00:08 | 巴幣 0 | 人氣 48

題目連結:


題目意譯:
你想要用澆花器幫你的花園中的 n 株植物澆水。植物們排成一列並且從左至右編號為 0 到 n - 1,其中第 i 株植物位於 x = i。現有一條河位於 x = -1,你可以在那裡裝滿你的澆花器。

每株植物各自需要某特定量的水。而你將會按照以下方式來澆花:
從左至右依序為每株植物澆花。
當澆完目前這株植物後,如果你沒有足夠的水可以完整澆灌下一株植物,則回到河邊將澆花器重新裝滿。
你不得提早重新裝滿澆花器。

你現正位於那條河(即 x = -1)。在 x 軸上移動一單位需要一步。
(譯者注:一開始的澆花器是滿的(或者是全空的,然後依據規則在澆第 0 株植物前裝滿)。這點並沒有寫在原英文題目敘述中。而是只能從範例測資看出來)

給定一個索引值從 0 開始有著 n 個整數的整數陣列 plants,其中 plants[i] 為第 i 株植物需要的水量,以及給定一個整數 capacity 代表著澆花器的容量。回傳將所有植物澆完水所需之步數。

限制:
n == plants.length
1 ≦ n ≦ 1000
1 ≦ plants[i] ≦ 10 ^ 6
max(plants[i]) ≦ capacity ≦ 10 ^ 9



範例測資:
範例 1:
輸入: plants = [2,2,3,3], capacity = 5
輸出: 14
解釋: 開始於河邊並有著裝滿的澆花器:
- 走到植物 0(1 步)並澆花。澆花器剩 3 單位的水。
- 走到植物 1(1 步)並澆花。澆花器剩 1 單位的水。
- 由於無法完整澆灌植物 2,走回到河邊裝滿澆花器(2 步)。
- 走到植物 2(3 步)並澆花。澆花器剩 2 單位的水。
- 由於無法完整澆灌植物 3,走回到河邊裝滿澆花器(3 步)。
- 走到植物 3(4 步)並澆花。
需要步數 = 1 + 1 + 2 + 3 + 3 + 4 = 14。

範例 2:
輸入: plants = [1,1,1,4,2,3], capacity = 4
輸出: 30
解釋: 開始於河邊並有著裝滿的澆花器:
- 為植物 0 、 1 、 2 澆水(3 步)。回到河邊(3 步)。
- 為植物 3 澆水(4 步)。回到河邊(4 步)。
- 為植物 4 澆水(5 步)。回到河邊(5 步)。
- 為植物 5 澆水(6 步)。
需要步數 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30。

範例 3:
輸入: plants = [7,7,7,7,7,7,7], capacity = 8
輸出: 49
解釋: 你在為每株植物澆花前都必須重新裝滿澆花器。
需要步數 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49。


解題思維:
沒什麼特別的,就是單純地模擬即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作