[各种面试题] 堆放积木

112 阅读 0 评论 74 点赞

我是靠谱客的博主怕黑红牛，这篇文章主要介绍[各种面试题] 堆放积木，现在分享给大家，希望可以做个参考。

有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。

样例：

复制代码

1
2
3
4
5
有7个积木boxes:
[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木，从上到下分别为：
(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6。

题目来源：CRACKING THE CODING INTERVIEW 9.7

其实就是个最长递减子序列的题，先排序，朴素的办法是O(n2)的，如果是一维的话可以用二分查找优化为O(nlong)，但是二维的貌似这个优化行不通。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*积木的定义(请不要在代码中定义该结构)
struct Box {
int vol, weight;
};*/
struct compare
{
bool operator()(const Box& b1,const Box& b2)const
{
if (b1.vol==b2.vol)
return b1.weight>b2.weight;
return b1.vol>b2.vol;
}
};
int maxBoxes(vector<Box> &boxes) {
if (boxes.empty())
return 0;
sort(boxes.begin(),boxes.end(),compare());
vector<int> longest(boxes.size(),1);
for(int i=1;i<longest.size();i++)
{
int t=1;
for(int k=i-1;k>=0;k--)
{
if ( boxes[k].vol >boxes[i].vol &&
boxes[k].weight>boxes[i].weight )
t=max(t,longest[k]+1);
}
longest[i]=t;
}
return *max_element(longest.begin(),longest.end());
}