力扣热题刷题记录
文章目录- 系列文章目录
- 前言
- 一、背景
- 二、我的思路
- 三、官方的思路
- 1.低到高排序，站位
- 2.高到低排序，站位
- 总结
每天进步一点点！！
一、背景给一群人，有他们的两个信息，第一个是身高信息，第二个是在他们前面的人当中比他们高（>=）的人有几个，根据这些信息，将他们排序，使得符合要求。
数据格式为 [ 身高，比自己高的人的个数 ]
如下图：
题目：
二、我的思路来源：力扣
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/
不好意思，又不会做，但是代码是我自己写的，思路是看官方提示的。
描述一下思路：
总共有n个空位置。对原始的数据先排个序，对于每一个身高由低到高进行排序。每取一个人的信息，说明它前面的人的身高不影响它站在哪里，所以，它前面有ki个比他高的，那么就留ki个空位给那些高个子，自己站在第ki +1的位置即可。
代码如下 ：
class Solution {
public:
static bool cmp(vectora,vectorb){
if(a[0]!=b[0]) return a[0] b[1];//k值大的放在前面
}
vector> reconstructQueue(vector>& people) {
//标签是贪心，那就试试
//还是看题解了，干
vector > my_vec(people.size(),vector(people[0].size(),-1));
sort(people.begin(),people.end(),cmp);
//cout<
这里注意两个事项：
第一，cmp比较函数，按身高从低到高，但是比自己高的人数 则按得是从大到小排序。道理很简单，身高一样，要使得前面的人对自己的站位不构成影响，根据比自己高的人数，数值大的先去站位置（仔细想想，数值小的去战队了，那么当前元素会受到前面的人的影响，因为一样高）。
第二，cmp函数放在类里面，是非静态成员函数指针，而sort函数要求的是静态成员函数指针，所以需要加一个static，要不然，就放在这个类外面。（究其原因，是因为类成员函数依赖于某个具体的对象）
三、官方的思路
1.低到高排序，站位
同我上面说的，代码附上：
class Solution {
public:
vector> reconstructQueue(vector>& people) {
sort(people.begin(), people.end(), [](const vector& u, const vector& v) {
return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
});
int n = people.size();
vector> ans(n);
for (const vector& person: people) {
int spaces = person[1] + 1;
for (int i = 0; i < n; ++i) {
if (ans[i].empty()) {
--spaces;
if (!spaces) {
ans[i] = person;
break;
}
}
}
}
return ans;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
来源：力扣（LeetCode）
2.高到低排序，站位
高到低排序，说明后面的人都受到前面的人的影响，就是说，每取一个人，就要看前面的人是什么情况（剩下的人都不对当前元素构成影响），这个可以根据下标来看。
由于剩下的人都不对当前元素构成影响，所以只需要看已有的站队情况，数一数前面站好的人比自己高的情况，这样就可以直接站到他们后面。
代码如下：
class Solution {
public:
static bool cmp(vectora,vectorb){
if(a[0]!=b[0]) return a[0]>b[0];
else return a[1] < b[1];//k值小的放在前面
}
vector> reconstructQueue(vector>& people) {
//由高到低排序
vector > my_vec;
sort(people.begin(),people.end(),cmp);
for (int i=0;i= people[i][0] )
count++;
}
}
return my_vec;
}
};
官方更牛：
思维：后面的人不会构成影响，故这个Ki就是自己的最终位置
class Solution {
public:
static bool cmp(vectora,vectorb){
if(a[0]!=b[0]) return a[0]>b[0];
else return a[1] < b[1];//k值小的放在前面
}
vector> reconstructQueue(vector>& people) {
//由高到低排序
vector > my_vec;
sort(people.begin(),people.end(),cmp);
for (int i=0;i
我还是没反应过来啊啊啊！！
一个是占位置，另一个是直接插入。牛！
总结
思路很重要，有了思路，写代码就是手到擒来！！
喜欢就点个赞叭！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）