Lexi's Leetcode solutions

[leetcode] Candy | 给小孩子分糖

Posted on: October 8, 2013

一维DP。

  • d[i] 是给第i个小孩最少几块糖
    • rank[i] > rank[i – 1],必须比前一个多给一块,d[i] = d[i – 1] + 1
    • rank[i] == rank[i – 1],两个排名一样,第二个就给一块就行了, d[i] = 1
    • rank[i] < rank[i – 1],比上一个排名低,应该少给一块,但是若上一个已经只给一块了,就得往前推一个一个多给。推到什么时候为止呢?若排名比下一个高,糖还一样多,就得再给;直到这个关系打破(排名一样或比下一个还低,或是糖已经满足关系)就不用再往前推了。
public int candy(int[] ratings) {
    if (ratings.length == 0)
        return 0;
    int[] d = new int[ratings.length];
        d[0] = 1;
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] == ratings[i - 1])
            d[i] = 1;
        else if (ratings[i] > ratings[i - 1])
            d[i] = d[i - 1] + 1;
        else {// should give less candy than prev child
            d[i] = 1;
            if (d[i - 1] == 1) {
                int j = i;
                while (j > 0 && ratings[j - 1] > ratings[j] && d[j - 1] == d[j]) {
                    //only push backwards when ratings diff but candy are same
                   d[j - 1]++;
                   j--;
                }
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < ratings.length; i++) {
        sum += d[i];
    }
    return sum;
}
Advertisements
Tags:

4 Responses to "[leetcode] Candy | 给小孩子分糖"

这个做法貌似大量数据的时候不能通过,比如有12000个child,rating是从12000到1的递减。 楼主有遇到这样的问题嘛?

这个做法是我第一次做的时候就post了,那个时候刚出这个题,可能数据和现在不一样。好的做法是o(n)的,两个数组,我一会儿更新啊哈亲。

O(n) 从左往右刷一遍,再从右往左刷一遍。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: