首页 > 试题广场 >

叠罗汉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

算法知识视频讲解

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)

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)