数据结构
网络
关系数据库管理系统(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次
广告