LeetCode刷题day18——贪心

昨天写了一道，今天写了一道，都有思路，却不能全整对。昨天和小伙伴聊天，说是因为最近作业多，昨天没打题，负罪感满满，养成习惯了都。

135. 分发糖果

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

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

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

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

示例 1：

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

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

分析：

如果它ratings大，它的candy要比邻居多！我一开始是在同一个循环里，同时左右检查，这是搞不清楚的，要分开扫。

• 从左到右扫：if i < i+1,candy(i+1)++;
• 从右到左扫：if i-1 > i && candy(i-1)<=candy(i), candy(i-1)=candy(i)+1;

class Solution {
public:int candy(vector<int>& ratings) {//从左到右扫：if i < i+1,candy(i+1)++;//从右到左扫：if i-1 > i && candy(i-1)<=candy(i), candy(i-1)=candy(i)+1;vector<int> candy(ratings.size(), 1);for (int i = 0; i < ratings.size() - 1; i++)//from left to right.if (ratings[i] < ratings[i + 1])candy[i + 1] = candy[i] + 1;for (int i = ratings.size() - 1; i > 0; i--)//from right to left.if (ratings[i] < ratings[i - 1] && candy[i] >= candy[i - 1])candy[i - 1] = candy[i] + 1;int sum = 0;for (int i = 0; i < candy.size(); i++) sum += candy[i];return sum;}
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 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]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

• 1 <= people.length <= 2000
• 0 <= hi <= 106
• 0 <= ki < people.length
• 题目数据确保队列可以被重建

分析：

核心思路是，先排序，再插入。why???

身高降序排序：首先处理较高的人，确保较高的人已经放到正确的位置后，身高较低的人再插入时就不需要考虑身高大于自己的人。

按 k 升序处理相同身高的人：对于身高相同的人，较小的 k 值代表他前面需要站的人更少，插入顺序决定了前面人的排布，因此按照 k 值升序插入能确保结果的正确性。

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {vector<vector<int>> res;sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);});//lambda 表达式for (auto p : people) {res.insert(res.begin() + p[1], p);}return res;}
};

---

有些眼生的表达：

//如果你不习惯看 lambda 表达式，我们可以把它拆分成普通函数：
bool compare(vector<int>& a, vector<int>& b) {return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
}sort(people.begin(), people.end(), compare);

for (auto& p : people)

这部分是一个 范围基的 for 循环，用来遍历 people 数组中的每个元素。

• people 是一个二维数组，形如 {{身高, k}, {身高, k}, ...}。
• auto& p 的意思是，p 是 people 数组中的每个元素，类型是 vector<int>&，也就是每个人的身高和 k 值组成的数组 [身高, k]。
• 通过 auto，编译器会自动推导出 p 的类型。

举个例子，如果 people 是 {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}}，那么在这段代码中，p 依次会取值为：

cpp复制代码
{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}

---

其实我一开始用了回溯法，天呐，真的能成功！但是只通过了16/36个样例，然后就时间超限了，应该是复杂度太高了。

class Solution {
public:vector<vector<int>> ans;bool check(vector<vector<int>> queue,vector<int> p) {int h=p[0];int k=p[1];int sum=0;for(int i=0;i<queue.size();i++) {if(queue[i][0]>=h ) {sum++;}}if(sum==k)return true;elsereturn false;}void backtracking(vector<vector<int> > &res, vector<vector<int> > people, int index) {if(index==people.size()) {ans=res;return;}for(int i=0;i<people.size();i++) {if(res.empty()&&people[i][1]!=0) {continue;}if(check(res,people[i])) {res.push_back(people[i]);backtracking(res,people,index+1);res.pop_back();}}}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {vector<vector<int>> res;backtracking(res,people,0);return ans;}
};

gpt是这样跟我说的：可能的原因是

回溯搜索效率低：每次递归调用时，check 函数会遍历 res 列表，检查每个人的身高是否符合条件。对于每次递归，check 的时间复杂度是 O(n)，这样每次递归都需要进行一次 O(n) 的检查。

重复计算：回溯中的每个分支都可能会重复尝试同样的状态，导致了大量的重复计算。比如，check 函数中遍历所有已有的人的身高来计算是否符合条件，这对于大规模输入时会变得非常慢。