牛客网算法进阶课程：详解常见算法与实战

"牛客网算法进阶课程第二课涵盖了两个主要的算法问题：设计可变缓存结构和计算二维数组表示的大楼轮廓线。课程由左程云老师讲授，他具有丰富的IT行业背景，曾在IBM、百度、GrowingIO、亚马逊等公司任职。课程在每周六日的14:00至16:00进行，通过牛客网平台进行，该平台提供校招真题、专项练习、学习资源和交流论坛。 首先，让我们深入探讨第一个算法问题——设计可变缓存结构。这是一个典型的LRU（Least Recently Used）缓存淘汰策略问题。LRU策略是常见的内存管理策略，当缓存满时，最近最少使用的数据会被优先淘汰。在这个问题中，我们需要实现一个数据结构，其功能包括`set(key, value)`和`get(key)`，并且保证这两个操作的时间复杂度为O(1)。这意味着我们需要一个高效的数据结构来存储键值对并跟踪它们的访问频率。一个常见的解决方案是使用哈希表和双向链表结合的方式。哈希表用于O(1)时间查找，而双向链表则用于保持元素的访问顺序。当执行`set`或`get`操作时，更新元素在链表中的位置，以反映最近使用的信息。当缓存满时，删除链表尾部的元素，因为它们是最不常使用的。 第二个算法问题是计算二维数组表示的大楼轮廓线。这个问题涉及到二维空间中的几何形状处理。给定的二维数组描述了N座大楼在X轴上的基础以及它们的高度。轮廓线是由所有大楼顶部构成的连续线段。解决这个问题的关键在于找到所有大楼顶部的连接点，这些点构成了最终的轮廓线。这可以通过遍历每一座大楼，找出其与其他大楼的交点来实现。对于每一对相邻的大楼，检查它们是否有重叠部分，如果有，根据它们的高度和位置添加交点到结果列表中。最后，将这些交点按顺序连接起来，就得到了整体的轮廓线。 在这个问题中，需要注意的是，由于大楼高度可能不同，轮廓线上的点可能会在同一X坐标上有多个不同的高度，因此需要特别处理这种情况。在给定的例子中，输入的二维数组为`[[1,3,3],[2,4,4],[5,6,1]]`，经过计算后，输出的轮廓线应为`[[1,2,3],[2,4,4],[5,6,1]]`，表示从X坐标1到2，高度为3；从X坐标2到4，高度为4；从X坐标5到6，高度为1。 这两个问题都是数据结构和算法的经典实例，涵盖了哈希表、链表、二维空间几何以及高效数据结构设计等核心概念。通过学习和解决这些问题，学员可以提升自己的算法设计和实现能力，为后续的算法挑战做好准备。