【去哪儿最新秋招笔试试题】是一份针对互联网公司校招的笔试题目，涉及的知识点主要包括动态规划、图论和数据结构。以下是这些题目详细解析：
1. **日本旅行**：
这是一道动态规划问题，需要计算用特定面额的硬币组合成指定金额所需的最少硬币数量。动态规划的思路是从最小面额开始，逐步增加硬币的面额，每次尝试用当前面额的硬币最大化地减少总硬币数量。若无法组合出所需金额，则返回`NOWAY`。此题的约束条件是硬币面额为1元、5元、10元、50元、100元和500元，且每种硬币数量不超过1亿枚，目标金额不超过1亿。例如，当楚乔有3个1元，2个5元，1个10元，3个50元，0个100元和2个500元硬币，要购买价格为620元的饮料时，最少需要62枚硬币。
2. **带权的DAG节点排序**：
这道题考察的是图的拓扑排序和最大权重优先排序。DAG（有向无环图）中，每个节点都有一个权重表示其重要性。任务的排序应满足拓扑排序的要求，即无向边连接的节点B不能排在节点A之前，同时要尽可能让权重大的节点优先。解决这个问题可以采用拓扑排序结合最大堆的思想，先对节点按照权重降序排列，然后进行拓扑排序。例如，对于一个有4个节点的DAG，如果节点1的权重为2，节点3的权重为5，节点2的权重为3，节点4的权重为4，且存在边1->2, 2->3, 3->4，那么正确的排序结果为1 3 2 4。
3. **模拟LRU Cache**：
LRU（Least Recently Used，最近最少使用）缓存策略是常见的内存管理策略。题目要求在固定大小的缓存中，根据LRU原则进行数据的存储和删除。在Python等语言中，可以使用内置的`collections.OrderedDict`来实现，但题目明确禁止使用。实现LRU Cache的关键是维护一个有序的数据结构，如双向链表，来记录数据的访问顺序，并配合哈希表快速查找和删除元素。对于put和get操作，put操作需要插入数据并检查缓存是否已满，满则移除最近最少使用的数据；get操作则需要检查键是否存在，若存在则返回对应的值，否则返回null。例如，对于一个大小为3的缓存，初始操作序列`put a b, put x y, put d kkk, put zzz lll, get a`，输出应为`null`，因为a已被替换。
