首页 > 试题广场 > candy
[编程题]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?


90个回答

添加回答
class Solution {
public:
    int candy(vector<int> &ratings) {
        //题意:N个孩子站成一排,每个孩子分配一个分值。给这些孩子派发糖果,满足如下要求:
        //每个孩子至少一个
        //分值更高的孩子比他的相邻位的孩子获得更多的糖果
        //求至少分发多少糖果?
        int len=ratings.size();
        if(len==1) return 1;
        
        int sum=0;
        vector<int> v(len,1);//初始将每个孩子的糖果数都设为1
        
        //从左向右扫描,保证一个方向上分数更大的糖果更多
        for(int i=1;i<len;i++){
            if(ratings[i] > ratings[i-1])
                v[i]=v[i-1]+1;
        }
        //从右向左扫描,保证另一个方向上分数更大的糖果更多
        for(int i=len-2;i>=0;i--){
            if(ratings[i] > ratings[i+1] && v[i] <= v[i+1])
                v[i]=v[i+1]+1;
        }
        
        for(int i=0;i<len;i++){
            sum+=v[i];
        }
        return sum;
    }
};

发表于 2016-09-12 00:34:44 回复(6)
import java.util.*;
public class Solution {
    public int candy(int[] ratings) {
        if(ratings==null || ratings.length==0) {
            return 0;
        }
        
        int[] count = new int[ratings.length];
        //每个孩子初始都有一个糖果
        Arrays.fill(count,1);
        int sum = 0;
        for(int i=1;i<ratings.length;i++) {
            if(ratings[i]>ratings[i-1]) {
                count[i] = count[i-1]+1;
            }
        }
        
        for(int i=ratings.length-1;i>0;i--) {
            sum+=count[i];
            if(ratings[i]<ratings[i-1] && count[i]>=count[i-1]) {
                count[i-1] = count[i]+1;
            }
        }
        sum+=count[0];
        
        return sum;
    }
}

发表于 2016-03-19 15:56:08 回复(10)
class Solution {
public:
  /*
  遍历两边,首先每个人得一块糖,第一遍从左到右,若当前点比前一个点高就比前者多一块。
  这样保证了在一个方向上满足了要求。第二遍从右往左,若左右两点,左侧高于右侧,但
  左侧的糖果数不多于右侧,则左侧糖果数等于右侧糖果数+1,这就保证了另一个方向上满足要求
 */
    int candy(vector<int> &ratings)
    {
        int n = ratings.size();
        if(n==0) return 0;
        vector<int> candy(n,1);
        for(int i=1;i<n;i++)
        {
            if(ratings[i] > ratings[i-1])
                candy[i] = candy[i-1]+1;
        }
        for(int i=n-1;i>=0;i--)
        {
            if(ratings[i-1] > ratings[i] && candy[i-1] <= candy[i])
                candy[i-1] = candy[i]+1;
        }
        return accumulate(candy.begin(),candy.end(),0);
    }
};

发表于 2017-07-06 14:49:47 回复(1)

(1)笨方法
动态规划思想(易于理解):每个糖果的值都要受限与邻居结点(如果评估值比邻居结点大,那么得到的糖果也比邻居结点多)

  1. 根据限制我们可以想到一个二维数组,从初次扫描开始,每次扫描将评估值与同行前一个结点和前一行后一个结点的值比较,如果大于就加一。
  2. 何时结束:N个值,最多进行N次循环,因为最多N个不同的数,最大糖果差为N。
    本题,使用NN的数组会超出内存限制,于是改用2N的数组,其实,也只用到两行,前一行,后一行。
    int candy(vector<int> &ratings) {
        vector<vector<int>>  v(2,vector<int>());
        for(int i = 0;i < ratings.size();i++){
            v[0].push_back(0);
            v[1].push_back(0);
        }
        //初始化,每个孩子一个糖果
        for(int i = 0;i < ratings.size();i++)
            v[0][i] = 1;

        bool bc = true;
        bool inturn = true;
        int pre,pos;
        for(int i = 1;i < ratings.size();i++){
            if(!bc) break;
            bc = false;
            //轮流切换两行
            if(inturn){
                pre = 0;
                pos = 1;
                inturn = false;
            } else{
                pre = 1;
                pos = 0;
                inturn = true;
            }
            //与左邻居和右邻居比较
            for(int j = 0;j < ratings.size();j++){
                v[pos][j] = v[pre][j];
                if(j>0){
                    if(ratings[j] > ratings[j-1]){
                        if(v[pre][j] <= v[pos][j-1]){
                            v[pos][j] = v[pos][j-1] + 1;
                            if(!bc) bc = true;
                        }
                    }
                }
                if(j<ratings.size()-1){
                    if(ratings[j] > ratings[j+1]){
                        if(v[pos][j] <= v[pre][j+1]){
                            v[pos][j] = v[pre][j+1] + 1;
                            if(!bc) bc = true;
                        }
                    }
                }
            }
        }
        int minCan = 0;
        if(inturn) pos = 0;
        else pos = 1;
        for(int i = 0;i < ratings.size();i++)
            minCan += v[pos][i];
        return minCan;
    }

(2)灵活方法
第一次从左向右扫描找到一个方向上的最大值,第二次从右向左扫描找到另一个方向的最大值。

  1. 从左向右扫描后能保证比左边邻居大1
  2. 从右向左扫描后能保证比右边邻居大1,同时因为第一次扫描,也可以保证比左边大1
    为什么还要从右向左扫描,因为有可能右边邻居等于自身。
    例如:2 1
    输出应该为 3,只从左向右的,会输出2
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        vector<int> v(n,1);
        for( int i = 1;i < n;i++)
            if(ratings[i]>ratings[i-1]) v[i] = v[i-1]+1;
        int sum = 0;
        for( int i = n-1;i > 0;i--){
            if(ratings[i-1]>ratings[i]&&v[i-1]<=v[i]) v[i-1] = v[i] + 1;
            sum += v[i];
        }
        sum += v[0];
        return sum;
        }
    
    同步博客
发表于 2017-11-28 15:29:36 回复(0)
import java.util.Arrays;

public class Solution {     //状态转移方程为 candies[i] = max{candies[i-1], candies[i+1]} + 1
    public int candy(int[] ratings) {
        int sum = 0;
        int [] candies = new int [ratings.length];
        Arrays.fill(candies, 1);//把糖果数组初始化为1
        //从左向右使得当ratings[i] > ratings[i-1]时,candies[i] > candies[i-1]
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i-1])
                candies[i] = Math.max(candies[i], candies[i-1] + 1);
        }
        //从右向左扫描,使得ratings[i] > ratings[i+1]时,candies[i] > candies[i+1]
        sum += candies[candies.length-1];
        for(int i = ratings.length-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1])
                candies[i] = Math.max(candies[i], candies[i+1] + 1);
            sum += candies[i];
        }

        return sum;
    }
}

发表于 2017-12-06 13:03:05 回复(0)
先从左到右,再从右到左扫描两遍即可
public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length <= 1)
        	return 1;
        
        int[] candy = new int[ratings.length];
        int sum = 0;
        for(int i = 0; i < candy.length; i++)
        	candy[i] = 1;
        for(int i = 1; i < candy.length; i++){
        	if(ratings[i] > ratings[i - 1])
        		candy[i] = candy[i - 1] + 1;
        }
        for(int i = candy.length - 1; i > 0; i--){
        	if(ratings[i] < ratings[i - 1] && candy[i] >= candy[i - 1])
        		candy[i - 1] = candy[i] + 1;
        }
        
        for(int i = 0; i < candy.length; i++)
        	sum += candy[i];
        
        return sum;
    }
}

发表于 2017-05-15 16:35:55 回复(0)
dp做法:
class Solution {
public:
    int candy(vector<int> &ratings) {
        int r=ratings.size();
        map<int,int> mp;mp.clear();
        for(int i=0;i<r;i++) mp[i]=1;
        for(int i=0;i<r-1;i++){
            if(ratings[i]<ratings[i+1])
               mp[i+1]=mp[i]+1; 
        }
        int ans=0;
        for(int i=r-2;i>=0;i--)
            if(ratings[i]>ratings[i+1])
               mp[i]=max(mp[i],mp[i+1]+1);
        for(int i=0;i<r;i++) ans+=mp[i]; 
        return ans;
    }
};

拓扑排序做法(果然我dp还是弱到爆)
class Solution {
public:
    int candy(vector<int> &ratings) {
       queue<int> q;
       vector<int> G[100000];
       int ans=0,r=ratings.size(),indeg[100000],dp[100000];
       memset(indeg,0,sizeof(indeg));
       memset(dp,0,sizeof(dp)); 
       for(int i=0;i<r-1;i++){
           if(ratings[i]>ratings[i+1]) indeg[i]++,G[i+1].push_back(i);
           else if(ratings[i]<ratings[i+1]) indeg[i+1]++,G[i].push_back(i+1);
       } 
       for(int i=0;i<r;i++) if(!indeg[i]) dp[i]=1,q.push(i);
       while(q.size()){
           int u=q.front();q.pop();
           for(int j=0;j<G[u].size();j++){
               int v=G[u][j];
               dp[v]=max(dp[v],dp[u]+1);
               indeg[v]--;
               if(!indeg[v]) q.push(v);
           }
       }
        for(int i=0;i<r;i++) ans+=dp[i];
        return ans;
    }
};

编辑于 2017-04-14 13:29:43 回复(0)
class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        vector<int> res(n,1);
        for(int i = 0; i < n; i++){
            if(ratings[i+1] > ratings[i]){
                res[i+1] = res[i] + 1;
            }
        }
        for(int i = n-1; i >=1; i--){
            if(ratings[i-1] > ratings[i] && res[i-1] <= res[i]){
                res[i-1] = res[i] + 1;
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += res[i];
        }
        return sum;
    }
};

发表于 2018-07-27 20:54:33 回复(0)
这道题目采用动态规划的思想来求解,我觉得思想很重要
分为以下几个步骤:
1)当前孩子的rating比前面的孩子的rating高时:只需要考虑当前孩子的candies数目比前面孩子的candies的数目多至少一个即可;当前面的rating等于后面孩子的rating时,则题目没有说明,则可以比他多或者少;
2)当前孩子的rating比后面孩子的raitng低时:考虑当前孩子的后面的单调递减的孩子的数目,因为最后一个单调递减的孩子的手里至少还剩下一个糖果存在,则新建一个数组来存储单调递减孩子的数目,并将当前孩子的手里的糖果的数目设定为单调递减孩子的数目+1;
3)判断左边动态规划和右边动态规划的糖果数目,取其中糖果数目最大的即可;
代码如下:
class Solution {
public:
    int candy(vector<int> &ratings) {
        if(ratings.size()==0)
            return -1;
        int length=ratings.size();
        vector<int> array(length);
        for(int i=0;i<length;i++){
            int space=0;
            for(int j=i+1;j<length;j++){
                if(ratings[j]>=ratings[j-1])
                    break;
                else{
                    space++;
                }
            }
            array[i]=space;
        }
        
        int result=0;
        vector<int>candies(length);
        candies[0]=array[0]+1;
        result+=candies[0];
        
        for(int i=1;i<length;i++){
            int leftcandies=0;
            if(ratings[i]>ratings[i-1])
                leftcandies=candies[i-1]+1;
            int rightcandies=array[i]+1;
            candies[i]=max(leftcandies,rightcandies);
            result+=candies[i];
            
        }
        return result;
        
    }
};

发表于 2018-07-21 22:00:00 回复(0)
class Solution {
public:
    int candy(vector<int> &ratings) {
        int l = ratings.size();         if(l == 1)             return 1;         int s = 0;         vector<int> a(l,1);                  for(int i=1;i<l;i++)             if(ratings[i] > ratings[i-1])                 a[i] = a[i-1] + 1;                  for(int i=l-2;i>=0;i--)             if(ratings[i] > ratings[i+1] && a[i] <= a[i+1])                 a[i] = a[i+1] + 1;                  for(int i=0;i<l;i++)             s += a[i];                  return s;
    }
};

发表于 2017-09-25 01:16:23 回复(0)
class Solution {
public:
    int candy(vector<int> &rat) {
        vector<int> num(rat.size()+1,1);
        for(int i=1;i<rat.size();i++){
            if(rat[i]>rat[i-1]) num[i]=num[i-1]+1;
            else{
                int j=i-1;
                while(j>=0 && rat[j]>rat[j+1] && num[j]<=num[j+1]){ num[j]+=1; j--; } 
            }
        }
        int res=0;
        for(int i=0;i<rat.size();i++) res+=num[i];
        return res;
    }
};
发表于 2017-09-07 20:55:21 回复(0)
class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        int dp[n];

        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                dp[i] = max(dp[i], dp[i + 1] + 1);
            }
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += dp[i]; 
        }

        return sum;
    }
};

发表于 2017-08-30 17:53:49 回复(0)
class Solution {
public:
	int candy(vector<int> &ratings) {
        vector<pair<int, int>> v;
        for (int i = 0; i < ratings.size(); ++i)
            v.push_back({ ratings[i], i });
        sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b) {return a.first < b.first;});

        vector<int> candies(ratings.size(), 0);
        int n_count = 0;
        for (auto e : v) {
            int i = e.second;
            int left = 0;
            if (i - 1 >= 0) left = candies[i - 1];
            int right = 0;
            if (i + 1 < candies.size()) right = candies[i + 1];

            candies[i] = 1;
            if (left != 0 && ratings[i - 1] < ratings[i])
                candies[i] = left + 1;
            if (right != 0 && ratings[i + 1] < ratings[i])
                candies[i] = max(candies[i], right + 1);

            n_count += candies[i];
        }

        return n_count;
    }
};

发表于 2017-08-06 15:50:59 回复(0)
import java.util.*;
public class Solution {
    public int candy(int[] ratings) {
		int[] arr1 = new int[ratings.length];
		int[] arr2 = new int[ratings.length];
		Arrays.fill(arr1, 1);
		Arrays.fill(arr2, 1);
		for (int i = 1; i < ratings.length; i ++) {
			if(ratings[i] > ratings[i - 1]) arr1[i] = arr1[i - 1] + 1;
		}
		for (int i = ratings.length - 1; i >= 1; i --) {
			if(ratings[i] < ratings[i - 1]) arr2[i - 1] = arr2[i] + 1;
		}
		int sum = 0;
		for (int i = 0; i < ratings.length; i ++) {
			sum += arr1[i] > arr2[i] ? arr1[i] : arr2[i];
		}
		return sum;
	}
}
编辑于 2017-03-19 17:04:09 回复(0)
class Solution {
public:
    int candy(vector<int>& ratings) {
        int ret = 0;
        int len = ratings.size();
        vector<int> temp(len, 1);
        for(int i = 1; i < len; i++){
            if(ratings[i] > ratings[i-1]){
                temp[i] = temp[i-1]+1;
            }
        }
        for(int i = len-2; i >= 0; i--){
            if(ratings[i] > ratings[i+1]){
                temp[i] = max(temp[i], temp[i+1]+1);
            }
        }
        for(int i = 0; i < len; i++){
            ret += temp[i];
        }
        return ret;
    }
};

发表于 2016-09-06 16:52:31 回复(0)
class Solution {
public:
    int candy(vector<int> &ratings) {
        int n=ratings.size();
        if(n==0) return 0;
        
        vector<int> res(n);//存每个小孩应发的糖果数
        res[0]=1;
        for(int i=1;i<n;i++){//不断遍历ratings并更新res
            //如果新加入的小孩大于前一个小孩,则糖果比前一个小孩+1
            if(ratings[i]>ratings[i-1]) {
                res[i]=res[i-1]+1;
            }
            //关键:如果等于前一个小孩,则新小孩只需要分一个糖果,res不需要更新
            else if(ratings[i]==ratings[i-1]) {
                    res[i]=1;
            }
            //如果小于前一个小孩,则新加入小孩分一个糖果,之前的小孩应该比他多分到糖果  
            else{
                res[i]=1;
                //如果前面的小孩只有一个糖果,需要更新res
                if(res[i-1]==1) {
                    
                    //前面的小孩都多分一个糖果,直到递增结束
                    int j=i-1;
                    for(;j!=0&&res[j]<res[j-1];j--){
                        res[j]++;
                    }
                    //关键:注意相等rating的情况
                    if(res[j]<=res[j+1] && ratings[j]!=ratings[j+1])res[j]++;
                }
            }
            
        }
        int sum=0;
        for(auto e:res){
            sum+=e;
        }
        return sum;
    }
};

发表于 2016-07-04 01:27:26 回复(0)
    第一次想到的方法:
    1 找到所有的局部最高点 和 最低点
    2 每个局部最低点向两边延伸
    3 每个局部最高点的值等于他的左右两边的值中较大值
    4 统计每个点的值
    
    第二次想到的方法:
    其实从左边来一次,再从右边来一次,就OK了

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            // 1 3 5 2 7
            vector<int> a = ratings;
            vector<int> top;
            vector<int> low;

            int size = a.size();
            vector<int> candy(size);
            for( int i=0 ; i<size ; i++ ) {
                candy[i] = 1;
            }

            for( int i=0 ; i<size ; i++ ) {
                if( (i==0 || (i!=0 && a[i-1]<a[i])) &&
                    (i==size-1 || (i+1!=size && a[i]>a[i+1])) ) {	// 找到所有的局部最高点
                    top.push_back( i );
                }
                if( (i==0 || (i!=0 && a[i-1]>=a[i])) &&
                    (i==size-1 || (i+1!=size && a[i]<=a[i+1])) ) {// 找到所有的局部最低点
                    low.push_back( i );
                }
            }

            // 遍历每个局部最低点
            for( int i=0 ; i<low.size() ; i++ ) {	// 每个最低点向两边延伸,遇到大的就+1
                int k;
                // 向左边延伸
                k = low[i] -1;
                // tips : 处理边界问题的时候,只判断要处理的最靠近边界的下标 是否越界就行了.
                while( k>=0 && a[k]>a[k+1] ) {
                    candy[k] = candy[k+1] +1;
                    k--;
                }
                // 向右边延伸
                k = low[i] +1;
                while( k<size && a[k]>a[k-1] ) {
                    candy[k] = candy[k-1] +1;
                    k++;
                }   
            }

            // 遍历每个局部最高点
            for( int k=0 ; k<top.size() ; k++ ) {
                int i = top[k];

                // 局部最高点的值等于 他的左右两边的值中较大值 +1
                int t1 = 0, t2 = 0;
                if( i>0 ) t1 = candy[i-1];
                if( i<size-1 ) t2 = candy[i+1];
                candy[i] = (t1 > t2 ? t1 : t2) +1;
            }

            // 统计candy
            int ans = 0;
            for( int i=0 ; i<size ; i++ ) {
                ans += candy[i];
            }

            return ans;
        }
    };
    
    
    class Solution {
    public:
    	int max( int x, int y ) {
    		return x>y ? x : y;
    	}
    
        int candy(vector<int> &ratings) {
            // 1 3 5 2 7
            vector<int> a = ratings;
            vector<int> top;
            vector<int> low;
            
            int size = a.size();
            vector<int> candy(size);
            for( int i=0 ; i<size ; i++ ) {
                candy[i] = 1;
            }
            
    		// from left
    		for( int i=1 ; i<size ; i++ ) {
    			if( a[i] > a[i-1] ) 
    				candy[i] = candy[i-1] +1;
    		}
    
    		// from right
    		for( int i=size-2 ; i>=0 ; i-- ) {
    			if( a[i] > a[i+1] )
    				candy[i] = max( candy[i], candy[i+1] +1 );
    		}
                
            // 统计candy
            int ans = 0;
            for( int i=0 ; i<size ; i++ ) {
                ans += candy[i];
            }
                   
            return ans;
        }
    };
编辑于 2017-03-12 21:17:04 回复(0)
public class Solution {
    public int candy(int[] ratings) {
        int ret = 1;
        int len = ratings.length;
        int[] num = new int[len];
        num[0] = 1;
        int emark = 0;
        int lmark = 0;
        int tmpnum = 1;
        for (int i = 0; i < len-1; i++) {
            if (ratings[i] == ratings[i+1]) {
                emark = i + 1;
                tmpnum = 1;
                ret += tmpnum;
                num[i+1] = tmpnum;
            } else if (ratings[i] < ratings[i+1]) {
                tmpnum++;
                ret += tmpnum;
                lmark = i + 1;
                num[i+1] = tmpnum;
            } else {
                tmpnum--;
                if (tmpnum == 0) {
                    if (emark <= lmark) {
                        ret += i - lmark;
                        for (int j = lmark + 1; j <= i+1; j++) {
                            num[j] += 1;
                        }
                        if (num[lmark] == num[lmark+1]) {
                            num[lmark] += 1;
                            ret += 1;
                        }
                    } else {
                        ret += i - emark + 1;
                        for (int j = emark; j <= i+1; j++) {
                            num[j] += 1;
                        }
                    }
                
                tmpnum = 1;
                ret += tmpnum;
                num[i+1] = tmpnum;
            }
        }
        return ret;
    }
}

发表于 2018-09-24 17:36:55 回复(0)
思路
两次遍历:从左边开始向右边遍历,保证右边分值大的,得到苹果数比左边大1
                再从右边开始向左边遍历,保证左边比右边分值大的,得到的苹果数比右边大1
但是,注意一种特殊情况,就是第一次向右边遍历后能够确定,右边比左边大的,得到的苹果数加1,但是到第二次遍历的时候可能出现,左边的分值已经比左边大了,并且苹果数已经大了,就不用再加了。例如 3,4,1 

发表于 2018-08-25 15:01:32 回复(0)
import java.util.Arrays;
public class Solution {     public int candy(int[] ratings) {         int len=ratings.length;         if(ratings.length==0)             return 0;         int[] count=new int[len+1];         Arrays.fill(count, 1);         //从左向右扫描         for(int i=1;i<len;i++){             if(ratings[i]>ratings[i-1]){                 count[i]=count[i-1]+1;             }         }         //从右向左扫描         for(int i=len-2;i>=0;i--){             if(ratings[i]>ratings[i+1]&&count[i]<=count[i+1]){                 count[i]=count[i+1]+1;             }         }         int sum=0;         for(int i=0;i<len;i++){             sum+=count[i];         }         return sum;     }
}

发表于 2018-08-24 11:10:34 回复(0)