给定一个二维int的数组actors,每个元素对应两个值,分别代表一个演员的身高和体重。要求一个演员站在另一个演员的肩膀上叠起来,且上面的人要比下面的人轻,下面的人要比上面的人高。同时给定演员总数n,要求返回最多能叠的人数。保证总人数小于等于500。
测试样例:
[[1,2],[3,4],[5,6],[7,8]],4
返回:4
import java.util.*;
public class Stack {
public int getHeight(int[][] actors, int n) {
// write code here
Comparator<int[]> com = new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if(a[0] < b[0])
return -1;
else if(a[0] > b[0])
return 1;
else {
if(a[1] < b[1])
return -1;
else if(a[1] > b[1])
return 1;
else
return 0;
}
}
};
Arrays.sort(actors, com);
int[] res = new int[n];
res[0] = 1;
int max = 1;
for(int i = 1; i < n; i++) {
int t = 0;
for(int j = 0; j < i; j++) {
if(actors[i][1] > actors[j][1])
t = Math.max(t, res[j]);
}
res[i] = t+1;
max = Math.max(max, res[i]);
}
return max;
}
}
/* 哈哈,吃了一个饭回来就想到办法了。参考前面一题的方法(求解最长递增子序列),这里的二维数组可以简化为一维的问题。因为身高是递增顺序的情况下,求出的最大体重递增子序列其身高一定也是递增的序列。 */ class Stack { public: int getHeight(vector<vector<int> > actors, int n) { // write code here if(n == 0) return 0; vector<int> dp(n,1); int i,j; int max = 0; sort(actors.begin(),actors.end(),cmb); for(i=1;i<n;i++){ for(j=0;j<i;j++){ if(actors[i][1]>actors[j][1]){ if(dp[i]<(dp[j]+1)) dp[i] = dp[j]+1; } } } for(i=0;i<n;i++){ if(max<dp[i]) max = dp[i]; } return max; } static bool cmb(vector<int> num1,vector<int> num2){ return num1[0]<num2[0]; } };
class Stack { public: static bool cmp(vector<int> a, vector<int> b){ return a[0] < b[0]; } int getHeight(vector<vector<int> > actors, int n) { int Max = 0, dp[n]; memset(dp,0,sizeof(dp)); sort(actors.begin(), actors.end(), cmp); dp[0] = 1; for(int i=1;i<n;i++){ int t = 0; for(int j=0;j<i;j++) if(actors[i][1] > actors[j][1]) t = max(t,dp[j]); dp[i] = t + 1; Max = max(Max, dp[i]); } return Max; } };
import java.util.*; /* 我的思路:先按照身高排序,身高相同就按体重排序, 在排序好的二维数组中找最长的连续递增子序列的长度(动态规划) dp[i]表示前i个人中的最长递增序列长度 状态转移:(由于已经对身高进行过排序) 当arr[i][1]>arr[i-1][1]时,dp[i] = max(dp[i],dp[i-1]+1); 否则dp[i] = max(dp[i],dp[i-1]); 边界情况dp[i]初始值为1 */ public class Stack { public int getHeight(int[][] actors, int n) { // write code here //排序 Arrays.sort(actors, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if (o1[0]==o2[0]) return o1[1]-o2[1]; return o1[0]-o2[0]; } }); //排序 /* for(int i = 0;i<n;i++){ for(int j = i+1;j<n;j++){ if(actors[i][0] > actors[j][0]){ int temp = actors[i][0]; actors[i][0] = actors[j][0]; actors[j][0] = temp; //交换身高 temp = actors[i][1]; actors[i][1] = actors[j][1]; actors[j][1] = temp; }else if(actors[i][0] == actors[j][0]){ if(actors[i][1] > actors[j][1]){ int temp = actors[i][0]; actors[i][0] = actors[j][0]; actors[j][0] = temp; //交换身高 temp = actors[i][1]; actors[i][1] = actors[j][1]; actors[j][1] = temp; } } } }*/ //动态规划方面 int[] dp = new int[n]; dp[0] = 1; int max = Integer.MIN_VALUE; for(int i = 1;i<n;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(actors[j][1] < actors[i][1]){ dp[i] = Math.max(dp[i],dp[j]+1); } } max = Math.max(dp[i],max); } return max; } }
class Stack { public: int getHeight(vector<vector<int> > actors, int n) { // write code here sort(actors.begin(),actors.end()); vector<int>dp{actors[0][1]}; int k=0,flag=1; for(int i=1;i<n;i++) { if (actors[i][0] == actors[i - 1][0] && flag==1 ) //判断相同的是否是push_back加入的 continue; //如果是相同的身高都不要了,不是就可以继续执行 flag = 0; int l=0,r=k; while(l<=r) { int mid=(r+l)/2; if(dp[mid]>=actors[i][1]) { r=mid-1; } else l=mid+1; } if(l>k)dp.push_back(actors[i][1]),k++,flag=1;//flag标志加入到尾部 else dp[l]=actors[i][1]; } return k+1; } };身高排序,体重最长升序子数列,解决相同身高的,就看前面同一身高的是这么进去的, 如果是替换,则后面的相同身高还得判断, 如果是尾部插入,则后面相同身高的直接continue [1,2][2,1][2,5],这种情况相同身高是替换,[2,5]还需判断, [1,2][2,3][2,5]这种情况[2,3]尾部插入,[2,5]就不需要判断了直接continue 注:此最长升序数列,是二分法维护一个升序数组, 进来一个数a若能找到第一个比a大的直接替换,不能找到,a加入数组尾部, 最后数组的长度就是升序数列的长度
""" 求数组arr的最长递增子序列 创建一个列表res,res[i]用来存放以arr[i]结尾的最长递增子序列的长度 为了求出res[i],要将arr[i]与arr[j]比较,其中j=[0,i),而如果arr[j]<arr[i], arr[i]自然可以放在以arr[j]的后面,这时res[i]=res[j]+1,遍历所有的j,找到一个 可以让res[i]最大的值,这个值便是以arr[i]结尾的最长递增子序列的长度 """ def getMax(arr, n): dp = [1] * n for i in range(n): for j in range(i): if arr[i] > arr[j] and dp[j]+1 > dp[i]: dp[i] = dp[j] + 1 return max(dp) class Stack: """ 这道题可以先将列表按身高排序,然后求体重的最长递增子序列 """ def getHeight(self, actors, n): actors.sort() arr = [li[1] for li in actors] return getMax(arr, n)
先排序,然后添加判断条件,与上题类似 class Stack { public: int getHeight(vector<vector<int>> actors, int n) { int maxCount = 1; sort(actors.begin(),actors.end()); vector<int> dp(n, 1); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) if (actors[j][0] < actors[i][0] && actors[j][1] < actors[i][1]) dp[i] = max(dp[i], dp[j] + 1); maxCount = max(maxCount, dp[i]); } return maxCount; } };
bool cmp(vector<int> a, vector<int> b) { return a[0]<b[0];//按照第一个参数,顺序排列 } class Stack { public: int getHeight(vector<vector<int> > actors, int n) { if(actors.empty()) return 0; sort(actors.begin(),actors.end(),cmp); vector<int> dp(n,0); dp[0]=1; int res=0; for(int i=1;i<n;i++) { int tmax=0; for(int j=0;j<i;j++) { if(actors[i][1]>actors[j][1]) tmax=max(tmax,dp[j]); } dp[i]=tmax+1; res=max(res,dp[i]); } return res; } };
//看了《程序员面试金典》书上的提升,先将身高排序,然后对体重查找最长递增子系列; //看了大家的代码,各种方法都有,有的人用multimap排序的。 class Stack { public: int getHeight(vector<vector<int> > actors, int n) { // write code here if(n<=0) return 0; sort(actors.begin(),actors.end(),comp); int* help=new int[n]; for(int i=0;i<n;i++)//初始化 help[i]=1; int max=0; for(int i=1;i<n;i++) { int j=0; while(j<i) { if(actors[j][1]<=actors[i][1] && help[j]>help[i]-1) help[i]++; j++; } if(help[i]>max) max=help[i]; } return max; } static bool comp(vector<int> a,vector<int> b) { return a[0]<b[0]; } };
# -*- coding:utf-8 -*- class Stack: def getHeight(self, actors, n): actors.sort() men = [weight for _, weight in actors] return self.getHeight1(men, n) def getHeight1(self, men, n): dp = [0] * n dp[0] = 1 bs = [0] * n bs[0] = men[0] # 在bs中找到第一个比x大的数并替换 def binary_search(x, end): i = 0 j = end while i <= j: mid = (i + j) / 2 if x > bs[mid]: i = mid + 1 else: j = mid - 1 end = max(end, i) bs[i] = x return i, end end = 0 # bs length for i in range(1, n): val, end = binary_search(men[i], end) dp[i] = val+1 return max(dp)
int fun(vector<int> men, int n) { vector<int> ret(n,1); ret[0]=1; int maxlen=1; for(int i=1;i<n;i++) { for(int j=i-1;j>=0;j--){ if(men[i]>men[j]) ret[i]=max(ret[i],ret[j]+1); } maxlen=max(ret[i],maxlen); } return maxlen; } int getHeight(vector<vector<int> > actors, int n) { multimap<int,int> m; multimap<int,int>::iterator mit; vector<int> tmp; for(int i=0;i<n;i++) m.insert(pair<int,int>(actors[i][0],actors[i][1])); for(mit=m.begin();mit!=m.end();mit++) tmp.push_back(mit->second); return fun(tmp,n); }
//总感觉用身高排序,找体重的最大子序列 //或者用体重找身高,总感觉缺了点什么,就写了两个。 class Stack { public: int getHeight(vector<vector<int> > actors, int n) { // write code here if(n==0) return 0; int result1=0,result2=0; result1=getHeightByHeight(actors,n); result2=getHeightByWeight(actors,n); return max(result1,result2); } int getHeightByHeight(vector<vector<int> > actors,int n){ vector<int> f(n,1); int result=1; sort(actors.begin(),actors.end(),compare1); for(int i=1;i<n;++i) for(int j=0;j<i;++j){ if(actors[i][1]>actors[j][1]) f[i]=max(f[i],f[j]+1); } for(int i=0;i<n;++i) result=max(result,f[i]); return result; } int getHeightByWeight(vector<vector<int> > actors,int n){ vector<int> f(n,1); int result=1; sort(actors.begin(),actors.end(),compare2); for(int i=1;i<n;++i) for(int j=0;j<i;++j){ if(actors[i][0]>actors[j][0]) f[i]=max(f[i],f[j]+1); } for(int i=0;i<n;++i) result=max(result,f[i]); return result; } static bool compare1(vector<int> nums1,vector<int> nums2){ return nums1[0]<nums2[0]; } static bool compare2(vector<int> nums1,vector<int> nums2){ return nums1[1]<nums2[1]; } };
import java.util.*; public class Stack { public int getHeight(int[][] actors, int n) { // write code here Arrays.sort(actors, new Comparator<int[]>() {//排序 身高升序,体重降序 @Override public int compare(int[] o1, int[] o2) { if(o1[0]!=o2[0]) return o1[0]-o2[0]; else return o2[1]-o1[1]; } } ); int[] heights = new int[n]; heights[0] = actors[0][1]; int cur =0;//heights有效数字最后一位 下标 for(int i=1;i<n;i++){ int index= getIndex(heights,0,cur,actors[i][1]); if(index>cur){ cur++; heights[index]=actors[i][1]; }else{ heights[index]=actors[i][1]; } } return ++cur;//heights有效数字最后一位 下标 即最大叠加人数 } static int getIndex(int[] heights,int l,int r,int height){ int index = r+1; while(l<=r){ int mid = l+((r-l)>>1); if(heights[mid]<height){ l=mid+1; }else{ r=mid-1; index=mid; } } return index; } }
class Stack: def getHeight(self, actors, n): # write code here actors.sort(key=lambda b: b[0]) dq = [[actors[0]]] for i in range(1,n): order = [actors[i]] for dqi in dq: if dqi[-1][1] < actors[i][1] and len(dqi) >= len(order): order = dqi + [actors[i]] dq.append(order) return len(max(dq, key=lambda a: len(a)))
class Stack { public: int getHeight(vector<vector<int> > actors, int n) { // write code here memset(dp, 0, sizeof(dp) ); dp[0] = 1; sort(actors.begin(), actors.end(), cmpByHeight); for (int i = 1; i < n; ++i) { dp[i] = 1; for (int j = 0; j < i; ++j) { if (actors[j][1] > actors[i][1] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; } } } int ret = 0; for (int i = 0; i < n; ++i) { ret = max(ret, dp[i]); } return ret; } private: static bool cmpByHeight(vector<int> &a, vector<int> &b) { return a[0] > b[0]; } int dp[503] = {0}; };
class Stack { public: bool static cmp(vector<int> a, vector<int> b){ return a[0] < b[0]; } int getHeight(vector<vector<int> > actors, int n) { vector<int> dp(n, 1); int maxCount = -1; sort(actors.begin(), actors.end(), cmp); for(int i = 1; i < n; i++){ for(int j = 0; j < i; j++) if(actors[i][1] > actors[j][1]) dp[i] = max(dp[i], dp[j]+1); maxCount = max(maxCount, dp[i]); } return maxCount; } };