資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 中的旋轉函式
假設我們給定一個整數陣列 A，設 n 為陣列 A 的長度。現在假設 Bk 是透過將陣列 A 順時針旋轉 k 個位置獲得的陣列。這裡的旋轉可以定義為：
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(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
最大值是 26。
為了解決這個問題，我們將遵循以下步驟：
n := 陣列 A 的大小，如果 n 為 0，則返回 0
ret := 0，建立兩個大小為 n 的陣列，它們分別是 right 和 left
left[0] := A[0]
對於 i 從 1 到 n – 1
left[i] := left[i] + left[i – 1]
left[i] := left[i] + A[i]
right[n – 1] := A[n – 1]
對於 i 從 n – 1 到 0
right[i] := right[i] + right[i + 1]
right[i] := right[i] + A[i]
rightMul := 0, cnt := n – 1
對於 i 從 n – 1 到 1
rightMul := rightMul + A[i] * cnt
cnt 減 1
建立一個大小為 n 的陣列 x
對於 i 從 0 到 n – 2
x[i] := rightMul
rightMul := rightMul – right[i + 1]
leftMul := 0, cnt := 1
對於 i 從 0 到 n – 2
leftMul := leftMul + A[i] * cnt
cnt 加 1
cnt 減 1
對於 i 從 n – 1 到 1
x[i] := x[i] + leftMul
leftMul := leftMul – A[i – 1] * cnt
如果 i – 2 >= 0，則 leftMul := leftMul + left[i – 2]
返回 x 的最大值
示例 (C++)
讓我們看看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
lli n = A.size();
if(n == 0) return 0;
lli ret = 0;
vector <lli>right(n);
vector <lli> left(n);
left[0] = A[0];
for(lli i = 1; i < n; i++){
left[i] += left[i - 1];
left[i] += A[i];
}
right[n - 1] = A[n - 1];
for(lli i = n - 2; i >= 0; i--){
right[i] += right[i + 1];
right[i] += A[i];
}
lli rightMul = 0;
lli cnt = n - 1;
for(lli i = n - 1; i > 0; i--){
rightMul += (A[i] * cnt);
cnt--;
}
vector <lli> x(n);
for(lli i = 0; i < n - 1; i++){
x[i] = rightMul;
rightMul -= right[i + 1];
}
lli leftMul = 0;
cnt = 1;
for(lli i = 0; i < n - 1; i++){
leftMul += A[i] * cnt;
cnt++;
}
cnt--;
for(lli i = n - 1; i >= 1; i--){
x[i] += leftMul;
leftMul -= (A[i - 1] * cnt);
if(i - 2 >= 0) leftMul += left[i - 2];
}
ret = INT_MIN;
for(lli i = 0; i < x.size(); i++) ret = max(ret, x[i]);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {4,3,2,6};
cout <<(ob.maxRotateFunction(v));
}輸入
[4,3,2,6]
輸出
26
266 次瀏覽
