資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告