題目連結:
題目意譯:
現在存在著一個無限大的二維且未塗色的網格。你被給定一個正整數 n,其代表著你接下來的 n 分鐘必須執行以下固定動作:
在第一分鐘,將任意格子塗成藍色;
其後每一分鐘,將所有碰到藍色格子的未塗色格子全部塗著藍色。
以下為一個在第 1 、 2 和 3 分鐘後的網格之圖示。
回傳 n 分鐘後有塗色的格子總數。
限制:
1 ≦ n ≦ 10 ^ 5
範例測資:
範例 1:
輸入: n = 1
輸出: 1
解釋: 1 分鐘後,只有 1 個藍色格子存在。所以我們回傳 1。
範例 2:
輸入: n = 2
輸出: 5
解釋: 2 分鐘後,邊界上有 4 個已塗色之格子,而中心則有 1 個。所以我們回傳 5。
解題思維:
可以看到每一分鐘新塗色的格子之數列為
1 、 4 、 8 、 …… 、 4n - 4
而 4i - 4 這個通式除了 i = 1 以外的分鐘數皆適用。
因此如果先不考慮第 1 分鐘的格子只考慮通式的話,數列應為
0 、 4 、 8 、 …… 、 4n - 4
因為所求為有顏色的格子之總數,所以要求上述數列之級數和。而這是一個等差數列,因此可以直接套用等差公式得到
(4n - 4) * n ÷ 2
化簡可得
2n ^ 2 - 2n
最後再把第 1 分鐘的格子加回去便可以得到公式解
2n ^ 2 - 2n + 1
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。