数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中的糖果
假设有N个孩子，他们排成一列。每个孩子都被分配了一个评级值。我们根据以下要求向这些孩子提供糖果：
每个孩子至少要有一颗糖果。
评级高的孩子比他们邻居获得的糖果多。
我们必须找到我们必须提供的最少糖果数量？
因此，如果输入类似于[1,1,3]，则输出将为4。因此，他们将分别获得1、1和2颗糖果。
为了解决这个问题，我们将遵循以下步骤：
n：=数组ratings的大小，创建一个名为dp的数组，大小为n，使用1填充它
ret：= 0
对于范围1到n – 1中的i
如果ratings[i] > ratings[i – 1]，则dp[i]：= dp[i - 1] + 1
对于范围n - 2到0中的i
如果ratings[i] > ratings[i + 1]，则dp[i]：= dp[i]和dp[i + 1] + 1的最大值
ret：= dp元素的总和
返回ret
示例（C++）
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector <int> dp(n, 1);
int ret = 0;
for(int i = 1; i < n; i++){
if(ratings[i] > ratings[i - 1]){
dp[i] = dp[i - 1] + 1;
}
}
for(int i = n - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]){
dp[i] = max(dp[i], dp[i + 1] + 1);
}
}
for(int i = 0; i < n; i+=1){
ret += dp[i];
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,1,3};
cout << (ob.candy(v));
}输入
[1,1,3]
输出
4
更新于： 2020年5月26日
464次查看
广告