搜狐2016研发工程师编程题及答案.pdf

【知识点解析】 本题是关于算法和数据结构的一道编程题目，主要考察的是有序数组的操作以及堆栈的应用。题目描述了一个实际问题：马戏团成员叠罗汉，要求站在某人肩上的人必须比自己矮且轻，或者两者相等。目的是找到可以叠出的最高罗汉塔的高度。以下是对题目涉及知识点的详细说明： 1. **数据结构**： - **Dis类**：定义了一个数据结构，包含了成员的编号（Num）、身高（high）、体重（weight）以及最大高度（max_high）。这个结构用于存储每个马戏团成员的信息。 - **数组**：题目中使用数组（map[]）来存储所有马戏团成员的数据。 2. **排序算法**： - **冒泡排序**：代码中使用了冒泡排序算法，对马戏团成员按体重从小到大进行排序。冒泡排序是一种简单的排序算法，通过不断交换相邻元素的位置，使得每一轮遍历后最大的元素浮到数组末尾。这里还考虑了体重相同的情况，此时根据身高进行排序，身高矮的成员排在后面。 3. **栈（Stack）**： - **模拟罗汉塔**：虽然题目中没有明确提到使用栈，但解决此问题通常会用到栈的数据结构。栈是一种后进先出（LIFO）的数据结构，适用于处理这种需要回溯的问题。可以创建一个栈来保存当前可以继续添加成员的节点，每次尝试将当前最小的成员（即体重最轻或体重相同但身高更矮的成员）放到塔顶，直到找不到符合条件的成员为止。这样可以确保每次添加的成员都是最优的。 4. **动态规划**： - **计算最大高度**：为了找到最高罗汉塔的高度，可以使用动态规划的思想，从底部向上构建罗汉塔。对于每个成员，我们需要知道他能作为底座支撑的最大高度。这可以通过遍历数组，检查每个成员是否可以站在其他成员的肩膀上，然后更新其max_high值。 5. **遍历与循环**： - **双重循环**：题目中使用了一个外层循环读取成员数量，一个内层循环进行冒泡排序。在计算最大高度时，可能需要再次遍历数组，检查每个成员与其他成员的组合。 6. **输入与输出**： - **Scanner类**：Java中的Scanner类用于读取用户输入，例如从控制台获取成员的数量和他们的信息。 解答该题目，需要实现的主要步骤包括： 1. 读取马戏团成员的数量和他们的身高、体重信息。 2. 使用冒泡排序对成员按体重和身高进行排序。 3. 初始化一个空栈，表示罗汉塔的底部。 4. 遍历排序后的成员，将符合条件的成员（即体重小于或等于栈顶成员且身高小于或等于栈顶成员的成员）压入栈中，同时更新栈顶成员的最大高度。 5. 当无法再添加成员时，栈顶成员的高度即为当前罗汉塔的最大高度。 6. 在所有成员都遍历完后，找到的最大高度就是整个罗汉塔的最大高度。 注意，以上解题思路仅提供了大致方向，具体实现还需要编写完整的代码并进行测试，确保所有情况都能正确处理。