题解 | #信封嵌套问题#

信封嵌套问题

http://www.nowcoder.com/practice/9bf77b5b018d4d24951c9a7edb40408f

信封嵌套问题

问题描述:给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。
示例1
输入:[[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
输入:[[1,4],[4,1]]
返回值:1

方法一

思路分析

     首先对所给的信封进行排序,我们需要按照信封的长度length进行升序排序,如果两个信封的长度相同则可以按照其宽度width进行降序排序,之后对宽度寻找最长递增序列,在寻找最长递增序列时使用动态规划的办法。这里需要解释为什么在长度相同的时候要按照其宽度进行降序排序,因为长度相同的信封无法进行嵌套,因此长度相同的信封只能选取一个,如果按照升序排序,那么就会造成无法嵌套但仍归纳为递增序列中造成错误。
动态规划构造最长自增序列的过程以及转移方程:
  • 设置$dp[i]$表示第i个位置上的最长递增序列长度,那么初始化所有位置$dp[i]=1$只有一个元素
  • 寻找$i$位置上的最长递增序列,需要寻找该位置之前左侧所有的元素,如果是递增的,那么$dp[i]=max(dp[i],dp[j]+1)$,其中$j<i$
  • 最后返回$dp$数组中的最大值即为最长递增序列的长度也即信封嵌套的层数

图解



C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0]) return a[1]>=b[1];//长度相同,宽度按照降序排序
        else return a[0]<b[0];//长度按照升序排序
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        if(letters.empty()) return 0;
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//对数组元素排序
        vector<int > dp(n,0);//设置最长递增序列的数组
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)//从i位置之前的位置寻找可能的最长递增序列
            {
                if(letters[i][1]>=letters[j][1])
                {
                    dp[i]=max(dp[i],dp[j]+1);//动态规划的办法寻找每个位置的最长子序列数组
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
        
    }
};

复杂度分析

  • 时间复杂度:两层循环,循环次数为$1+2+3+4+n-1=n*(n-1)/2$,因此时间复杂度为$O(n^2)$
  • 空间复杂度:借助于一个辅助数组用于存放每个位置的最长递增序列长度,因此空间复杂度为$O(n)$

方法二

思路分析

      上面的方法时间复杂度高不符合规定的要求,为提高速度,采取以空间换时间的方式,使用二分法的办法优化动态规划,在求解$dp[i]$的过程中使用二分法的办法优化。先设置一个长度为n的数组ends,初始时ends[0]=letters[0][1],其他位置上的值为0,$ends[b]=c$表示遍历到目前为止,在所有长度为b+1的递增序列中,最小的结尾数是c。每次ends数组存储当前位置之前所有长度为b+1的递增序列中,最小的结尾数是c的元素

图解



C++ 核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0]) return a[1]>=b[1];//长度相同,宽度按照降序排序
        else return a[0]<b[0];//长度按照升序排序
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        if(letters.empty()) return 0;
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//对数组元素排序
        vector<int > dp(n,1);//设置最长递增序列的数组
        dp[0]=1;
        vector<int> ends(n);
        ends[0] = letters[0][1];//ends[b]=c,则表示遍历到目前为止,在所有长度为b+1的递增序列中,最小的结尾数是c
        int right = 0;
        int ll = 0;
        int rr = 0;
        int mm = 0;
        for (int i = 1; i < n; ++i) 
        {
            ll = 0;
            rr = right;
            while (ll <= rr) 
            {
                mm = (ll + rr) / 2;
                if (letters[i][1] > ends[mm]) 
                {
                    ll = mm + 1;
                } 
                else 
                {
                    rr = mm - 1;
                }
            }
            right = max(right, ll);
            ends[ll] = letters[i][1];
            dp[i] = ll + 1;
        }

        return *max_element(dp.begin(),dp.end());//返回最长递增序列的长度
        
    }
};

复杂度分析

  • 时间复杂度:循环遍历一次,每次查找为二分查找,因此时间复杂度为
  • 空间复杂度:借助于两个数组,因此空间复杂度为$O(n)$
全部评论

相关推荐

双飞二本嵌入式求拷打我是在&nbsp;BOSS&nbsp;上投递的简历,好多都没人回复,这是开场白和简历求大神帮忙看看。您好!我是2025届应届生,最快可在一周内上岗,能够实习六个月以上,并接受加班。以下是我的核心优势和相关经验:1.&nbsp;嵌入式开发能力:&nbsp;&nbsp;&nbsp;熟练掌握STM32系列单片机及其外设(如GPIO、定时器、ADC、DAC、I2C、SPI、UART等),能够独立完成硬件驱动开发和调试。&nbsp;&nbsp;熟悉FreeRTOS实时操作系统,具备多任务调度和资源管理经验。&nbsp;&nbsp;熟悉LVGL图形库开发,能够实现嵌入式设备的图形界面设计。2.&nbsp;硬件设计能力:&nbsp;&nbsp;&nbsp;具备PCB设计经验,曾为2023年工创赛物流搬运赛道设计小车主板,带领团队获得国家级银奖。&nbsp;&nbsp;&nbsp;熟悉硬件原理图分析,能够快速理解并调试硬件电路。3.&nbsp;机器人开发与竞赛经验:&nbsp;&nbsp;&nbsp;在全国大学生智能车竞赛、ROS机器人竞赛中多次获得国家级奖项,具备丰富的机器人开发经验。&nbsp;&nbsp;&nbsp;熟悉Linux环境,对ROS和ROS&nbsp;2有一定了解,能够进行机器人系统的开发与调试。4.&nbsp;编程能力:&nbsp;&nbsp;&nbsp;熟悉C/C++,熟悉Python,能够高效完成嵌入式开发和算法实现。&nbsp;&nbsp;&nbsp;具备良好的代码规范和文档编写能力。5.&nbsp;团队协作与领导能力:&nbsp;&nbsp;&nbsp;在多个项目中担任核心开发或团队负责人,具备良好的沟通能力和团队协作精神。&nbsp;&nbsp;&nbsp;在工创赛中带领团队完成项目规划、任务分配和技术攻关,展现了较强的领导力。我对嵌入式开发、机器人技术和智能硬件充满热情,期待加入贵公司,与团队共同成长,为公司创造价值!如果有合适的岗位,欢迎随时联系我,期待进一步沟通!
沉淀一会:嵌入式就是狗屎
点赞 评论 收藏
分享
02-05 08:18
四川大学 Java
在思考的熊熊很讨厌吃香菜:不是,我门头沟学院呢?这都没排上?
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务