Leetcode Answers 396

接着刷题,这是一道长着矩阵相乘的脸的代数题。

题目:
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 10^5.

Example:

1
2
3
4
5
6
7
8
A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

思路:
这道题长着一副算 1 x n 与n x n 的矩阵相乘的结果向量里最大值的脸,但是直觉就会告诉我们,这不是该出现在Leetcode里的问题,而且那个10^5也明说了,没那么大地方给你算。

换个思路,我们把这几个F(x)换个方式写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
F(0) = 0a + 1b + 2c + 3d
F(1) = 3a + 0b + 1c + 2d
F(2) = 2a + 3b + 0c + 1d
F(3) = 1a + 2b + 3c + 0d
=>
F(1) - F(0) = 3a - b - c - d = 4a - (a + b + c + d)
F(2) - F(1) = 3b - a - c - d = 4b - (a + b + c + d)
F(3) - F(2) = 3c - a - b - d = 4c - (a + b + c + d)
=>
F(m) - F(m-1) = n * n(m-1) - sum(n)

所以写到这就很明显了,求出sum,有了length,就可以迭代地算出所有的F(m),再找其中的max就可以了。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int MaxRotateFunction(int[] A) {
int sum = 0;
int len = A.Length;
for(int i = 0; i<len; ++i) sum+= A[i];
int init = 0;
for(int i = 0; i<len; ++i) init+= i*A[i];
int max = init;
for(int i = 1; i<len; ++i){
int curr = init - sum + len * A[i-1];
max = curr > max ? curr : max;
init = curr;
}
return max;
}
}

考察:很多数学问题都是长了一副复杂的脸,然后用各种代数方法能把它变成另一类方法更简单的计算的。

以上。

17-04-27
@Sturbridge