LeetCode – 396. Rotate Function

題目來源:LeetCode – 396. Rotate Function


題目:

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

粗略翻譯:

題目會給予一個陣列A,並定義n為A的長度,

假設Bk為旋轉後的A陣列,其中k為順時針旋轉,

我們定義一個旋轉的方法F,定義如下:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

程式需要求出F(0), F(1), ..., F(n-1)中最大的數值為多少並返回。

例如:

解法:

這題可以觀察出其中的規律,並推算出公式

此網站有詳細的教學,我就不重複說明了,

下面我直接套用數字來解釋

我們拿上面的例子來舉例,

A = [4, 3, 2, 6]

F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25

如果我們把F(1) – F(0)代表會得到下列算式:

F(1) – F(0) =  (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2)   (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)

=  (1 * 4) + (1 * 3) + (1 * 2) + ((1 – n) * 6)

= ((1 * 6) + (1 * 4) + (1 * 3) + (1 * 2)) – n * 6

=  (sum) – n * 6

其中sum代表陣列的數值全部相加,n代表陣列長度。

因此

F(1) – F(0) =  (sum) – n * 6

F(1) = F(0) + (sum) – n * 6

F(1) = 25 + 15 – 24

= 16

因此得到公式為:

F(k) = F(k-1) + sum – n * A[n-k]

也就代表我們程式一開始只需要先算出F(0) 以及sum,

之後都可以套用此公式來取得答案

 

 


網站:http://wp.mlab.tw/
GitHub:https://github.com/yoll522/LeetCode
程式碼:https://github.com/yoll522/LeetCode/tree/master/396.%20Rotate%20Function

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *