Can somebody help me to point out where my codes go wrong ?


  • 0
    W

    My codes pass some small test cases but when it comes with large scale cases,it's wrong as follows:

    Submission Result: Wrong Answer
    Input: [56,82,584,683,750,....................... such a really long serial....
    Output: 1975
    Expected: 1974

    Is there some fault with my algorithm?

    class Solution {
        public:
            int candy(vector<int> &ratings) {
              
        	//max increase serial.
              vector<int> max_increase(ratings.size(),0);
              for(int i=ratings.size()-1;i>0;i--)
        	{
        	 if(ratings[i-1] <= ratings[i])
        	   {
        	     max_increase[i-1] = max_increase[i] + 1;
        	     max_increase[i] = 0;
        	   }
        	}
              vector<int> candy_num(ratings.size(),1);
              /*
        		                  17
        	          7	       11    13  4
                   6    4     9        4
                5         3  2        
             3              2
        
        */
              int index = 0;
              int inc_begin = 0;
              vector<int>  each_value(ratings.size(),1);
              while(inc_begin<ratings.size()-1)
        	{
        	  while(inc_begin<ratings.size()-1 && max_increase[inc_begin]==0)
        	    {
        	      inc_begin++;
        	    }
        	  ///////////////// for  \  serial
        	  for(int i=inc_begin;i>index;i--)
        	    {
        		  if(each_value[i]+1 >= each_value[i-1])
        		     each_value[i-1] = each_value[i]+1;
        	    }
        	  ///////////////////// for /  serial
        	  for(int j=inc_begin;j<inc_begin + max_increase[inc_begin];j++)
        	    {
        			if(ratings[j] < ratings[j+1]) 
        			{
        				each_value[j+1] = each_value[j]+1;
        			}
        			else //equal
        			{
        				if (each_value[j]>=2)
        				{
        					each_value[j+1]=each_value[j]-1;
        				}
        			 }
        	    }
        	  inc_begin = inc_begin + max_increase[inc_begin];
        	  index = inc_begin;
        	}
             int sum_num = 0;
             for(int k=0;k<each_value.size();k++)
        	 sum_num+= each_value[k];
             return sum_num;
           }
        };

  • 0
    W

    I've found where the fault happended. It is here:
    if (each_value[j]>=2)
    {
    each_value[j+1]=each_value[j]-1;
    }
    It should be each_value[j+1] = 1;

    I think if you hand out candy for children , It is better to give them the same candy if the neighbour children have a same rating value.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.