首页 > 试题广场 >

叠罗汉II

[编程题]叠罗汉II
  • 热度指数:5058 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个二维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;
    }
}

发表于 2015-09-04 22:36:16 回复(0)
简直了!!错了也把测试案例写完整啊,这让我怎么弄TAT


发表于 2015-08-27 17:58:02 回复(2)
/*
哈哈,吃了一个饭回来就想到办法了。参考前面一题的方法(求解最长递增子序列),这里的二维数组可以简化为一维的问题。因为身高是递增顺序的情况下,求出的最大体重递增子序列其身高一定也是递增的序列。
*/
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)
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)
跟前面一题其实思路差不多
在身高排序递增之后, 再求得体重递增子序列,其对应的身高子序列也肯定是递增的
总共四种思路,可以参考我前面一题的回答
# -*- 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)
L0L头像 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)
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)