【leetcode】396 Rotate Function

发表于 | 分类于 ，

旋转数组，求最小和


描述

给定一个整数数组A，让n为其长度。
假设Bk是通过按时钟方向旋转阵列A k位置而获得的阵列，我们在A上定义如下的“旋转函数”F：
f（k）＝0＊bk〔0〕＋1＊bk〔1〕＋…+（n-1）*bk[n-1 ]。
计算f（0）、f（1）、…、f（n-1）的最大值。
注：n保证小于105。

样例

1
2
输入: [4, 3, 2, 6]
输出: 26

思路

建立一个长度为之前数组两倍长度的数组，保存两个之前的数组，之后遍历求和，很简单，很慢。

vector<vector> test ;test.push_back(vector{INT_MIN} 居然报错！emmm

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int calsum(vector<int>& A) {
        int len = A.size();
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += i * A[i];
        }
        return sum;
    }

    int maxRotateFunction(vector<int>& A) {
        int len = A.size();
        if (len == 0) { return 0; }
        vector<int> doubleA;

        for (int i = 0; i < 2 * len; i++) {
            doubleA.push_back(A[i%len]);
        }

        int maxsum = INT_MIN;
        for (int i = 0 ; i < len; i++) {
            vector<int> moveArray(doubleA.begin()+i, doubleA.begin() + i+len);
            int t = calsum(moveArray);
            maxsum = (maxsum > t) ? maxsum : t;
        }
        return maxsum;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        const int N = A.size();
        int sum = 0;
        int f = 0;
        for (int i = 0; i < N; i++) {
            sum += A[i];
            f += i * A[i];
        }
        int ans = f;
        for (int i = 1; i < N; i++) {
            f = f - sum + N * A[i - 1];
            ans = max(ans, f);
        }
        return ans;
    }
};

参考

原题链接