主題

LeetCode - 1954. Minimum Garden Perimeter to Collect Enough Apples 解題心得

Not In My Back Yard | 2021-12-31 00:00:03 | 巴幣 2 | 人氣 97

題目連結:


題目意譯:
在一個以一個無限二維網格表示的花園中,每個格子點都種有一棵蘋果樹。位於整數座標 (i, j) 的蘋果樹有著 |i| + |j| 顆蘋果長在上面。

你將會買下一個與座標軸對齊的正方形地號(Plot of Land),其中心位於 (0, 0)。

給定一整數 neededApples,回傳地號的最小周長使得至少有著 neededApples 顆蘋果位於地號的內部或是邊上。

|x| 之值定義為
x 如果 x ≧ 0
-x 如果 x < 0

限制:
1 ≦ neededApples ≦ 10 ^ 15



範例測資:
範例 1:
輸入: neededApples = 1
輸出: 8
解釋: 一個邊長為 1 的地號不包含任何蘋果。
不過一個邊長為 2 的正方形地號內部有著 12 顆蘋果(如上圖所示)。
周長為 2 × 4 = 8。

範例 2:
輸入: neededApples = 13
輸出: 16

範例 3:
輸入: neededApples = 1000000000
輸出: 5040


解題思維:
因為題目所述的地號可以視為:座標平面上由四個象限各一個正方形拼湊而成,其中一個頂點為原點、邊與軸對齊且邊長皆為 k。

因此我們只需要算出其中一塊邊長 k(例如說第一象限(右上角)的正方形,而其右上角頂點將位於 (k, k))中含有的蘋果樹(暫時忽略座標軸上的蘋果樹)。將其乘以 4 再把座標軸上的蘋果數量加回來便可以得到整塊地號所含有的蘋果總數。

因為要暫且忽略座標軸上的蘋果樹,因此我們需要討論第一象限中左下角為 (1, 1)、右上角為 (k, k) 這個正方形中含有多少蘋果。可以看到,蘋果數量分布如下圖所示:
可以看到這個正方形是鏡像的(左上到右下,以左下到右上那條對角線作為翻轉線)。因此我們只需要求出藍色三角形部分的蘋果數量 × 2 + 橘色對角線蘋果數即可得到總數。

而藍色三角形部分的蘋果數量 X 之值為

因此兩個藍色三角形的蘋果數即為
k(k + 1)(k - 1)
顆。再加上橘色對角線部分的蘋果 k(k + 1) 顆後便可以得到整個正方形有
k ^ 2 × (k + 1)
顆蘋果。

因此整個地號的蘋果數即是四個正方形 + 座標軸上四個方向的蘋果(總計 2k(k + 1) 顆),即
2k(k + 1)(2k + 1)



接著我們只需要利用二分搜尋法(Binary Search)哪個 k 值是第一個使得上式 ≧ neededApples。不過其實窮舉 k 也可以,因為根據 neededApples 的範圍,k 不會超過 65536。

找到 k 值後,因為 k 是單一一個正方形的邊長,因此 8k 即為所求的整塊土地的周長。




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

創作回應

相關創作

更多創作