尧图网站设计 尧图网站设计YAOTU DESIGN
ARTICLE DETAIL

资讯详情

深耕网站设计与一线实操的经验洞察。

freeCodeCamp 每日编程挑战 279:使用回溯法求解最长多米诺骨牌链(Longest Domino Chain)

freeCodeCamp 每日编程挑战 279:使用回溯法求解最长多米诺骨牌链(Longest Domino Chain) freeCodeCamp 每日编程挑战 279使用回溯法求解最长多米诺骨牌链Longest Domino 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 Challenges」模块的第 279 号挑战展开给定一组由 0–6 数字对构成的多米诺骨牌要求找出其中最长的合法链条并允许任意翻转骨牌。读完本文你将掌握该挑战的完整规则、官方示例解法中的递归回溯实现细节、测试断言设计思路以及它在前端练习与后端每日挑战接口中的落地方式可以直接在本地练习并验证你的实现。挑战背景Daily Coding Challenges 在 freeCodeCamp 中的位置「每日编程挑战」是 freeCodeCamp 课程体系中一个独立的 JavaScript 挑战块block在仓库中由curriculum/structure/blocks/daily-coding-challenges-javascript.json定义。该块以isUpcomingChange: true标记为进行中的新内容包含从Challenge 1: Vowel Balance到Challenge 365: The Last Challenge: Bucket Fill 3共 365 道挑战每道挑战对应一年中的一天。Challenge 279 位于列表第 1122–1124 行紧随其后的 280 是「Mongo ID Date」前一道 278 是「Coffee Order Parser」。这些挑战遵循统一的 Markdown 文件结构每个文件包含 frontmatterid、title、challengeType、dashedName、--description--题目描述、--hints--测试断言、--seed--起始代码和--solutions--参考答案。Challenge 279 的challengeType: 28属于编码挑战类型前端由client/src/components/daily-coding-challenge/下的widget.tsx、calendar.tsx等组件渲染后端则由api/src/daily-coding-challenge/模块按日期提供每日题目数据。题目规则详解curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69f35a5bb823ed620fcb7cb8.md给出了getLongestChain(dominoes)函数的要求输入一个二维数组代表一组多米诺骨牌返回最长的合法链。具体规则如下骨牌表示每张骨牌是一对 0–6 之间的数字例如[3, 2]链的合法性后一张骨牌的第一个数字必须与前一张骨牌的第二个数字相等即chain[i][1] chain[i1][0]两端自由第一张骨牌的第一个数字、最后一张骨牌的第二个数字不需要与任何东西匹配允许翻转任何骨牌都可以翻转[3, 2]既可以按[3, 2]打也可以按[2, 3]打解的唯一性题目保证恰好存在一条最长合法链长度上唯一但翻转/顺序可能不唯一见下文测试设计。示例给定[[1, 2], [4, 5], [2, 3]]最长链为[[1, 2], [2, 3]]因为[4, 5]两端分别与1、2、3都不衔接。测试断言设计为何答案允许两种表示该挑战的--hints--部分共有 5 组测试全部通过 Chai 的assert.isTrue断言链的 JSON 序列化结果等于result1或result2中的任意一个。这种「二选一」的设计源于骨牌翻转带来的等价性整条链从头到尾全部翻转后依然是一条合法的等长链。以第二组测试为例输入[[2, 1], [4, 3], [5, 3]]要求返回[[4, 3], [3, 5]]或[[5, 3], [3, 4]]——后者正是前者整体翻转的结果。测试代码片段如下const chain JSON.stringify(getLongestChain([[2, 1], [4, 3], [5, 3]])); const result1 JSON.stringify([[4, 3], [3, 5]]); const result2 JSON.stringify([[5, 3], [3, 4]]); assert.isTrue(chain result1 || chain result2);5 组测试的输入规模由简到繁覆盖了不同复杂度输入期望输出之一特点[[1,2],[4,5],[2,3]][[1,2],[2,3]]存在完全无法接入的孤立骨牌[[2,1],[4,3],[5,3]][[4,3],[3,5]]需翻转[5,3]为[3,5]才能衔接[[1,2],[3,4],[2,3],[4,0]][[1,2],[2,3],[3,4],[4,0]]全部骨牌可串成一条完整链[[6,6],[6,1],[1,1],[0,3],[2,3],[4,1],[5,6]][[4,1],[1,1],[1,6],[6,6],[6,5]]存在双点骨牌双六、双一需筛选出最长的 5 张[[0,4],[3,3],[0,3],[5,6],[4,5],[4,2],[5,5],[1,2],[4,4]][[3,3],[3,0],[0,4],[4,4],[4,5],[5,5],[5,6]]9 张骨牌中拼出 7 张最长链注意第 4、5 组测试中输入里都混入了无法接入最长链的「干扰骨牌」如[0,3]、[2,3]、[1,2]等这要求算法必须遍历所有可能的组合才能保证结果是全局最优而不是简单的贪心拼接。此外第 4 组测试验证了双点骨牌[6,6]、[1,1]的正确处理——它们翻转前后完全相同a ! b的判断保证了不会产生重复分支。种子代码起点与目标挑战提供的起始代码--seed--非常精简只给出了函数骨架要求补全实现逻辑function getLongestChain(dominoes) { return dominoes; }--seed-contents--只保留函数签名和直接返回入参的占位行为挑战者需要自行实现搜索逻辑。这种「空壳函数 测试驱动」的模式贯穿整个 daily-coding-challenges 块评价体系依赖--hints--中独立的assert断言本挑战的断言使用assert.isTrue比较序列化字符串而非固定的输入输出对因此实现方案可以自由选择只要最终返回的链在语义上等价即可。官方解法逐行拆解递归回溯Backtracking--solutions--中给出了完整参考实现其核心是递归回溯尝试所有可能的起始骨牌从当前链的末端数字出发逐一尝试剩余的每一张骨牌包括翻转递归地扩展链条并始终保留长度最长的结果。内部递归函数searchfunction search(chain, remaining) { let best chain; const last chain[chain.length - 1][1]; for (let i 0; i remaining.length; i) { const [a, b] remaining[i]; const rest remaining.filter((_, j) j ! i); if (a last) { const result search([...chain, [a, b]], rest); if (result.length best.length) best result; } if (b last a ! b) { const result search([...chain, [b, a]], rest); if (result.length best.length) best result; } } return best; }关键设计点best初始化为当前chain当没有剩余骨牌可接时remaining为空或全部不匹配search直接返回当前链这构成了递归的终止条件同时best始终保留「不追加任何骨牌」作为兜底保证任何状态下都有合法返回。last取自链尾的第二数字chain[chain.length - 1][1]是需要被下一张骨牌匹配的接口值。剩余骨牌筛选remaining.filter((_, j) j ! i)构造出移除第i张后的新剩余集合配合[...chain, [a, b]]的不可变风格每次递归产生新数组天然避免了对原数组的原地修改和回溯时需要撤销状态的问题。方向判断a last时按原方向[a, b]接入b last a ! b时按翻转方向[b, a]接入。a ! b的条件是性能与正确性的关键优化——对于双点骨牌如[6,6]翻转后与原来完全相同若不排除会生成重复分支、浪费指数级搜索空间甚至导致某些场景下出现「自我重复扩展」的死循环式无效分支。不可变展开 长度比较result.length best.length确保每个分支返回的都是该分支下的局部最优逐层向上比较后search最终返回从当前chain出发能扩展出的最长链。外层主函数枚举所有起点let best []; for (let i 0; i dominoes.length; i) { const [a, b] dominoes[i]; const rest dominoes.filter((_, j) j ! i); const r1 search([[a, b]], rest); if (r1.length best.length) best r1; if (a ! b) { const r2 search([[b, a]], rest); if (r2.length best.length) best r2; } } return best;主函数对每一张骨牌分别以其原始方向和翻转方向作为链的起点进行搜索best初始化为空数组[]与所有递归结果比较后返回全局最长链。best.length的比较天然处理了「长度相同取谁」的问题——由于题目保证恰好存在一条长度唯一的最长链任何一条等长的合法链都会被测试接受。复杂度分析从实现结构看该算法的时间复杂度为指数级对n张骨牌每个递归层都在remaining上做线性filter最坏情况下的搜索空间接近O(n!)排列数级空间复杂度为O(n)递归深度与每层新数组。因此本解法适合n较小挑战用例最大为 9 张骨牌的输入规模属于「正确性优先于效率」的教学式实现——这正是理解回溯、子集枚举与状态不可变性的理想载体。与 Challenge 214「Domino Chain Validator」的关系验证 vs 求解同一课程块中Challenge 214curriculum/challenges/english/blocks/daily-coding-challenges-javascript/699c8e045ee7cb94ed2322d5.md是一道难度递进的姊妹题它只要求判断一个给定的骨牌序列是否构成合法链输入数组已经排好顺序不允许重排或翻转解法是一个O(n)的线性扫描function isValidDominoChain(dominoes) { for (let i 0; i dominoes.length - 1; i) { if (dominoes[i][1] ! dominoes[i1][0]) return false } return true; }两者的对比清晰地展示了「验证」与「求解」两类问题的本质差异Challenge 214 是确定性的顺序检查而 Challenge 279 需要在「任意排列 任意翻转」的解空间中搜索全局最优复杂度从线性跃升到指数级。两题共享challengeType: 28与相同的 Markdown 结构规范适合放在一起练习形成从基础到进阶的完整理解闭环。在课程生态中的实际落地前端渲染与交互这类挑战在前端由client/src/components/daily-coding-challenge/目录承载widget.tsx负责展示每日挑战卡片题目、测试、编辑器calendar.tsx与calendar-day.tsx提供按日期浏览挑战的日历视图。client/src/utils/daily-coding-challenge-validator.ts定义了挑战数据从数据库到前端的形状校验规则每条挑战包含id、challengeNumber、title、date、description以及javascript与python两个语言版本的数据块每个语言块由teststexttestString数组和challengeFilesfileKeycontents数组构成——其中testString就是本文开头那些assert断言脚本challengeFiles则是--seed--的起始代码。该校验器基于 Joi 实现并对challengeNumber要求为不小于 1 的整数。后端数据接口api/src/daily-coding-challenge/routes/daily-coding-challenge.ts提供了 6 个公开 GET 接口将挑战数据按日期提供给前端GET /daily-coding-challenge/date/:date——按YYYY-MM-DD精确查询单日挑战日期格式非法返回 400早于今天 US Central 时间之前不存在返回 404GET /daily-coding-challenge/day/:day——按MM-DD查询会换算到对应的年份GET /daily-coding-challenge/today——返回当日挑战GET /daily-coding-challenge/month/:month——按YYYY-MM返回整月挑战摘要仅id、challengeNumber、date、titleGET /daily-coding-challenge/all——返回全部已发布挑战摘要GET /daily-coding-challenge/newest——返回最新挑战的日期。数据通过 Prisma 从dailyCodingChallenges表中读取接口代码中注释明确指出挑战数据仅发布到 2026 年 8 月 10 日为止挑战提交仍走主 API 的挑战完成路由api/src/daily-coding-challenge/README.md亦说明「每日挑战提交仍位于主 API 部分」。所有请求都会通过fastify.Sentry记录dcc.challenge_viewed、dcc.challenge_not_found等指标便于观测每日挑战的访问量。本地练习与验证建议想要动手验证你的getLongestChain实现可以按以下步骤打开curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69f35a5bb823ed620fcb7cb8.md将--seed--的函数骨架复制到你的编辑器用--hints--中的 5 组测试逐一断言你的输出注意JSON.stringify后与result1/result2任一等价即通过与--solutions--的参考实现对照重点体会「双点骨牌去重」「剩余集合不可变筛选」「best兜底」三个设计点如果想验证自己的理解可先完成 Challenge 214 的线性验证版本再升级到本挑战的搜索版本感受问题复杂度随约束放宽而爆炸式增长的过程。小结Challenge 279 是一个教科书式的递归回溯题规则简单数字匹配 允许翻转但解空间巨大排列 × 2 的翻转组合迫使你跳出贪心思维、建立完整的搜索树心智模型。官方解法以不可变数组 递归 长度比较三个元素在 20 行代码内优雅地解决了问题是学习回溯算法、剪枝思想与「验证 vs 求解」问题区分度的优质素材。配合本仓库中该挑战的前端渲染组件与后端数据接口你可以完整体验一道 freeCodeCamp 每日编程挑战从题目、测试、求解到上线的全链路。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表