给定一个二维int的数组actors，每个元素对应两个值，分别代表一个演员的身高和体重。要求一个演员站在另一个演员的肩膀上叠起来，且上面的人要比下面的人轻，下面的人要比上面的人高。同时给定演员总数n，要求返回最多能叠的人数。保证总人数小于等于500。
测试样例：
[[1,2],[3,4],[5,6],[7,8]],4
返回：4
[编程题]叠罗汉II
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;
}
}
发表于 2015-09-04 22:36:16
回复(0)
/*
哈哈，吃了一个饭回来就想到办法了。参考前面一题的方法（求解最长递增子序列），这里的二维数组可以简化为一维的问题。因为身高是递增顺序的情况下，求出的最大体重递增子序列其身高一定也是递增的序列。
*/
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];
}
};
发表于 2015-09-06 18:51:16
回复(2)
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;
}
};
发表于 2019-03-11 01:57:18
回复(0)
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;
}
}
编辑于 2020-06-16 19:16:56
回复(0)
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加入数组尾部，
最后数组的长度就是升序数列的长度
编辑于 2020-04-19 15:08:07
回复(0)
""" 求数组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)
编辑于 2019-07-21 13:27:22
回复(0)
先排序，然后添加判断条件，与上题类似
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;
}
};
发表于 2017-06-29 19:13:06
回复(1)
左神的课讲过，讲的真好
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;
}
};
发表于 2016-08-31 13:01:40
回复(0)
//看了《程序员面试金典》书上的提升，先将身高排序，然后对体重查找最长递增子系列；
//看了大家的代码，各种方法都有，有的人用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];
}
};
编辑于 2016-08-18 16:18:26
回复(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)
发表于 2016-08-08 20:20:02
回复(0)
Solution: DP，先把二维数组按acctors[i][0]排序，然后再对actors[i][1]查找最长递增子序列：
public int getHeight(int[][] actors, int n) {
if(actors==null || n==0) return 0;
Comparator<int[]> cmp = new
Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0]-b[0];
}
};
Arrays.sort(actors, cmp);
int max=0;
int[] f=new int[n];
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++){
//if(actors[j][0]<actors[i][0] &&
actors[j][1]<actors[i][1]){
if(actors[j][1]<actors[i][1]){
f[i]=Math.max(f[i],f[j]+1);
}
}
max=Math.max(max,f[i]);
}
return max;
}
发表于 2016-01-03 00:02:42
回复(0)
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);
}
发表于 2015-10-12 19:47:43
回复(0)
//总感觉用身高排序，找体重的最大子序列
//或者用体重找身高，总感觉缺了点什么，就写了两个。
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];
}
};
发表于 2015-10-07 12:12:49
回复(0)
首先按照身高进行排序，得到排完序的结果再按照体重得到最长递增子序列，这个最长的子序列就是最终的结果
class Stack:
def getHeight(self, actors, n):
#按照身高对其进行排序
actors.sort()
dp = [1 for i in range(n)]
max_count = 0
for i in range(1,n):
for j in range(0,i):
if actors[i][1] >= actors[j][1]:
dp[i] = dp[i] if dp[i] >= dp[j] + 1 else dp[j] + 1
if dp[i] > max_count:
max_count = dp[i]
return max_count
class Stack:
def getHeight(self, actors, n):
#按照身高对其进行排序
actors.sort()
dp = [1 for i in range(n)]
max_count = 0
for i in range(1,n):
for j in range(0,i):
if actors[i][1] >= actors[j][1]:
dp[i] = dp[i] if dp[i] >= dp[j] + 1 else dp[j] + 1
if dp[i] > max_count:
max_count = dp[i]
return max_count
发表于 2022-06-21 14:39:12
回复(0)
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;
}
}
发表于 2022-01-18 14:20:12
回复(0)
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)))
发表于 2020-08-10 21:11:37
回复(0)
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};
};
发表于 2020-07-23 15:05:10
回复(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;
}
};
发表于 2020-04-29 17:44:25
回复(0)
问题信息
难度：
52条回答
44收藏
16611浏览
通过挑战的用户
查看代码-
2023-02-15 21:58:32
-
2023-02-13 14:55:05 -
2022-11-08 19:29:53
-
2022-08-20 21:13:07
-
2022-08-04 09:11:02
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
