C++實現LeetCode(135.分糖果問題)

Posted on by

[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?

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

解法一：

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;
    }
};

下面來看一次遍歷的方法，相比於遍歷兩次的思路簡單明瞭，這種隻遍歷一次的解法就稍有些復雜瞭。首先我們給第一個同學一個糖果，那麼對於接下來的一個同學就有三種情況：

1. 接下來的同學的rating等於前一個同學，那麼給接下來的同學一個糖果就行。

2. 接下來的同學的rating大於前一個同學，那麼給接下來的同學的糖果數要比前一個同學糖果數加1。

3.接下來的同學的rating小於前一個同學，那麼我們此時不知道應該給這個同學多少個糖果，需要看後面的情況。

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

1 3 2 1

先給第一個rating為1的同學一個糖果，然後從第二個同學開始遍歷，第二個同學rating為3，比1大，所以多給一個糖果，第二個同學得到兩個糖果。下面第三個同學，他的rating為2，比前一個同學的rating小，如果我們此時給1個糖果的話，那麼rating更小的第四個同學就得不到糖果瞭，所以我們要給第四個同學1個糖果，而給第三個同學2個糖果，此時要給第二個同學追加1個糖果，使其能夠比第三個同學的糖果數多至少一個。那麼我們就需要統計出多有個連著的同學的rating變小，用變量cnt來記錄，找出瞭最後一個減小的同學，那麼就可以往前推，每往前一個加一個糖果，這就是個等差數列，我們可以直接利用求和公式算出這些rating減小的同學的糖果之和。然後我們還要看第一個開始減小的同學的前一個同學需不需要追加糖果，隻要比較cnt和pre的大小，pre是之前同學得到的最大糖果數，二者做差加1就是需要追加的糖果數，加到結果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

到此這篇關於C++實現LeetCode(135.分糖果問題)的文章就介紹到這瞭,更多相關C++實現分糖果問題內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：