首页 > 代码库 > leetcode candy
leetcode candy
这道题折腾了好久，一开始想复杂了。比较好理解的一个方法是通过两次遍历。
注意到一个事实：只有当当前孩子比旁边孩子高的时候才会要求比他更多的糖，而这个比当前孩子矮的孩子既有可能来自左边，也有可能来自右边。
也就是说，左右两边的孩子都会对当前孩子做出限定。当每个孩子既能满足左边孩子的限定又能满足右边孩子的限定的时候，分配的糖果才是符合要求的。
1 int candy(vector<int> &ratings){ 2 int size = ratings.size(); 3 vector<int> count(size, 1); 4 if (size == 0) return 0; 5 else if (size == 1) return 1; 6 for (int i = 1; i < size; i++){ 7 if (ratings[i] > ratings[i - 1]){ 8 count[i] = count[i - 1] + 1; 9 }10 }11 for (int i = size - 2; i >= 0; i--){12 if (ratings[i] > ratings[i + 1] && count[i] <= count[i + 1]){13 count[i] = count[i + 1] + 1;14 }15 16 }17 int result = 0;18 for (int i = 0; i < size; i++){19 result += count[i];20 }21 return result;22 }
注意第二次遍历的时候，使得当前孩子糖果数目增多的条件又多了一个（count[i] <= count[i +１]），那是因为第一次遍历的时候，所有孩子都只有一个糖果，所以这个条件直接成立。
但第二次面临的是已经经过修改后的数据。
ac之后又在讨论区发现一种更巧妙的一次遍历方法：
1 int candy(vector<int> &ratings) { 2 // Note: The Solution object is instantiated only once and is reused by each test case. 3 int nCandyCnt = 0;///Total candies 4 int nSeqLen = 0; /// Continuous ratings descending sequence length 5 int nPreCanCnt = 1; /// Previous child‘s candy count 6 int nMaxCntInSeq = nPreCanCnt; 7 if (ratings.begin() != ratings.end()) 8 { 9 nCandyCnt++;//Counting the first child‘s candy.10 for (vector<int>::iterator i = ratings.begin() + 1; i != ratings.end(); i++)11 {12 // if r[k]>r[k+1]>r[k+2]...>r[k+n],r[k+n]<=r[k+n+1],13 // r[i] needs n-(i-k)+(Pre‘s) candies(k<i<k+n)14 // But if possible, we can allocate one candy to the child,15 // and with the sequence extends, add the child‘s candy by one16 // until the child‘s candy reaches that of the prev‘s.17 // Then increase the pre‘s candy as well.18 19 // if r[k] < r[k+1], r[k+1] needs one more candy than r[k]20 // 21 if (*i < *(i - 1))22 {23 //Now we are in a sequence24 nSeqLen++;25 if (nMaxCntInSeq == nSeqLen)26 {27 //The first child in the sequence has the same candy as the prev28 //The prev should be included in the sequence.29 nSeqLen++;30 }31 nCandyCnt += nSeqLen;32 nPreCanCnt = 1;33 }34 else35 {36 if (*i > *(i - 1))37 {38 nPreCanCnt++;39 }40 else41 {42 nPreCanCnt = 1;43 }44 nCandyCnt += nPreCanCnt;45 nSeqLen = 0;46 nMaxCntInSeq = nPreCanCnt;47 }48 }49 }50 return nCandyCnt;51 }
这个算法的为什么成立我还没搞明白，有待继续探索。
leetcode candy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。