代码随想录31

目录

leetcode135.分发糖果

思路：

leetcode860.柠檬水找零

思路：就是一个个遍历然后判断，用哈希表存储数。

leetcode406.根据身高重建队列

---

leetcode135.分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

思路：

• 每个孩子至少有一个糖果：

  • 先初始化一个数组 candy，数组长度和评分数组 ratings 相同，所有元素都初始化为 1，表示每个孩子至少会有一个糖果。

• 从左到右遍历：

  • 在第一次遍历中，确保 如果当前孩子的评分比前一个孩子高，则当前孩子的糖果数量要比前一个孩子多 1。
  • 具体地，if (ratings[i] > ratings[i - 1]) 判断当前孩子的评分是否高于前一个孩子，如果是，那么更新当前孩子的糖果数为 candy[i - 1] + 1，即比前一个孩子的糖果多一个。

• 从右到左遍历：

  • 在第二次遍历中，确保 如果当前孩子的评分比后一个孩子高，则当前孩子的糖果数量要比后一个孩子多 1。
  • 具体地，if (ratings[i] > ratings[i + 1]) 判断当前孩子的评分是否高于后一个孩子。如果是，那么更新当前孩子的糖果数为 max(candy[i], candy[i + 1] + 1)。这里 max 确保如果已经在左到右遍历时给当前孩子分配过糖果，那么不会被右到左的遍历重新分配为更少的糖果。

• 计算总糖果数：

  • 最后，遍历 candy 数组，累加每个孩子的糖果数，得到总的糖果数。

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);// 从前向后for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}// 从后向前for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}}// 统计结果int result = 0;for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];return result;}
};

leetcode860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

这是我自己写的：

思路：就是一个个遍历然后判断，用哈希表存储数。

这道题题目限制比较多，所以很多情况可以不用考虑。比如收到五块钱就直接收下也不用考虑要不要找零；收到10，就只有一种找零情况，就是找五块钱出去；收到20，要优先把10块钱花出去，因为五块钱的用处比较大。所以比较简单

class Solution {
public:bool lemonadeChange(vector<int>& bills) {//哈希数组unordered_map<int,int> money;for(int i=0;i<bills.size();i++){if(bills[i]==5){money[bills[i]]++;}if(bills[i]==10){money[bills[i]]++;if(money[5]>=1){money[5]--;}else if(money[5]<=0){return false;}}if(bills[i]==20){money[bills[i]]++;if(money[10]>=1&&money[5]>=1){money[10]--;money[5]--;}else if(money[5]>=3){money[5]--;money[5]--;money[5]--;}else return false;}}return true;}
};

leetcode406.根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}//身高和数量两个维度分开排vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {//身高从大到小，相同的话，数量小的在前面，sort (people.begin(), people.end(), cmp);vector<vector<int>> que;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);}return que;}
};