数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的俄罗斯套娃信封
假设我们有一些信封，这些信封的高度和宽度值作为对出现。如果第二个信封的高度和宽度都小于第一个信封的高度和宽度，则我们可以将一个信封放入另一个信封中。那么，我们最多可以将多少个信封放入其他信封中呢？因此，如果输入类似于 [[5,5], [6,4], [6,8], [2,3]]，则输出将为 3，因为最小的信封是 [2,3]，然后是 [5,5]，然后是 [6,8]。
为了解决这个问题，我们将遵循以下步骤：
- 根据高度对数组 v 进行排序，当高度相同时，比较宽度
- 如果 v 的大小与 0 相同，则：
- 返回 0
- 定义一个数组 ret
- 对于初始化 i := 0，当 i < v 的大小，更新（i 增加 1），执行：
- 定义一个数组 temp = v[i]
- x := temp[1]
- low := 0, high := ret 的大小, curr := 0
- 当 low <= high 时，执行：
- mid := low + (high - low) / 2
- 如果 ret[mid] < temp[1]，则：
- curr := mid + 1
- low := mid + 1
- 否则
- high := mid - 1
- 如果 curr < 0，则：
- 忽略以下部分，跳到下一次迭代
- 如果 curr >= ret 的大小，则：
- 将 temp[1] 插入到 ret 的末尾
- 否则
- ret[curr] := temp[1]
- 返回 ret 的大小
让我们看看以下实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
if(a[0] == b[0])return a[1] > b[1];
return a[0] < b[0];
}
int maxEnvelopes(vector<vector<int>>& v) {
sort(v.begin(), v.end(), cmp);
if(v.size() == 0)return 0;
vector <int> ret;
for(int i = 0; i < v.size(); i++){
vector <int> temp = v[i];
int x = temp[1];
int low = 0;
int high = ret.size() -1;
int curr = 0;
while(low <= high){
int mid = low + (high - low) / 2;
if(ret[mid]<temp[1]){
curr = mid + 1;
low = mid + 1;
}else{
high = mid - 1;
}
}
if(curr < 0) continue;
if(curr >= (int)ret.size()){
ret.push_back(temp[1]);;
}else{
ret[curr] = temp[1];
}
}
return ret.size();
}
};
main(){
Solution ob;
vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
cout << (ob.maxEnvelopes(v));
}输入
{{5,5}, {6,4}, {6,8}, {2,3}}输出
3
更新于: 2020年6月1日
421 次浏览
广告