首页 > 试题广场 >

叠罗汉II

[编程题]叠罗汉II

热度指数：5072 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个二维int的数组actors，每个元素对应两个值，分别代表一个演员的身高和体重。要求一个演员站在另一个演员的肩膀上叠起来，且上面的人要比下面的人轻，下面的人要比上面的人高。同时给定演员总数n，要求返回最多能叠的人数。保证总人数小于等于500。

测试样例：

[[1,2],[3,4],[5,6],[7,8]],4

返回：4

算法知识视频讲解

牛客924233号

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)

LemonTree

简直了！！错了也把测试案例写完整啊，这让我怎么弄TAT

发表于 2015-08-27 17:58:02 回复(2)

zyweng

/*
哈哈，吃了一个饭回来就想到办法了。参考前面一题的方法（求解最长递增子序列），这里的二维数组可以简化为一维的问题。因为身高是递增顺序的情况下，求出的最大体重递增子序列其身高一定也是递增的序列。
*/
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)

C/C++

nbgao

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)

Java

lmz9509

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)

南少201911241210480

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)

Python

雷凌云

"""
求数组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)

Cavs

先排序，然后添加判断条件，与上题类似
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)

Aurora1

class Stack:
    def getHeight(self, actors, n):
        k = [0] * n #记录以i结尾的最长子序列
        A = sorted(actors) #先对身高排序，排体重也行
        for i in range(n):
            t = 0
            for j in range(i - 1, -1, -1):
                if A[i][1] > A[j][1] and k[j] > t: #找最长子序列
                    t = k[j]
            k[i] = t + 1
        return max(k)

发表于 2017-03-04 09:25:11 回复(0)

周星星_

左神的课讲过，讲的真好

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)

Python

Yannyezixin

跟前面一题其实思路差不多

在身高排序递增之后，再求得体重递增子序列，其对应的身高子序列也肯定是递增的

总共四种思路，可以参考我前面一题的回答

# -*- 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)

hwm18

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)

L0L

 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

发表于 2022-06-21 14:39:12 回复(0)

Java

wanbf

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)

TankWitch

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)

C/C++

字节内推小跟班

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)