406. Queue Reconstruction by Height（队列排序根据高度）

左手的ㄟ右手 2023-02-13 00:23 16阅读 0赞

题目：  
假设您有排队的人的随机列表。每个人都用一对整数描述(h, k)，其中h代表该人的身高，k是该人前面且身高大于或等于的人数h。编写算法以重建队列。

注意：  
人数少于1,100。

思路：  
先找出最大的那一个（或多个——相等），按照k排序，后面小的数依次插入进来，完全按照k插入。因为此时进来的数一定小于已经排好了的数的。此时后面的数的 k 就是它应该在的位置。因为随便隔k个数都是大于该数的。  
这种方式将每个元素（h,k) 设置为一个整体  
这里麻烦的就是对于pair和vector的转换问题  
新温习到了三个部分

1.  lambda表达式
2.  make\_pair<int ,int >(x, y)
3.  sort

code：

class Solution { 
    //这一题学到了个lambda，make_pair<T1,T2>(),sort三个部分
    public:
        vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { 
            vector<pair<int, int>> vec;
            for (auto person : people)
            { 
                pair<int, int> t(person[0], person[1]);
                vec.push_back(t);
            }
            sort(vec.begin(), vec.end(), [](pair<int, int> p1, pair<int, int>p2) { 
                return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
                });
            //按照h第一，k第二的方式排序。h是递减，k是递增
    
            vector<pair<int, int>> res;
             vector<vector<int>> ans;
            for (auto fac : vec) 
                res.insert(res.begin() + fac.second, fac);
             
            for (auto x : res) { 
                    vector<int> tmp(2);         //错误在这里，没有将vector设置大小就用下标访问
                    tmp[0] = x.first;
                    tmp[1] = x.second;
                    ans.push_back(tmp);
                }
    
            return ans;
        }
    };

1.  lambda表达式
2.  make\_pair<int ,int >(x, y)
3.  sort

1  
lambda 表达式：是一个可调用对象。可调用对象还有函数，函数指针。格式：  
\[ capture list \] ( parameter list）return type \{ function body　\};  
capture list 是一个lambda 在的函数中定义的局部变量的列表（通常 空），接下来是和普通函数一样。参数列表和返回类型可以忽略不写。（如果忽略返回类型，lambda 根据函数体中的代码推断 返回类型。  
\[ \] 中的表示在函数体中会用到的调用这个lambda的函数中的局部变量。  
& var 可以引用捕获。  
2  
pair 是 标准库类型，不是一个容器。头文件在 utility 中。一个pair 保存两个数据成员，是一个生成特定类型的模板。  
可以的操作

pair <T1,T2> p;
    make_pair(v1,v2)			#返回一个用v1，v2初始化的pair
    p1 == p2;		#可以比较的

3  
std:: sort 函数。[std::sort][std_sort]  
这是一个模板函数，在这里用到的是

template< class RandomIt, class Compare >
    void sort( RandomIt first, RandomIt last, Compare comp );
    也可以用lambda表达式

[std_sort]: https://en.cppreference.com/w/cpp/algorithm/sort