没有输出的输入是不完整的

0%

leetcode-406-QueueReconstructionbyHeight

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

这道题目不是很难，但是思路也很好玩.
通过这道题，我们还可以顺便掌握c++11中刚刚引入的lambda表达式，非常棒！

题目描述

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

sample

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

贪心算法。

详细解释

最开始先排序，按照如下规则进行排序

1
2
如果第一个元素不等，那么大的在前。
如果第一个元素相等，那么第二个元素小的在前。

所以变化如下。

  1. 初始状态：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
  2. 排序之后：[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

接下来从第二个元素开始插入，按照如下规则进行排序。

1
2
将两个数构成的数组插入到数组中第二个数的位置。
如将[6,1]插入到1号位置，将[5,2]插入到2号位置，注意这个地方要从前往后一次的进行插入。

插入之后的变化依次如下,这里可以从第二个元素开始进行判断

  1. 插入[7,1]元素：[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
  2. 插入[6,1]元素：[[7,0], [6,1], [7,1], [5,0], [5,2], [4,4]]
  3. 插入[5,0]元素：[[5,0], [7,0], [6,1], [7,1], [5,2], [4,4]]
  4. 插入[5,2]元素：[[5,0], [7,0], [5,2], [6,1], [7,1], [4,4]]
  5. 插入[4,4]元素：[[5,0], [7,0], [5,2], [6,1], [4,4]，[7,1]]

巧妙之处

  1. 要学会使用lambda表达式，也就是如下的代码。
1
2
3
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表达式那么就需要写成如下模样。

1
2
3
4
5
static bool cmp(vector<int>& a, vector<int> b){
    return ((a[0] > b[0]) ||(a[0] == b[0] && a[1] < b[1]));
}
# 然后调用的时候如下
sort(people.begin(),people.end(),cmp);
  1. 发现排序之后整个vector可以插入的位置刚刚好是vector中第二个元素的位置。

解题代码

原始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(),
             [](vector<int>& a,vector<int>& b){
                 return ((a[0] > b[0]) ||(a[0] == b[0] && a[1] < b[1]));
             }
            );

        for(int i = 1; i < people.size(); i++ ){
            auto p = people[i]; 
            if(p[1] != i){
                people.erase(people.begin()+i);
                people.insert(people.begin() + p[1],p);   
            }
        }
        return people;
    }
};

升级代码

上面的那种方法速度比较满，原因在于是在原数组上进行插入同时还要进行删除操作，而如果我们直接新建一个vector来保存结果，那么就只需要插入就可以了，然后速度会有很大的提升。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){
        return (a[0] > b[0] ||(a[0]==b[0] && a[1] < b[1]));
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(),cmp);
        
        vector< vector<int> > ans;
        for(int i = 0; i < people.size(); i++ ){
            auto p = people[i]; 
            ans.insert(ans.begin()+p[1],p);
        }
        return ans;
    }
};

再次升级代码

为了代码好看，可以再次升级代码，使用增强的for循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){
        return (a[0] > b[0] ||(a[0]==b[0] && a[1] < b[1]));
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(),cmp);
        
        vector< vector<int> > ans;
        for(auto p:people){
            ans.insert(ans.begin()+p[1],p);
        }
        return ans;
    }
};

以上，本题结束。