資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中得分最高的最小旋轉
假設我們有一個數組A，我們可以將其旋轉K位，使得陣列變為A[K]，A[K+1]，A[K+2]，... A[A.length - 1]，A[0]，A[1]，...，A[K-1]。然後，任何小於或等於其索引的條目都值1分。
例如，讓我們有一個數組[2, 4, 1, 3, 0]，我們旋轉K = 2位，它變成[1, 3, 0, 2, 4]。這值3分，因為1 > 0 [不得分]，3 > 1 [不得分]，0 <= 2 [得一分]，2 <= 3 [得一分]，4 <= 4 [得一分]。
我們必須找到K，對於這個K，我們將獲得最高分。如果有多個答案，則返回最小的K索引。因此，如果輸入類似於K = 2，則答案將為5。
因此，如果輸入類似於[2,3,1,5,1]，則輸出將為3，這是因為：
| K | 陣列 | 得分 |
|---|---|---|
| 0 | [2,3,1,5,1] | 2 |
| 1 | [3,1,5,1,2] | 3 |
| 2 | [1,5,1,2,4] | 3 |
| 3 | [5,1,2,4,1] | 4 |
| 4 | [1,2,4,1,3] | 3 |
答案將是3。
為了解決這個問題，我們將遵循以下步驟：
- ret := 0
- n := A的大小
- 定義一個大小為n的陣列cnt
- 初始化i := 0，當i < n時，更新（i增加1），執行：
- 如果A[i] <= i，則：
- minI := 0，（cnt[minI]增加1）
- maxI := i - A[i]
- 如果maxI + 1 < n，則：
- cnt[maxI + 1]減少1
- 如果i + 1 < n，則：
- cnt[i + 1]增加1
- 否則
- 如果A[i] >= n，則：
- 忽略以下部分，跳到下一個迭代
- minI := i + 1
- （cnt[minI]增加1）
- maxI := i + (n - A[i])
- 如果maxI + 1 < n，則：
- cnt[maxI + 1]減少1
- 如果A[i] >= n，則：
- 如果A[i] <= i，則：
- maxCnt := -1，temp := 0
- 初始化i := 0，當i < n時，更新（i增加1），執行：
- temp := temp + cnt[i]
- 如果temp > maxCnt，則：
- maxCnt := temp
- ret := i
- 返回ret
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bestRotation(vector<int>& A) {
int ret = 0;
int n = A.size();
vector <int> cnt(n);
for(int i = 0; i < n; i++){
if(A[i] <= i){
int minI = 0;
cnt[minI]++;
int maxI = i - A[i];
if(maxI + 1 < n) cnt[maxI + 1]--;
if(i + 1 < n) cnt[i + 1]++;
}else{
if(A[i] >= n) continue;
int minI = i + 1;
cnt[minI]++;
int maxi = i + (n - A[i]);
if(maxi + 1 < n)cnt[maxi + 1]--;
}
}
int maxCnt = -1;
int temp = 0;
for(int i = 0; i < n; i++){
temp += cnt[i];
if(temp > maxCnt){
maxCnt = temp;
ret = i;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,3,1,5,1};
cout << (ob.bestRotation(v));
}輸入
[2,3,1,5,1]
輸出
3
更新於：2020年6月2日
瀏覽量128次
廣告