leetcode 135. Candy

迈不过友情╰ 2022-07-28 09:51 168阅读 0赞

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.

马丹，开始以为你可以自己排列这些小朋友，然后发给他们糖果，提交之后发现不对，看了测试用例之后悔悟必须按原先的排列顺序来

class Solution {
    public:
    	int candy(vector<int>& ratings) {
    		if (ratings.empty())
    			return 0;
    		if (ratings == vector<int>(ratings.size(), ratings[0]))
    			return ratings.size();
    		map<int,int>cnt;
    		for (int i = 0; i < ratings.size(); i++)
    			cnt[ratings[i]]++;
    		int sum = 0;
    		int imax = (cnt.size() + 1) & 4 == 0 ? cnt.size() / 2 + 1 : cnt.size() / 2;
    		int i = 0;
    		int more2=0;
    		for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); it++)
    		{
    			if (i < imax)
    				sum += it->second;
    			else
    			{
    				if (it->second >= 2)
    				{
    					more2++;
    					sum += 2 * it->second - 2 * (it->second - 2);
    				}
    				else
    					sum += 2;
    			}
    			i++;
    		}
    		if ((cnt.size() + 1) & 4 != 0 && more2 > 0)
    		{
    			if ((cnt.size() - 1) & 4 == 0 && more2 >= 2)
    				sum -= 2;
    			else
    				sum -= 1;
    		}
    		return sum;
    	}
    };

下面是正确理解题意后的代码，问题不算很难，但代码严谨性要高，否则还是会出些问题的

class Solution {
    public:
    	int candy(vector<int>& ratings) {
    		if (ratings.empty())
    			return 0;
    		if (ratings == vector<int>(ratings.size(), ratings[0]))
    			return ratings.size();
    		vector<int>cans(ratings.size());
    		int k = 0;
    		while (k < ratings.size())
    		{
    			int k1 = k;
    			while (k1 + 1 < ratings.size() && ratings[k1] < ratings[k1 + 1])
    				k1++;
    			int k2;
    			if (k1 == k)
    				k2 = k;
    			else
    			{
    				for (int i = k; i < k1 + 1; i++)
    					if (cans[i] == 0)
    					{
    					if (i == 0)
    						cans[i] = 1;
    					else
    					{
    						if (ratings[i] <= ratings[i - 1])
    							cans[i] = 1;
    						else
    						cans[i] = cans[i - 1] + 1;
    					}
    					}
    				k1++;
    				k2 = k1 ;
    			}
    			while (k2 + 1 < ratings.size() && ratings[k2] > ratings[k2 + 1])
    				k2++;
    			if (k1<ratings.size()&&k1>0 && k2 + 1 - k1 >= cans[k1 - 1] && ratings[k1 - 1] > ratings[k1])
    				cans[k1 - 1] = k2 + 1 - k1 + 1;
    			for (int i = k1; k1<ratings.size()&&i < k2 + 1; i++)
    				cans[i] = k2+1 - k1  - (i - k1);
    			if (k2 + 1 >= ratings.size())
    				break;
    			if (ratings[k2] == ratings[k2 + 1])
    				k = k2 + 1;
    			else
    				k = k2;
    		}
    		int sum = 0;
    		for (int i = 0; i < cans.size(); i++)
    			sum += cans[i];
    		return sum;
    	}
    };