题解 | #信封嵌套问题#
信封嵌套问题
http://www.nowcoder.com/practice/9bf77b5b018d4d24951c9a7edb40408f
题意:
- 给 n 个信封的长度和宽度。如果信封 A 的长和宽都小于信封 B ,那么信封 A 可以放到信封 B 里,请求出信封最多可以嵌套多少层。
方法一:动态规划
如下方法二中的解题思路,不同之处是在于寻找dp中不小于letters[i][1]的最小值直接简单遍历寻找.
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ //排序的比较函数,长越小排前面,长相同宽不同的宽越大排前面 static bool cmp(vector<int>&a,vector<int>&b){ if(a[0]==b[0]){ return a[1]>b[1]; }else{ return a[0]<b[0]; } } //寻找nums数组中比target大的最小值 int search(vector<int> nums,int target){ for(int i=0;i<nums.size();i++){ if(nums[i]>target) return i; } return -1; } int maxLetters(vector<vector<int> >& letters) { // write code here int n=letters.size(); if(n==0) return 0; //排序 sort(letters.begin(),letters.end(),cmp); //动态数组dp存信封宽度 vector<int> dp; dp.push_back(letters[0][1]); //遍历信封letters,更新数组dp for(int i=1;i<n;i++){ int width=letters[i][1]; if(width>dp.back()) dp.push_back(width); //在数组dp中,找比width大的最小值,并将其替换为width。 else{ int index= search(dp,width); dp[index]=width; } } //dp的长度即为最终返回值 return dp.size(); } };
复杂度分析:
时间复杂度:,遍历数组lettes , 寻找特定值,总。
空间复杂度:,额外数组dp,其大小是信封最多嵌套的层数,当所有信封都能嵌套进去时取最大值n。
方法二:动态规划+二分法
解题思路:
- 本题目是题目————最长递增子序列的变式。
- 参考该题目的解法,同时由于题目要求时间复杂度O(nlogn),空间复杂度O(n),所以选择使用动态规划加二分法的方法来解决。
- 具体解题方法如下:
1.对二维数组letters排序,排序依照函数cmp的方法,按照长度递增,相同长度宽度递减的顺序。
2.分配动态数组dp,dp[i]---表示嵌套信封为i+1个时,最外层的信封的宽度的最小值。则数组dp的大小为最大嵌套信封个数,即为所求返回值。
3.遍历排序后的数组letters,按照如下方法更新数组dp。
(1)若letters[i][1]>dp.back()--->dp.push_back(letters[i][1]);
(2)若letters[i][1]<=dp.back()--->寻找dp中不小于letters[i][1]的最小值,寻找时使用二分法,如下函数dichotomy()所示,并将其更新为letters[i][1]。
4.遍历完毕,返回值dp.size()。
图解如下:
代码如下:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ //排序的比较函数,长越小排前面,长相同宽不同的宽越大排前面 static bool cmp(vector<int>&a,vector<int>&b){ if(a[0]==b[0]){ return a[1]>b[1]; }else{ return a[0]<b[0]; } } //二分法寻找当前数组nums中比target大的最小值,或者跟target一样大的,返回索引。 //其中数组nums严格递增,且nums中必定存在比target大或者与target一样大的 int dichotomy(vector<int> nums,int target){ int left=0,right=nums.size()-1; int cur; while(true){ cur=left+(right-left)/2; if(nums[cur]<target){ if(nums[cur+1]>target){ //nums[cur]<target<nums[cur+1] return cur+1 return cur+1; } else left=cur; } else if(nums[cur]>target){ if(cur==0||nums[cur-1]<target) //nums[0]>target or nums[cur-1]<target<nums[cur] return cur return cur; else right=cur; } else{ return cur; } } return -1; } int maxLetters(vector<vector<int> >& letters) { // write code here int n=letters.size(); if(n==0) return 0; //排序 sort(letters.begin(),letters.end(),cmp); //动态数组dp存信封宽度 vector<int> dp; dp.push_back(letters[0][1]); //遍历信封letters,更新数组dp for(int i=1;i<n;i++){ int width=letters[i][1]; if(width>dp.back()) dp.push_back(width); //在数组dp中,找比width大的最小值,并将其替换为width。 else{ int index= dichotomy(dp,width); dp[index]=width; } } //dp的长度即为最终返回值 return dp.size(); } };
复杂度分析:
时间复杂度:,遍历数组lettes , 在数组dp中利用二分法寻找特定值,总。
空间复杂度:,额外数组dp,其大小是信封最多嵌套的层数,当所有信封都能嵌套进去时取最大值n。