网站经营性备案多少钱,西宁网站建设,广西建设网官网培训中心,2022年世界职业技能大赛LeetCode刷题day18——贪心 135. 分发糖果分析#xff1a; 406. 根据身高重建队列分析#xff1a;for (auto p : people) 昨天写了一道#xff0c;今天写了一道#xff0c;都有思路#xff0c;却不能全整对。昨天和小伙伴聊天#xff0c;说是因为最近作业多#xf… LeetCode刷题day18——贪心 135. 分发糖果分析 406. 根据身高重建队列分析for (auto p : people) 昨天写了一道今天写了一道都有思路却不能全整对。昨天和小伙伴聊天说是因为最近作业多昨天没打题负罪感满满养成习惯了都。
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.length1 n 2 * 1040 ratings[i] 2 * 104
分析
如果它ratings大它的candy要比邻居多我一开始是在同一个循环里同时左右检查这是搞不清楚的要分开扫。
从左到右扫if i i1,candy(i1);从右到左扫if i-1 i candy(i-1)candy(i), candy(i-1)candy(i)1;
class Solution {
public:int candy(vectorint ratings) {//从左到右扫if i i1,candy(i1);//从右到左扫if i-1 i candy(i-1)candy(i), candy(i-1)candy(i)1;vectorint 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 20000 hi 1060 ki people.length题目数据确保队列可以被重建
分析
核心思路是先排序再插入。why???
身高降序排序首先处理较高的人确保较高的人已经放到正确的位置后身高较低的人再插入时就不需要考虑身高大于自己的人。
按 k 升序处理相同身高的人对于身高相同的人较小的 k 值代表他前面需要站的人更少插入顺序决定了前面人的排布因此按照 k 值升序插入能确保结果的正确性。
class Solution {
public:vectorvectorint reconstructQueue(vectorvectorint people) {vectorvectorint res;sort(people.begin(), people.end(), [](vectorint a, vectorint 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(vectorint a, vectorint 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 数组中的每个元素类型是 vectorint也就是每个人的身高和 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:vectorvectorint ans;bool check(vectorvectorint queue,vectorint p) {int hp[0];int kp[1];int sum0;for(int i0;iqueue.size();i) {if(queue[i][0]h ) {sum;}}if(sumk)return true;elsereturn false;}void backtracking(vectorvectorint res, vectorvectorint people, int index) {if(indexpeople.size()) {ansres;return;}for(int i0;ipeople.size();i) {if(res.empty()people[i][1]!0) {continue;}if(check(res,people[i])) {res.push_back(people[i]);backtracking(res,people,index1);res.pop_back();}}}vectorvectorint reconstructQueue(vectorvectorint people) {vectorvectorint res;backtracking(res,people,0);return ans;}
};gpt是这样跟我说的可能的原因是
回溯搜索效率低每次递归调用时check 函数会遍历 res 列表检查每个人的身高是否符合条件。对于每次递归check 的时间复杂度是 O(n)这样每次递归都需要进行一次 O(n) 的检查。
重复计算回溯中的每个分支都可能会重复尝试同样的状态导致了大量的重复计算。比如check 函数中遍历所有已有的人的身高来计算是否符合条件这对于大规模输入时会变得非常慢。
