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

资讯详情

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

freeCodeCamp 每日编程挑战实战:用 Python 实现嵌套括号字符串解码(Reverse Parenthesis)

freeCodeCamp 每日编程挑战实战:用 Python 实现嵌套括号字符串解码(Reverse Parenthesis) freeCodeCamp 每日编程挑战实战用 Python 实现嵌套括号字符串解码Reverse Parenthesis【免费下载链接】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 Challenge」系列的第 16 题 Reverse Parenthesis 展开以 Python 版本原题文档为核心完整讲解题目规则、官方测试用例、参考解法逐行剖析、栈式备选实现并结合仓库源码揭示这道题从 Markdown 挑战文件到线上题目的完整数据链路。读完本文你将掌握嵌套括号解码问题的本质——从内向外反转——并能独立实现 O(n) 的栈解法同时理解 freeCodeCamp 每日挑战系统的构建与运行机制。题目来源与定位本挑战的原始文档位于 curriculum/challenges/english/blocks/daily-coding-challenges-python/6821ebda237de8297eaee792.md文件头部的 frontmatter 定义如下--- id: 6821ebda237de8297eaee792 title: Challenge 16: Reverse Parenthesis challengeType: 29 dashedName: challenge-16 ---其中challengeType: 29是理解这道题定位的关键。在 packages/shared/src/config/challenge-types.ts 中定义const dailyChallengeJs 28; const dailyChallengePy 29;即29对应dailyChallengePyPython 每日挑战而仓库中还存在一份完全同题、同 id 的 JavaScript 孪生版本 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/6821ebda237de8297eaee792.mdchallengeType: 28两份文档在题目描述与三个测试用例上一一对应仅在测试运行方式Python 走runPythonunittestJS 走assert.equal与种子代码上有所区别。从 curriculum/structure/blocks/daily-coding-challenges-python.json 可以看到本挑战隶属于daily-coding-challenges-python模块block其元信息为{ isUpcomingChange: true, dashedName: daily-coding-challenges-python, usesMultifileEditor: true, helpCategory: Python, blockLayout: legacy-challenge-list }该 block 中共有 365 道每日挑战Challenge 1 到 Challenge 365本题目为第 16 道位于 Vowel Balance、Base Check、Fibonacci Sequence 等题目之后属于字符串处理类题目的进阶关卡。解码规则详解原题--description--部分给出了如下规则Given a string that contains properly nested parentheses, return the decoded version of the string using the following rules:括号内字符全部反转每一对括号(...)内部的所有字符顺序颠倒。最终结果移除括号解码完成后所有(与)都不保留在结果中。嵌套时由内向外处理如果括号存在嵌套最内层的一对先反转反转得到的结果再参与外层括号的反转。输入保证合法可以假定所有括号都完全配对、正确嵌套properly nested无需处理非法输入。用一句话概括把字符串想象成洋葱从最内层开始一层层把括号剥掉每剥一层就把该层内容整体倒序。官方测试用例全解析原文档--hints--提供了三个必过的测试用例这是评判实现正确性的唯一标准。用例 1基础嵌套decode((f(b(dc)e)a)) abcdef逐步推演这是理解算法的最佳样例步骤处理字符串变化原始—(f(b(dc)e)a)第 1 轮最内层(dc)反转成cd(f(bcde)a)第 2 轮内层(bcde)反转成edcb(fedcba)第 3 轮最外层(fedcba)反转成abcdefabcdef注意每一轮反转后外层括号的内容是上一轮反转结果 相邻普通字符的组合这正是嵌套反转的语义所在。用例 2多组并列括号 空括号组decode(((is?)(a(t d)h)e(n y( uo)r)aC)) Can you read this?该用例包含三组并排的括号((is?)(a(t d)h)e(n y( uo)r)aC)且括号内可以出现空格、标点如?说明算法必须对任意可打印字符一视同仁反转粒度是字符而不是单词。用例 3与项目名呼应的综合用例decode(f(Ce(re))o((e(aC)m)d)p) freeCodeCamp这个用例直观展示了解码的实战趣味输入f(Ce(re))o((e(aC)m)d)p经过层层反转与去括号后恰好还原出 freeCodeCamp 的英文名。推演关键几步f(Ce(re))o((e(aC)m)d)p → 内层 (re) 反转成 er → f(Ceer)o((e(aC)m)d)p → (Ceer) 反转成 reeC → freeCo((e(aC)m)d)p → 内层 (aC) 反转成 Ca → freeCo((eCam)d)p → (eCam) 反转成 maCe → freeCo(maCed)p → (maCed) 反转成 deCam → freeCodeCamp测试的运行时形态Python 版本的 hint 使用 freeCodeCamp 的浏览器内 Python 运行机制通过runPython注入unittest断言({test: () { runPython( from unittest import TestCase TestCase().assertEqual(decode((f(b(dc)e)a)), abcdef)) }})而 JS 孪生版本则直接使用assert.equal。也就是说你的decode(s)函数会被这三个用例反复调用全部通过即视为完成挑战。种子代码与解题起点原文档--seed--给出的初始代码极简只有一个空壳函数def decode(s): return s你的任务就是填补函数体让decode(s)依据上述规则返回解码后的字符串。三个测试用例会作为隐式验收标准任何不符合规则的实现都无法通过验证。参考解法逐行剖析原文档--solutions--给出的官方参考实现非常精炼只有 6 行def decode(s): while ) in s: close_index s.index()) open_index s.rindex((, 0, close_index) inner s[open_index 1:close_index][::-1] s s[:open_index] inner s[close_index 1:] return s逐行拆解其工作原理while ) in s:—— 只要字符串中还存在右括号就说明还有未处理的括号对循环继续。每轮循环恰好消除一对括号。close_index s.index())—— 找到字符串中最靠左的右括号。由于输入保证正确嵌套字符串中第一个出现的)必然对应最内层或最靠左一个尚未处理的括号对。open_index s.rindex((, 0, close_index)—— 从该右括号位置向前0到close_index之间从右往左找最后一个左括号。这个最靠近右括号的左括号与该右括号构成当前最内层的一对括号。inner s[open_index 1:close_index][::-1]—— 取出这对括号内部的子串不含括号本身用[::-1]切片语法整体反转。s s[:open_index] inner s[close_index 1:]—— 用反转后的内容替换左括号 内容 右括号这一整段即完成了反转内容 移除括号两个动作同时保持了外层字符的顺序。循环结束后所有括号对都被处理return s返回最终解码结果。以用例 1 为例三轮循环的close_index/open_index取值分别为(7, 4)、(7, 2)、(7, 0)每次替换都让字符串缩短 2 个字符两个括号直至只剩纯字符序列abcdef。这套先找最左)、再向左找最近(的技巧本质上是把由内向外的嵌套处理转化为反复消除最内层括号对的迭代过程思路清晰、代码量极小是面试与刷题场景中值得记忆的经典写法。备选实现O(n) 栈解法官方参考解法每轮循环都要执行index、rindex和多次字符串拼接设括号对数为 k字符串长度为 n最坏情况下的时间复杂度为 O(k·n)接近 O(n²)。对于更追求性能或希望一次遍历完成的场景可以用栈在 O(n) 时间内解决问题def decode(s): stack [] for ch in s: if ch ): # 弹出直到遇到匹配的左括号 segment [] while stack and stack[-1] ! (: segment.append(stack.pop()) # 丢弃左括号 if stack: stack.pop() # 因为出栈顺序天然反转直接压回即可 stack.extend(segment) else: stack.append(ch) return .join(stack)原理说明从左到右扫描时所有普通字符和(都直接入栈一旦遇到)就不断出栈收集字符直到栈顶是与之配对的(。由于出栈顺序与入栈顺序相反收集到的segment天然就是括号内内容的反转结果因此只需丢弃(、再把segment原样压回栈就同时完成了反转 去括号。全部扫描完毕后栈中剩余字符按序拼接即为答案。这种做法的正确性同样来自正确嵌套这一前提遇到)时栈顶到最近(之间恰好是该括号对的全部内容。两个方案对比维度官方参考解法栈解法时间复杂度O(k·n)近似 O(n²)O(n)单次遍历额外空间O(1)原地替换O(n)栈代码可读性极简6 行略长逻辑直观适用场景代码量优先长字符串、性能敏感边界情况与解题要点无括号输入如decode(hello)官方解法中while ) in s不成立直接返回原串栈解法则所有字符入栈后原样拼接。并列括号组(ab)(cd)应得到b a d c即badc。两组括号互不干扰各自独立反转。空括号组(())内部是空串反转后仍为空结果为同时注意s.rindex((, 0, close_index)在空括号场景下open_index 1 close_index切片为空串逻辑依然正确。特殊字符空格、标点、数字都按普通字符参与反转测试用例 2 已经覆盖了空格与问号。不要改变非括号字符的相对位置括号外的字符只应被搬运到最终结果中其在字符串中的顺序由外层反转决定但任何单轮替换都不应打乱当前括号对之外内容的顺序——这是官方解法s[:open_index] inner s[close_index 1:]三段式拼接的设计精髓。挑战背后的完整数据链路这道 Challenge 16 并不是孤立存在的 Markdown 文件它在 freeCodeCamp 仓库中串联起课程编写 → 双语言配对 → 数据库播种 → API 下发 → 前端渲染的完整流水线理解这条链路有助于你把握每日挑战系统的全貌。双语言配对与一致性校验curriculum/src/test/daily-challenges.test.js 中的测试会从dev-playgroundsuperblock 下分别加载daily-coding-challenges-javascript与daily-coding-challenges-python两个 block 的全部挑战并断言两个 block 的挑战数量必须一致均为 365每个位置的挑战id、title、description必须完全匹配两侧的tests数量必须一致。也就是说像 Challenge 16 这样JS/Python 同题是系统级硬约束而不是偶然巧合。播种到数据库tools/daily-challenges/seed-daily-challenges.ts 是每日挑战的播种脚本其工作方式为要求本地客户端以显示 upcoming changes模式运行通过 GraphQLhttp://localhost:8000/___graphql从dev-playgroundsuperblock 拉取两个 block 的全部挑战调用 tools/daily-challenges/helpers.ts 中的combineChallenges将同一挑战的 JS 版本与 Python 版本合并为一条记录id沿用 JS 挑战 idtitle去掉 Challenge N: 前缀description去除解析器添加的section标签JS 与 Python 各自的tests与challengeFiles分别存入javascript/python字段写入 MongoDB 的DailyCodingChallenges集合从2025-08-11UTC开始每天一个挑战365 个挑战依次排布到约 2026-08-10。脚本中还内置了防呆检查挑战总数必须等于EXPECTED_CHALLENGE_COUNT 365起始日期被写死为2025-08-11T00:00:00.000Z一旦被改动会直接抛错防止线上已发布的数据被意外变更。API 下发api/src/daily-coding-challenge/routes/daily-coding-challenge.ts 定义了每日挑战的 6 个公开只读端点提交仍走主挑战完成路由路由说明GET /daily-coding-challenge/today返回美国中部时间当天的挑战GET /daily-coding-challenge/date/:date按YYYY-MM-DD返回指定日期挑战晚于最后挑战日2026-08-10返回 404GET /daily-coding-challenge/day/:day按MM-DD返回2 月 29 日会被映射处理跨年轮转GET /daily-coding-challenge/month/:month按YYYY-MM返回当月挑战列表id、编号、日期、标题GET /daily-coding-challenge/all返回全部已发布挑战的摘要列表GET /daily-coding-challenge/newest返回最新挑战的日期所有路由都会校验日期格式非法格式返回 400并配合 Sentry 记录dcc.challenge_viewed、dcc.challenge_not_found等埋点指标。前端渲染前端侧client/src/client-only-routes/show-daily-coding-challenge.tsx 负责把 API 返回的数据组装成ShowClassic组件所需的 propsPython 版本的challengeType被显式设为29文件为main.pyJS 版本设为28文件为script.js。这与 packages/shared/src/config/challenge-types.ts 中viewTypes[29] classic、submitTypes[29] tests的定义一一对应。入口小组件 client/src/components/daily-coding-challenge/widget.tsx 则提供今日挑战与挑战档案archive两个入口日期处理工具函数集中在 client/src/components/daily-coding-challenge/helpers.ts基于America/Chicago时区计算今天。本地验证与测试如果你想在本地验证 Challenge 16 的实现可以遵循以下路径独立验证算法直接在本机 Python 环境运行参考解法或栈解法用三个官方用例断言assert decode((f(b(dc)e)a)) abcdef assert decode(((is?)(a(t d)h)e(n y( uo)r)aC)) Can you read this? assert decode(f(Ce(re))o((e(aC)m)d)p) freeCodeCamp运行课程级测试仓库的每日挑战测试位于 curriculum/src/test/daily-challenges.test.js它校验的是两个语言 block 的配对一致性数量、id、标题、描述、测试数需要在SHOW_UPCOMING_CHANGEStrue的环境变量下运行。体验完整链路可选按 tools/daily-challenges/README.md 的说明启动客户端与 API 服务运行播种脚本把 365 道挑战写入本地 MongoDB即可通过/daily-coding-challenge/today等端点拿到 Challenge 16 的真实在线数据。小结Reverse Parenthesis 是一道典型的嵌套结构 字符串变换题核心考点在于识别最内层括号对并反复消除。官方参考解法用index()) rindex((, ...)在 6 行内完成全部逻辑而栈解法则提供了 O(n) 的更优路径。在 freeCodeCamp 仓库中这道题同时以 PythonchallengeType 29与 JavaScriptchallengeType 28双版本存在经过配对校验、数据库播种、API 下发与前端渲染最终成为每日编程挑战第 16 天的实战题目——掌握它既是一次扎实的字符串算法训练也是理解 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),仅供参考
返回列表