首页 > 代码库 > LeetCode: Candy
LeetCode: Candy
LeetCode: Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
地址：https://oj.leetcode.com/problems/candy/
算法：这道题用动态规划可以解决，之前在王道的练习赛上有遇到过，分析见我之前的一篇文章：http://www.cnblogs.com/boostable/p/online_judge_1470_1549_1493_1550.html
代码：
1 class Solution { 2 public: 3 int candy(vector<int> &ratings) { 4 int n = ratings.size(); 5 vector<int> num_candys(n); 6 if(n == 0) 7 return 0; 8 return subSolution(0,n-1,num_candys,ratings); 9 }10 int subSolution(int s, int e, vector<int> &num_candys,vector<int> &ratings){11 if(s == e){12 num_candys[s] = 1;13 return 1;14 }else{15 int total = 0;16 int mid = (s + e) >> 1;17 int left = subSolution(s,mid,num_candys,ratings);18 int right = subSolution(mid+1,e,num_candys,ratings);19 if(ratings[mid] == ratings[mid+1]){20 return left + right;21 }else if(ratings[mid] > ratings[mid+1]){22 if(num_candys[mid] > num_candys[mid+1])23 return left + right;24 else{25 total += (num_candys[mid+1] + 1 - num_candys[mid]);26 num_candys[mid] = num_candys[mid+1] + 1;27 int totalAdd = 0;28 for(int i = mid-1; i >= s; --i){29 if(ratings[i] <= ratings[i+1] || (ratings[i] > ratings[i+1] && num_candys[i] > num_candys[i+1]))30 break;31 else{32 total += (num_candys[i+1] + 1 - num_candys[i]);33 num_candys[i] = num_candys[i+1] + 1;34 }35 }36 return left + right + total;37 }38 }else{39 if(num_candys[mid] < num_candys[mid+1])40 return left + right;41 else{42 total += (num_candys[mid] + 1 - num_candys[mid+1]);43 num_candys[mid+1] = num_candys[mid] + 1;44 for(int i = mid+2; i <= e; ++i){45 if(ratings[i] <= ratings[i-1] || (ratings[i] > ratings[i-1] && num_candys[i] > num_candys[i-1]))46 break;47 else{48 total += (num_candys[i-1] + 1 - num_candys[i]);49 num_candys[i] = num_candys[i-1] + 1;50 }51 }52 return left + right + total;53 }54 }55 }56 }57 };
LeetCode: Candy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。