我的口试刷题记录-算法-第八天-信封嵌套

仙翁童子子os

来历：知乎
前言

为了预备下个月的秋招校招，天天都在电脑前刷题刷题刷题，只为提升自己的算法水平。
接待大师来会商交换我的解题思绪，相互进修新的题解方式！


明天是我的口试刷题记录-算法-第八天-第3题题目：信封嵌套
题目描写

给 n 个信封的长度和宽度。假如信封 a 的长和宽都小于信封 b ，那末信封 a 可以放到信封 b 里，请求出信封最多可以嵌套几多层。  
  

数据范围： 1≤n≤2×1031 \le n \le 2\times10^31≤n≤2×103 ， 1≤letters[0],letters[1]≤2×1031 \le letters[0], letters[1] \le 2\times10^31≤letters[0],letters[1]≤2×103
   
要求：空间复杂度 O(n) O(n)\ O(n) ，时候复杂度 O(n2) O(n^2) \ O(n2)
要求：空间复杂度 O(n)O(n)O(n) ，时候复杂度 O(nlogn)O(nlogn)O(nlogn)

输入描写：第一行输入一个正整数 n ，暗示信封的数目
后续 n 行每行输入两个正整数暗示信封的长度和宽度

输出描写：输出最多可以嵌套的层数
示例1


输入： 9 3 4 2 3 4 5 1 3 2 2 3 6 1 2 3 2 2 4
输出：4
说明： 从里到外是 (1,2) (2,3) (3,4) (4,5)
示例2


输入： 2 1 4 4 1
输出：1
小我思绪

题目分析：
1.这里需要用到最大上升子序列
2.需要将二维的数组降维：这里先对其中一维数据停止排序
3.这里有一个比力坑的点，就是都要长宽都要小于才可以，所以先对宽停止降序排，再对上停止正序排，便可以避免在求最大上升子序列时选中了等宽的信封
经历分享

从字符串处置到逻辑和Bit运算，直到高级一点的数据结构，很多工具在工作中不见得都能间接用到学到，可是久远看来是需要技能。





想熟练把握一门说话，必须经过大量的练习，刷题，最少需要一两万行的代码量，才能具有一定的编程才能，最少拿到一个功用，怎样去用编程说话去实现它，从现在起头我要开启刷题之路，进步自己的编程水平，还有最重要的口试才能。

本题总结

对即是求解最长上升子序列，先将输入依照升序排列。然后求解。 对于当前信封i有：

• 在此之前多一切嵌套0<=j<i0<=j<i0<=j<i只要满足v.first > v[j].first && v.second > v[j].second记录下最大的嵌套数，然后把i信封套入，dp+1.
  
• 读了一次假题，画蛇添足地讲信封的长宽做了调剂，保证first>second然后就错了，实在题目可以斟酌这一层。
  

代码以下
#include<bits/stdc++.h>
using namespace std;
int solve(vector<pair<int,int>> &v, vector<int> &dp, int n){//递归写法
    if(dp[n] != 0) return dp[n];
    if(n == 0) dp[n] = 1;
    else{
        int mx = 0;
        for(int i = 0; i < n; ++i){
            int tmp = solve(v, dp, i);
            if(v[n].first > v.first && v[n].second > v.second)
                mx = max(tmp,mx);
        }
        dp[n] = mx + 1;
        
    }
    return dp[n];
}
void solve2(vector<pair<int, int>> &v, vector<int> &dp){//递推写法
    dp[0] = 1;
    int i, j;
    for(i = 1; i < v.size(); ++i){
        int mx = 0;
        for(j = 0; j < i; ++j){
            if(v.first > v[j].first && v.second > v[j].second)
                mx = max(dp[j], mx);
        }
        dp = mx + 1;
    }
}
int main(){
    int n;
    cin >>n;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; ++i){
        // int a, b; //对应的假题操纵
        // cin>>a;
        // cin>>b;
        // v.first = max(a,b);
        // v.second = min(a,b);
        cin>>v.first;
        cin>>v.second;
    }
    vector<int> dp(n);
    sort(v.begin(), v.end());
    solve(v, dp, n-1);
    // solve2(v, dp);
    int max_cnt = 0;
    for(int i = 0; i < n; ++i){
        max_cnt = max(max_cnt, dp);
    }
    cout<<max_cnt<<endl;
    return 0;
}
自测运转成果


补一个python3答案：
方式：

• 按宽递增排序后，求长的最长严酷上升子序列，同时要求宽不相称
  

留意：为保证宽不相称，可以使等宽地区内按长逆序排列，这样严酷上升子序列在每组宽中只能取一个长
代码以下：
# 按宽递增排序后，求长的最长严酷上升子序列，同时宽不相称(等宽地区内按长逆序排列即可)

def maxIncSub(arr,col=1):
    # @arr 传入数组
    # @col 按第col列求
    # @return 返回最长严酷上升子序列的长度
    n=len(arr)
    dp=[1]*n
    for i in range(1,n):
        for j in range(i):
            if arr[j][col]<arr[col]:
                dp=max(dp,dp[j]+1)
    return max(dp)


n=eval(input())
letters=[]
for _ in range(n):
    letters.append(list(map(int,input().split())))

# 先按长逆序，后按宽正序，即可使等宽地区内按长逆序排列
letters.sort(key=lambda x:x[1],reverse=True) # O(nlogn)
letters.sort(key=lambda x:x[0]) # 按宽排序 O(nlogn)

print(maxIncSub(letters,1))
原文地址：https://zhuanlan.zhihu.com/p/571611606
免责声明：本帖内容由机械人自动收集于互联网，如加害了您的权益，请联系我们【E-Mail:cb@yoyodoc.com】 我们会实时删除侵权内容，给您带来未便，深感歉意！