[LeetCode] 135.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?

這道題看起來很難，其實解法并沒有那么復(fù)雜，當(dāng)然我也是看了別人的解法才做出來的，先來看看兩遍遍歷的解法，首先初始化每個人一個糖果，然后這個算法需要遍歷兩遍，第一遍從左向右遍歷，如果右邊的小盆友的等級高，等加一個糖果，這樣保證了一個方向上高等級的糖果多。然后再從右向左遍歷一遍，如果相鄰兩個左邊的等級高，而左邊的糖果又少的話，則左邊糖果數(shù)為右邊糖果數(shù)加一。最后再把所有小盆友的糖果數(shù)都加起來返回即可。代碼如下：

解法一：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 0, n = ratings.size();
        vector<int> nums(n, 1);
        for (int i = 0; i < n - 1; ++i) {
            if (ratings[i + 1] > ratings[i]) nums[i + 1] = nums[i] + 1;
        }
        for (int i = n - 1; i > 0; --i) {
            if (ratings[i - 1] > ratings[i]) nums[i - 1] = max(nums[i - 1], nums[i] + 1);
        }
        for (int num : nums) res += num;
        return res;
    }
};

下面來看一次遍歷的方法，相比于遍歷兩次的思路簡單明了，這種只遍歷一次的解法就稍有些復(fù)雜了。首先我們給第一個同學(xué)一個糖果，那么對于接下來的一個同學(xué)就有三種情況：

1. 接下來的同學(xué)的rating等于前一個同學(xué)，那么給接下來的同學(xué)一個糖果就行。

2. 接下來的同學(xué)的rating大于前一個同學(xué)，那么給接下來的同學(xué)的糖果數(shù)要比前一個同學(xué)糖果數(shù)加1。

3.接下來的同學(xué)的rating小于前一個同學(xué)，那么我們此時不知道應(yīng)該給這個同學(xué)多少個糖果，需要看后面的情況。

對于第三種情況，我們不確定要給幾個，因為要是只給1個的話，那么有可能接下來還有rating更小的同學(xué)，總不能一個都不給吧。也不能直接給前一個同學(xué)的糖果數(shù)減1，有可能給多了，因為如果后面再沒人了的話，其實只要給一個就行了。還有就是，如果后面好幾個rating越來越小的同學(xué)，那么前一個同學(xué)的糖果數(shù)可能還得追加，以保證最后面的同學(xué)至少能有1個糖果。來一個例子吧，四個同學(xué)，他們的rating如下：

1 3 2 1

先給第一個rating為1的同學(xué)一個糖果，然后從第二個同學(xué)開始遍歷，第二個同學(xué)rating為3，比1大，所以多給一個糖果，第二個同學(xué)得到兩個糖果。下面第三個同學(xué)，他的rating為2，比前一個同學(xué)的rating小，如果我們此時給1個糖果的話，那么rating更小的第四個同學(xué)就得不到糖果了，所以我們要給第四個同學(xué)1個糖果，而給第三個同學(xué)2個糖果，此時要給第二個同學(xué)追加1個糖果，使其能夠比第三個同學(xué)的糖果數(shù)多至少一個。那么我們就需要統(tǒng)計出多有個連著的同學(xué)的rating變小，用變量cnt來記錄，找出了最后一個減小的同學(xué)，那么就可以往前推，每往前一個加一個糖果，這就是個等差數(shù)列，我們可以直接利用求和公式算出這些rating減小的同學(xué)的糖果之和。然后我們還要看第一個開始減小的同學(xué)的前一個同學(xué)需不需要追加糖果，只要比較cnt和pre的大小，pre是之前同學(xué)得到的最大糖果數(shù)，二者做差加1就是需要追加的糖果數(shù)，加到結(jié)果res中即可，參見代碼如下：

解法二：

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.empty()) return 0;
        int res = 1, pre = 1, cnt = 0;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] >= ratings[i - 1]) {
                if (cnt > 0) {
                    res += cnt * (cnt + 1) / 2;
                    if (cnt >= pre) res += cnt - pre + 1;
                    cnt = 0;
                    pre = 1;
                }
                pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
                res += pre;
            } else {
                ++cnt;
            }
        }     
        if (cnt > 0) {
            res += cnt * (cnt + 1) / 2;
            if (cnt >= pre) res += cnt - pre + 1;
        }
        return res;
    }
};

參考資料：

https://discuss.leetcode.com/topic/5243/a-simple-solution

https://discuss.leetcode.com/topic/8208/one-pass-constant-space-java-solution

https://discuss.leetcode.com/topic/17722/two-c-solutions-given-with-explanation-both-with-o-n-time-one-with-o-1-space-the-other-with-o-n-space

到此這篇關(guān)于C++實現(xiàn)LeetCode(135.分糖果問題)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)分糖果問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論