人的高耸算法
在《破解编码面试》第四版中，有这样一个问题：
一个马戏团正在设计一个由站在一个人肩膀上的人组成的塔例程，为了实用和美观的原因，每个人都必须比他或她下面的人更矮更轻给定马戏团中每个人的身高和体重，写出一个计算这样一个塔中可能的最大人数的方法。
示例：输入（ht,wt）：（65,100）（70,150）（56,90）（75,190）（60,95）（68,110）
输出：最长的塔长度为6，从上到下包括：（56,90）（60,95）（65,100）（68,110）（70,150）（75,190）
书中有它的解决方法
第一步：先按高度排序，再按重量排序。这意味着，如果所有的高度都是唯一的，那么将按高度排序；如果高度相同，将按重量排序
步骤2找出包含增加高度和增加重量的最长序列来完成此操作，我们：
a）从序列的开头开始当前，max_sequence为空
b）如果下一个项目的高度和重量不大于上一个项目的高度和重量，我们将该项目标记为“不适合”
我对它的解决方法有些疑问。
Q1
我相信这个解决办法是错误的。
<代码>（3,2）（5,9）（6,7）（7,8）
显然，(6,7)是一个不适合的项目，但是(7,8)怎么样？根据解法,它的h和w比(6,7)大得多,并不是不适合,但由于(7,8)不适合(5,9),所以不能将它纳入序列。
我说的对吗？
如果我是对的，那有什么办法呢？
Q2
我相信，即使上面的解决方案有一个修复，解决方案的样式至少会导致O(n^2)，因为它需要根据步骤2-D一次又一次地迭代。
那么有可能有一个O（nlogn）解吗？
共有1个答案
你可以用动态编程来解决这个问题。
按身高对剧团进行排序。为简单起见，假设所有高度h_i和权重w_j是不同的。因此h_i是一个递增序列。
我们计算了一个序列T_i，其中T_i是一个塔，人i在最大尺寸的顶部。T_1只是{1}。我们可以从前面的T_j推导出后续的T_k-找到一个最大的塔T_j，它能承受k的重量(w_j
这个算法需要O(n**2)个时间，其中n是剧团的基数。
-
问题内容： 在《破解编码面试》第四版中，存在这样的问题： 马戏团正在设计一个塔楼套路，由站在一个人的肩膀上的人组成。出于实际和美学的原因，每个人都必须比其下方的人矮一些和矮一些。考虑到马戏团中每个人的身高和体重，编写一种方法来计算此类塔楼中的最大人数。 示例：输入（ht，wt）：（65，100）（70，150）（56，90）（75，190）（60，95）（68，110） 输出：最长的塔长为6，从上
-
我可能还真面试不过
-
我正在用Apache POI 3.13编写一个Excel（xls）表。我手动设置列宽。如果单元格的内容太长，我希望对其进行包装，并调整列高度。 如果我将单元格样式的wrapText属性设置为true，则文本不再“流出”单元格，但如何将行的高度设置为合适的值？ 我见过的所有方法都计算字符串中的换行符。这对我不起作用，因为我的文本不包含手动换行符。
-
问题内容： 有没有一种方法可以计算出地面与手机之间的高度？我以为我可以用它来测量身高，但这篇文章建议您不要考虑误差率。如果是这样，我应该采取什么方法来测量手机的高度？ 问题答案： GPS的精度足以使您将海拔高度提高到几米之内，但这可能并不是您想要的。 我想您可以在确定手机的麦克风/扬声器正好用加速度计指向地面的情况下尝试使用某种声纳。您可以假设使用STP，这可能会导致大约20％的错误。 您还可以告
-
我试图确定一个有效的,使用有向图的最大流算法,给定n个航班的列表（其中每个条目都有起始城市,结束城市,出发时间,到达时间,和航班容量）,将尽可能多的人从城市A出发，到城市B结束。我还希望能够返回可以乘坐的航班集，以便尽可能多的人从城市A到达城市B。我认为它可以只是Ford-Fulkerson算法的一个实现，或者类似的东西，但是我遇到了麻烦，无法以有效的方式将这个时间表转换成最大流实例，特别是在这样
-
cocos2d 高仿捕鱼达人。 [Code4App.com]