题解 | #信封嵌套问题#

信封嵌套问题

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)$

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-10 09:46
宁夏大学_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议