首页 > 试题广场 >

叠罗汉II

[编程题]叠罗汉II

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

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

测试样例：

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

返回：4

算法知识视频讲解

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)

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)

Java

天山剑客

import java.util.*;

public class Stack {
    public int getHeight(int[][] actors, int n) {
        // write code here
    	if (n < 1) {
    		return 0;
    	}
    	
    	if (n == 1) {
    		return 1;
    	}
    	
    	Arrays.sort(actors, new Comparator<int[]>() {
    		public int compare(int[] a, int[]b) {
    			if(a[0] == b[0]) {
    				return a[1] - b[1];
    			}
    			
    			return a[0] - b[0];
    		}
    	});
    	
    	int[] dp = new int[n];
    	int max = 1;
    	for(int i = 0; i < n; i++) {
    		dp[i] = 1;
    	}
    	
    	for (int i = 1; i < n; i++) {
    		for(int j = 0; j < i; j++) {
    			if(actors[i][1] > actors[j][1] && dp[i] < dp[j] + 1) {
    				dp[i] = dp[j] + 1;
    				if (dp[i] > max) {
    					max = dp[i];
    				}
    			}
    		}
    	}
    	
    	return max;
    }
}

发表于 2019-12-14 11:31:15 回复(0)

Java

妞客0111347号

public class Stack {
    class Actor {
        int height;
        int weight;

        Actor(int height, int weight) {
            this.height = height;
            this.weight = weight;
        }
    }

    public int getHeight(int[][] actors, int n) {
        ArrayList<Actor> actors1 = new ArrayList<Actor>();
        ArrayList<Actor> actors2 = new ArrayList<Actor>();
        for (int i = 0; i < n; i++) {
            actors1.add(new Actor(actors[i][0], actors[i][1]));
            actors2.add(new Actor(actors[i][0], actors[i][1]));
        }

        // 先按照身高从高到低排序，再按照体重从大到小排序
        Collections.sort(actors1, new Comparator<Actor>() {
            public int compare(Actor o1, Actor o2) {
                if (o1.height > o2.height) {
                    return -1;
                } else if (o1.height < o2.height) {
                    return 1;
                } else if (o1.weight < o2.weight) {
                    return -1;
                } else if (o1.weight > o2.weight) {
                    return 1;
                }
                return 0;
            }
        });

        // 先按照体重从大到小排序，再按照身高从高到低排序
        Collections.sort(actors2, new Comparator<Actor>() {
            public int compare(Actor o1, Actor o2) {
                if (o1.weight > o2.weight) {
                    return -1;
                } else if (o1.weight < o2.weight) {
                    return 1;
                } else if (o1.height > o2.height) {
                    return -1;
                } else if (o1.height < o2.height) {
                    return 1;
                }
                return 0;
            }
        });

        int[] dp1 = new int[n];
        int[] dp2 = new int[n];

        int max1 = 0;
        for (int i = 0; i < n; i++) {
            dp1[i] = 1;
            max1 = 1;
            for (int j = 0; j < i; j++) {
                if (actors1.get(i).weight < actors1.get(j).weight && dp1[j] + 1 > max1) {
                    max1 = dp1[j] + 1;
                }
            }
            dp1[i] = max1;
        }

        int max2 = 0;
        for (int i = 0; i < n; i++) {
            dp2[i] = 1;
            max2 = 1;
            for (int j = 0; j < i; j++) {
                if (actors2.get(i).height < actors2.get(j).height && dp2[j] + 1 > max2) {
                    max2 = dp2[j] + 1;
                }
            }
            dp2[i] = max2;
        }

        max1 = max2 = 0;
        for (int i = 0; i < n; i++) {
            if (dp1[i] > max1) {
                max1 = dp1[i];
            }
            if (dp2[i] > max2) {
                max2 = dp2[i];
            }
        }

        return max1 > max2 ? max1 : max2;
    }
}

发表于 2017-03-16 10:49:32 回复(0)