一起刷leetcode(135):Candy


问题名称:135.Candy
Link:https://oj.leetcode.com/problems/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?
已邀请:

青原行思 - Crazy about ML!

赞同来自:


基本思路:快排+贪心,已AC.
但运行时间好像较长,目前想到的可能的改进如下:
由于是对int进行排序,所以也许可以用基数排序或者桶排序,也许比快排要快

现已AC的代码如下:
/*
*Author:qingyuanxings
*Date:2015-03-03
*Title:135.Candy
*Link:https://oj.leetcode.com/problems/candy/
*Quick sort+Greedy algorithm
*/

include <unordered_map>

include <vector>

include <iostream>

include <algorithm>

include <numeric>

include <time.h>

using namespace std;

class Solution {
    public:
        int random(int start,int end)
        {
            srand(time(NULL));
            return start+rand()%(end-start+1);
        }

        void swap(int &a,int &b){
            int temp = a;
            a = b;
            b = temp;
        }

        int rand_partition(vector<int> &ratings,vector<int> &positions,int p, int q){
            int t=random(p,q);
            swap(ratings[t],ratings[p]);
            swap(positions[t],positions[p]);
            int base=ratings[p];
            int i=p;
            for(int j=p+1;j<=q;j++)
            {
                if(ratings[j]<base)
                {
                    i++;
                    swap(ratings[i],ratings[j]);
                    swap(positions[i],positions[j]);
                }
            }
            swap(ratings[i],ratings[p]);
            swap(positions[i],positions[p]);

            return i;
        }

        //quick sort and record its relative position
        void quicksort(vector<int> &ratings,vector<int> &positions,int left,int right){
            if(left<right){
                    int r = rand_partition(ratings,positions,left,right);
                    quicksort(ratings,positions,left,r-1);
                    quicksort(ratings,positions,r+1,right);
            }
        }

        int candy(vector<int> &ratings) {
            //Position and rating
            unordered_map<int,int> pos_map;
            int c_size = ratings.size();
            //Give one candy to each kid
            vector<int> candies(c_size,1);
            vector<int> positions(c_size);
            for(int i=0;i!=c_size;i++){
                positions[i] = i;
                pos_map[i] = ratings[i];
            }
            quicksort(ratings,positions,0,c_size-1);
            for(int i=0;i<c_size;i++){
                int pos = positions[i];
                int temp = pos_map[pos];
                if(pos>0){
                    if(pos_map[pos-1]>temp && candies[pos-1]<=candies[pos]){
                        candies[pos-1] = candies[pos]+1;
                    }
                }
                if(pos<c_size-1){
                    if(pos_map[pos+1]>temp && candies[pos+1]<=candies[pos]){
                        candies[pos+1] = candies[pos]+1;
                    }
                }
            }
            return accumulate(candies.begin(),candies.end(),0);
        }
};

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~