freeCodeCamp 每日编程挑战 357「Food Chain」详解从无序捕食者-猎物数组重建完整食物链【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp本文以 freeCodeCamp 每日编程挑战Daily Coding ChallengesJavaScript 系列中的第 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只吃一种东西。于是问题转化为找到唯一的 apex它是所有捕食者中不出现在猎物集合里的元素从 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 唯一。第 45 行const chain [apex]; while (map[chain.at(-1)]) chain.push(map[chain.at(-1)]);从 apex 开始迭代chain.at(-1)取当前链条末端map[chain.at(-1)]查到它的猎物只要该值存在非undefinedtruthy就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 → planktonmap[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即dailyChallengeJs29为dailyChallengePy该类型的viewTypes为classic经典编辑器submitTypes为tests——即提交时代码会直接跑本文前面列出的assert.deepEqual测试全过则判定完成。仓库还提供了getIsDailyCodingChallenge与getDailyCodingChallengeLanguage等辅助函数按 challengeType 区分是否为每日挑战及其语言。数据链路。每日挑战的选题与下发经过专门链路API 侧 daily-coding-challenge 路由 与 响应 schema 定义了单条挑战的结构——tests每项含text展示文本与testString实际执行代码和challengeFilesfileKeycontents即编辑器初始代码客户端则用 daily-coding-challenge-validator.ts 中的 Joi schema 对取回的每日挑战数据做同样字段的校验。题库本身由 tools/daily-challenges 下的种子脚本写入数据库的DailyCodingChallenges集合该 README 说明了从「Dev Playground」superblock 读取挑战并 seed 的流程。也就是说本文这道题的 seed 代码、hints 与 solutions 就存放在课程 Markdown 中经构建与 seed 流程后成为线上编辑器里的初始文件、提示与判题测试。小结与相关文件题面与全部测试6a26df3e2988bcdded204893.mdJS 块配置含disableLoopProtectTests、365 题列表daily-coding-challenges-javascript.json题型枚举dailyChallengeJs 28challenge-types.ts每日挑战 API 路由 / schemaroutes、schemas客户端每日挑战校验daily-coding-challenge-validator.ts题库 seed 工具seed-daily-challenges.ts、README本题的核心可迁移经验是把「乱序的成对关系」建模为映射表 集合用「不在猎物集合中的元素」定位链头再以 O(n) 的迭代沿边展开——这是处理任意「乱序链接/前驱后继关系」重建有序序列链表拼接、事件排序等的通用套路。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考