資料結構
網路
關係資料庫管理系統
作業系統
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次檢視
廣告