COMP9517 Final Exam Sample

问题传送门：https://leetcode.cn/problems/candy/description/




本题的思路是两次遍历。

注意到，核心规则为：

> 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么，我们将其拆分为左规则和右规则：

- 左规则：当 $ratings[i−1]<ratings[i]$ 时，$i$ 号学生的糖果数量将比 $i−1$ 号孩子的糖果数量多。
- 右规则：当 $ratings[i]>ratings[i+1]$ 时，$i$ 号学生的糖果数量将比 $i+1$ 号孩子的糖果数量多。

我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

以左规则为例：我们从左到右遍历该数组，假设当前遍历到位置 $i$，如果有 $ratings[i−1]<ratings[i]$， 那么 $i$ 号学生的糖果数量将比 $i−1$ 号孩子的糖果数量多，我们令 $left[i]=left[i−1]+1$ 即可，否则我们令 $left[i]=1$。

```C++
class Solution {
public:
    int candy(vector<int>& ratings) {
        auto length = ratings.size();
        vector<int> left(length);
        for (auto i = 0; i < length; i++) {
            if (i > 0 && ratings[i - 1] < ratings[i]) {
                left[i] = left[i - 1] + 1;
            }
            else {
                left[i] = 1;
            }
        }

        vector<int> right(length);
        for (int i = length - 1; i >=0; i--) {
            if (i < length - 1 && ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
            else {
                right[i] = 1;
            }
        }

        vector<int> result(length);
        auto sum = 0;
        for (int i = 0; i < length; i++) {
            result[i] = max(left[i], right[i]);
            sum += result[i];
        }
        return sum;
    }
};
```

但实际上用不着这么麻烦。主要在于向量right它不用做出来。它只是一个比较值，能拿来用就可以了。我们没必要存储它。向量result也是如此，如果我们只是为了求解一个sum，根本不需要把它存起来再一个个加上去。这种写法只是为了方便读者理解。

如果进行简化，可以将right直接简化成一个int类型，同时删去result相关的部分。

```C++
class Solution {
public:
    int candy(vector<int>& ratings) {
        auto length = ratings.size();
        vector<int> left(length);
        for (auto i = 0; i < length; i++) {
            if (i > 0 && ratings[i - 1] < ratings[i]) {
                left[i] = left[i - 1] + 1;
            }
            else {
                left[i] = 1;
            }
        }

        int right = 0;
        int sum = 0;
        for (int i = length - 1; i >=0; i--) {
            if (i < length - 1 && ratings[i] > ratings[i + 1]) {
                right += 1;
            }
            else {
                right = 1;
            }
            sum += max(left[i], right);
        }
        return sum;
    }
};
```

Leetcode 135. 分发糖果

COMP9517 Week 5 Image Segmentation Part 1

COMP9517 Week 4 Pattern Recognition Part 2

COMP9517 Week 4 Pattern Recognition Part 1

script

首页

分类

时间线

关于