主題

LeetCode - 1936. Add Minimum Number of Rungs 解題心得

Not In My Back Yard | 2021-12-07 00:00:03 | 巴幣 0 | 人氣 42

題目連結:


題目意譯:
你被給定一個嚴格遞增的整數陣列 rungs,其代表著一個梯子的梯級之高度。你目前位於高度 0 的地板上,而你想要抵達最後一級的梯級。

你同時也被給定一個整數 dist。你只能在目前所在位置(地板或梯級)與下一個梯級的高度差最多不超過 dist 的情況下爬到下一個梯級。你可以在任意正整數高度的位置安插一個梯級,前提是如果那裡不存在著梯級的話。

回傳最少所需安插的梯級數量,使得你可以爬到梯子的最後一個梯級。

限制:
1 ≦ rungs.length ≦ 10 ^ 5
1 ≦ rungs[i] ≦ 10 ^ 9
1 ≦ dist ≦ 10 ^ 9
rungs 為嚴格遞增。



範例測資:
範例 1:
輸入: rungs = [1,3,5,10], dist = 2
輸出: 2
解釋:
你當前無法抵達最後一個梯級。
在高度 7 和 8 安插梯級便可以爬上這個梯子。
梯子現在有著梯級於 [1,3,5,7,8,10]。

範例 2:
輸入: rungs = [3,6,8,10], dist = 3
輸出: 0
解釋:
梯子不需額外的梯級便可以完整攀爬。

範例 3:
輸入: rungs = [3,4,6,7], dist = 2
輸出: 1
解釋:
你當前無法從地板抵達第一個梯級。
在高度 1 安插梯級便可以爬上這個梯子。
梯子現在有著梯級於 [1,3,4,6,7]。

範例 4:
輸入: rungs = [5], dist = 10
輸出: 0
解釋:
梯子不需額外的梯級便可以完整攀爬。


解題思維:
一開始定義一個變數 X 代表到目前的梯級所需要安插的額外梯級之數量以及一個變數 L 代表前一個梯級的高度值。可以看到因為我們一開始在地板上,所以 X = L = 0。

接著我們掃過陣列 rungs。對於每個高度值 rungs[i],當 rungs[i] - L > dist 時,代表我們無法從目前在的高度到達下一個梯級。因此我們需要安插一些額外的梯級,其至少需為
floor((rungs[i] - L - 1) ÷ L)
其中 floor() 為下高斯函數(對於正數來說等價於無條件捨去小數點)。因此 X 之值將會加上上式之值。

然後不論 rungs[i] - L 是否大於 dist,我們都會將 L 之值更新為 rungs[i],代表我們現在成功爬上了第 i 個梯級。

最後的 X 之值即為所求之抵達頂端梯級最少所需之額外梯級數。




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

創作回應

相關創作

更多創作