企业官网建设流程全解析

freeCodeCamp 每日编程挑战 357「Food Chain」详解：从无序捕食者-猎物数组重建完整食物链

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

本文以 freeCodeCamp 每日编程挑战（Daily Coding Challenges）JavaScript 系列中的第 357 题「Food Chain」为主线，完整讲解这道题的题目要求、全部官方测试用例、参考解法的逐行原理与复杂度分析，并结合 freeCodeCamp 课程仓库源码说明该挑战在课程体系中的定位、题型编号（challengeType 28）以及每日挑战从题库到 API、再到编辑器测试运行的完整链路，帮助读者在解决本题的同时掌握这道图论入门题的标准解法。

题目要求

挑战原文（见 挑战定义文件）：

Given an array of[predator, prey]pairs, return the food chain from the apex predator down to the bottom.

• The apex predator is the animal that is never prey to another animal.
• Return the chain as an array of strings.

中文表述：给定一个由[捕食者, 猎物]二元组组成的数组，返回从顶级掠食者（apex predator）到食物链最底层的完整食物链：

• 顶级掠食者定义为：在整组数据中从未作为任何动物的猎物出现的那个动物；
• 结果是一个字符串数组，顺序从食物链顶端到最底层。

编辑器的初始代码（seed）如下，默认实现只是把入参原样返回，需要通过测试来改写：

function getFoodChain(pairs) { return pairs; }

官方测试用例（hints）

题目内置了 5 组assert.deepEqual测试，覆盖了从单对关系到乱序长链的全部典型场景：

// 单对关系：直接返回 assert.deepEqual(getFoodChain([["cat", "mouse"]]), ["cat", "mouse"]);

// 两对关系、按顺序给出 assert.deepEqual(getFoodChain([["wolf", "deer"], ["deer", "grass"]]), ["wolf", "deer", "grass"]);

// 三对关系、按顺序给出 assert.deepEqual(getFoodChain([["hawk", "snake"], ["snake", "frog"], ["frog", "fly"]]), ["hawk", "snake", "frog", "fly"]);

// 三对关系、乱序给出：rabbit 在前，apex 是最后出现的 eagle assert.deepEqual(getFoodChain([["rabbit", "grass"], ["fox", "rabbit"], ["eagle", "fox"]]), ["eagle", "fox", "rabbit", "grass"]);

// 五对关系、完全乱序：需要跨多个 pair 拼接出完整链 assert.deepEqual(getFoodChain([["seal", "salmon"], ["herring", "shrimp"], ["orca", "seal"], ["shrimp", "plankton"], ["salmon", "herring"]]), ["orca", "seal", "salmon", "herring", "shrimp", "plankton"]);

注意第 4、5 个用例：输入数组的顺序与食物链顺序无关。["rabbit", "grass"], ["fox", "rabbit"], ["eagle", "fox"]的排列并不对应链条方向，因此解法不能假设pairs[0]的捕食者就是 apex，也不能简单地按输入顺序拼接——必须自己从数据中找出链条起点。

解法建模：把 pair 数组当作有向边

把每个[predator, prey]看作一条有向边（predator → prey），整组数据在题目约定下恰好构成一条链：除 apex 外每个动物入度为 1（只被一个捕食者吃），除最底层猎物外每个动物出度为 1（只吃一种东西）。于是问题转化为：

1. 找到唯一的 apex：它是所有捕食者中不出现在猎物集合里的元素；
2. 从 apex 出发，沿「捕食者 → 猎物」的映射一路向下走到底。

官方参考解法（完整继承自挑战文件的# --solutions--段）：

function getFoodChain(pairs) { const prey = new Set(pairs.map(([, p]) => p)); const map = Object.fromEntries(pairs); const apex = pairs.map(([p]) => p).find(p => !prey.has(p)); const chain = [apex]; while (map[chain.at(-1)]) chain.push(map[chain.at(-1)]); return chain; }

逐行解析参考解法

第 1 行：const prey = new Set(pairs.map(([, p]) => p));

用数组解构([, p]) => p提取每对中的第二个元素（猎物），全部放入Set。后续判断「某动物是否是某物的猎物」只需一次Set.has()查找，避免了对原始数组的线性扫描。

第 2 行：const map = Object.fromEntries(pairs);

Object.fromEntries把[key, value]形式的二元组数组直接转成对象映射。由于每条 pair 恰好是[捕食者, 猎物]，转换后得到{ [捕食者]: 猎物 }的映射，例如[["wolf", "deer"], ["deer", "grass"]]变成{ wolf: "deer", deer: "grass" }。这是「当前动物的下一个猎物」的 O(1) 查表入口。

第 3 行：const apex = pairs.map(([p]) => p).find(p => !prey.has(p));

先取出所有捕食者（每对的第一个元素），再用find找到那个不在猎物Set里的动物——按题目定义，它必然是链条起点。用find而非filter隐含了一个题目保证：apex 唯一。

第 4～5 行：const chain = [apex]; while (map[chain.at(-1)]) chain.push(map[chain.at(-1)]);

从 apex 开始迭代：chain.at(-1)取当前链条末端，map[chain.at(-1)]查到它的猎物；只要该值存在（非undefined，truthy），就push进链条。当末端是「grass」「fly」「plankton」这类没有下游映射的底端动物时，map[...]为undefined，条件为假，循环自然终止。Array.prototype.at(-1)在这里比chain[chain.length - 1]更简洁，是 ES2022 标准方法。

以第 5 组乱序用例为例，执行过程为：prey = {salmon, shrimp, seal, plankton, herring}，apex = "orca"（唯一不在 prey 中的捕食者），随后orca → seal → salmon → herring → shrimp → plankton，map["plankton"]为undefined停止，得到["orca", "seal", "salmon", "herring", "shrimp", "plankton"]，与预期完全一致。

边界与复杂度

• 乱序输入：解法对 pair 顺序完全不敏感，因为起点靠「排除猎物集合」确定，方向靠映射表驱动，这正是第 4、5 组用例存在的意义。
• 单对输入：while循环体执行 1 次后即终止，无特殊分支。
• 时间复杂度：建立 prey Set 与 map 均为 O(n)，find扫描捕食者 O(n)，while每条边最多被访问一次 O(n)，整体O(n)；空间复杂度 O(n)（Set、map 与结果数组）。
• 一个从源码结构可以推断的细节：本块配置 daily-coding-challenges-javascript.json 中声明了"disableLoopProtectTests": true，即该挑战块禁用了循环保护测试，允许（也预期）答案使用while这类显式循环而不被超时拦截。

这道题在 freeCodeCamp 仓库中的位置

块与编号。挑战文件位于 daily-coding-challenges-javascript 块 下，其块配置 daily-coding-challenges-javascript.json 中，id6a26df3e2988bcdded204893排在 365 道题的倒数第 9 位，标题为Challenge 357: Food Chain。同一 id 也出现在 daily-coding-challenges-python.json 中——每日挑战是 JS/Python 双语言题库，同一题号下两种语言各有独立实现与测试。

题型编号。挑战文件 front matter 中challengeType: 28，对照 challenge-types.ts 可确认28即dailyChallengeJs，29为dailyChallengePy；该类型的viewTypes为classic（经典编辑器），submitTypes为tests——即提交时代码会直接跑本文前面列出的assert.deepEqual测试，全过则判定完成。仓库还提供了getIsDailyCodingChallenge与getDailyCodingChallengeLanguage等辅助函数，按 challengeType 区分是否为每日挑战及其语言。

数据链路。每日挑战的选题与下发经过专门链路：API 侧 daily-coding-challenge 路由 与 响应 schema 定义了单条挑战的结构——tests（每项含text展示文本与testString实际执行代码）和challengeFiles（fileKey+contents，即编辑器初始代码），客户端则用 daily-coding-challenge-validator.ts 中的 Joi schema 对取回的每日挑战数据做同样字段的校验。题库本身由 tools/daily-challenges 下的种子脚本写入数据库的DailyCodingChallenges集合（该 README 说明了从「Dev Playground」superblock 读取挑战并 seed 的流程）。也就是说，本文这道题的 seed 代码、hints 与 solutions 就存放在课程 Markdown 中，经构建与 seed 流程后成为线上编辑器里的初始文件、提示与判题测试。

小结与相关文件

• 题面与全部测试：6a26df3e2988bcdded204893.md
• JS 块配置（含disableLoopProtectTests、365 题列表）：daily-coding-challenges-javascript.json
• 题型枚举dailyChallengeJs = 28：challenge-types.ts
• 每日挑战 API 路由 / schema：routes、schemas
• 客户端每日挑战校验：daily-coding-challenge-validator.ts
• 题库 seed 工具：seed-daily-challenges.ts、README

本题的核心可迁移经验是把「乱序的成对关系」建模为映射表 + 集合，用「不在猎物集合中的元素」定位链头，再以 O(n) 的迭代沿边展开——这是处理任意「乱序链接/前驱后继关系」重建有序序列（链表拼接、事件排序等）的通用套路。

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp