LeetCode Rotate Function

· 691 words · 2 minute read
2017年8月
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 = [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 超时

最简单的根据公式来直接求解，在第16个样例上超时了，一开始我就纳闷了，感觉这道medium题好水，呵呵，原来是我自己想多了，是自己low… 不多说，先给出超时解。

public class Solution {
    public int maxRotateFunction(int[] A) {
        if(A == null || A.length == 0){
            return 0;
        }
        int[] num = new int[A.length];

        int p = 0;
        for(int i = 0; i < A.length; i++){
            for(int j = 0; j < A.length; j++){
                num[i] = num[i] + j*A[(p++)%A.length];
            }
            p = (i + A.length-1)%A.length;
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < A.length; i++){
            max = Math.max(max,num[i]);
        }
        return max;
    }
}

方法2

网上LeetCode大神已经说得很清楚简单了，就直接参考了

Consider we have 5 coins A,B,C,D,E

According to the problem statement

F(0) = (0A) + (1B) + (2C) + (3D) + (4E)

F(1) = (4A) + (0B) + (1C) + (2D) + (3E)

F(2) = (3A) + (4B) + (0C) + (1D) + (2*E)

We can construct F(1) from F(0) by two step: Step 1. taking away one count of each coin from F(0), this is done by subtracting “sum” from “iteration” in the code below

after step 1 F(0) = (-1A) + (0B) + (1C) + (2D) + (3*E)

Step 2. Add n times the element which didn’t contributed in F(0), which is A. This is done by adding “A[j-1]len” in the code below.

after step 2 F(0) = (4A) + (0B) + (1C) + (2D) + (3E)

At this point F(0) can be considered as F(1) and F(2) to F(4) can be constructed by repeating the above steps.

个人感觉这个样例也给的不是很好，如果按顺序给出的话，可能会较容易的看出，当然作为medium题型，这也算增加难度吧。。。

public class Solution {
    public int maxRotateFunction(int[] A) {
        if(A == null || A.length == 0){
            return 0;
        }
        int round = 0;
        int sum = 0;
        for(int i = 0; i < A.length; i++){
            sum = sum + i*A[i];
            round = round + A[i];
        }
        int max = sum;
        int newm = 0;
        for(int i = 1; i < A.length; i++){
            sum = sum - round + A.length*A[i-1];
            max = Math.max(max,sum);
        }
        return max;
    }
}
Share