freeCodeCamp 每日编程挑战解析：Blood Bank 血库配型问题与贪心分配算法

freeCodeCamp 每日编程挑战解析：Blood Bank 血库配型问题与贪心分配算法

【免费下载链接】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）序列的第 320 道题「Blood Bank」，完整拆解题目规则、血型兼容模型、参考解法中的贪心策略与优先级设计，并结合仓库源码说明该类挑战在课程结构、数据库播种与 API 层中的实际落地方式。读完本文，你将掌握如何把"多对多资源分配"问题建模为带优先级的贪心匹配，并理解 freeCodeCamp 每日挑战从 Markdown 题库到线上题目的完整链路。

挑战全景：第 320 道每日编程挑战

「Blood Bank」是daily-coding-challenges-javascript课程块（block）中的第 320 道题，其原始文档位于 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/6a15cadf5f240d05a264955e.md。从该文档的 frontmatter 可以看到：

id: 6a15cadf5f240d05a264955e title: "Challenge 320: Blood Bank" challengeType: 28 dashedName: challenge-320

其中challengeType: 28在 packages/shared/src/config/challenge-types.ts 中被定义为dailyChallengeJs（第 30 行），相邻的29对应dailyChallengePy。这意味着每一道每日挑战都以 JavaScript、Python 双语言形态存在，而本文分析的 Markdown 文件正是 JavaScript 版本的题库源。

整个块共包含 365 道题（对应全年每天一题），由 curriculum/structure/blocks/daily-coding-challenges-javascript.json 中的challengeOrder数组按id引用；Blood Bank 的 id6a15cadf5f240d05a264955e就出现在该数组中。块的配置还声明了"usesMultifileEditor": true、"helpCategory": "JavaScript"与"disableLoopProtectTests": true，说明这类题在答题界面上使用多文件编辑器、归类为 JavaScript 帮助类别，并关闭了循环保护检测以允许更自由的循环写法。

问题描述与输入输出约定

题目的核心描述（来自文档# --description--段）如下：

给定一个表示血库库存的血型数组，和一个表示患者血型需求的数组，返回形如"X of Y patients served"的字符串。其中X是库存能够满足的最大患者人数，Y是患者总人数。

两个数组中的每个元素都只能是以下四种血型之一："AB"、"A"、"B"、"O"。

• bank：库存数组，每个重复元素代表一单位库存血；
• patients：患者数组，每个重复元素代表一位需要该血型的患者；
• 返回值："X of Y patients served"，例如"4 of 4 patients served"。

要求实现的函数签名为triageBlood(bank, patients)，题目给出的初始种子代码（# --seed-contents--）为：

function triageBlood(bank, patients) { return bank; }

即学习者需要把占位实现替换为真正的配型逻辑。

血型兼容性模型

题目的配型规则非常明确（文档原文）：

这里存在两个关键不对称：

1. "O"是最紧缺的资源：它既能被"O"患者使用，也能被"A"、"B"、"AB"三类患者使用，但"O"患者本身只能使用"O"血；
2. "AB"患者最不挑：任何血型都能满足他们，因此他们应当最后再被服务。

这种"资源被多种需求方争夺、而其中一类需求方别无选择"的结构，正是贪心分配问题的典型特征——越受限制的需求越要先满足。

算法设计：带优先级的贪心分配

核心思路

要最大化服务患者总数，直观的策略是：先服务血型最受限的患者，并且在同一类患者内部，优先消耗"特异性"更高的血液，把通用血型"O"留到后面。仓库中的参考解法（# --solutions--段）正是按如下优先级处理：

1. "O"患者 → 只从"O"库存中取血；
2. "A"患者 → 先取"A"，不足再取"O"；
3. "B"患者 → 先取"B"，不足再取"O"；
4. "AB"患者 → 依次取"AB"、"A"、"B"、"O"。

这样设计的原因是："O"血可以满足四种患者，如果过早把它消耗在"A"/"B"/"AB"患者身上，后续遇到只能输"O"的"O"患者时就会无血可用，导致整体服务人数下降。反过来，把最挑剔的"O"患者优先安排，把最不挑剔的"AB"患者安排到最后吃剩余库存，才能逼近最大服务人数。

参考实现逐行拆解

仓库文档# --solutions--中给出的完整参考实现如下：

function triageBlood(bank, patients) { const b = {}; const p = {}; for (const t of bank) b[t] = (b[t] || 0) + 1; for (const t of patients) p[t] = (p[t] || 0) + 1; const serve = (patient, donors) => { for (const donor of donors) { const n = Math.min(p[patient] || 0, b[donor] || 0); p[patient] = (p[patient] || 0) - n; b[donor] = (b[donor] || 0) - n; saved += n; } }; let saved = 0; serve("O", ["O"]); serve("A", ["A", "O"]); serve("B", ["B", "O"]); serve("AB", ["AB", "A", "B", "O"]); return `${saved} of ${patients.length} patients served`; }

可以拆成三个阶段理解：

第一步：统计数量。用两个普通对象b与p分别对库存和患者做计数（频次统计），(b[t] || 0) + 1这种写法在键不存在时按 0 处理，是典型的计数惯用法。由于血型只有 4 种，对象始终只有不超过 4 个键，等价于一个固定大小的映射。

第二步：定义服务闭包。内部函数serve(patient, donors)按传入的供体优先级列表依次尝试：

• n = Math.min(p[patient] || 0, b[donor] || 0)计算本轮最多能匹配的单位数（患者剩余需求与对应库存的较小者）；
• 同步扣减患者剩余需求p[patient]与库存b[donor]；
• 把n累加到外部变量saved上。

注意serve内部引用的是外层声明的let saved，这正是闭包捕获外部变量的典型用法；saved的声明位置（在serve定义之后、调用之前）也符合"先定义函数、后初始化计数"的代码组织方式。

第三步：按优先级调度。依次对"O"、"A"、"B"、"AB"四类患者执行serve，供体列表的顺序即"先用特异性强的、后用通用血"的贪心顺序。最终返回模板字符串${saved} of ${patients.length} patients served。

为什么贪心在这里是安全的

对这道题而言，血型只有 4 类、兼容关系是单向偏序（"O"最底层、"AB"最顶层），因此"按受限程度从高到低、供体按特异性从高到低"的贪心顺序即可得到最优解。这种先服务受限方、再服务灵活方的思想，可以推广到更一般的资源分配问题，例如"有限通用资源 + 多种专用替代品"的库存调度场景。

测试用例验证

题目在# --hints--段给出了 6 组测试断言，全部使用assert.equal校验返回值。逐一推演如下：

用例 1：库存与需求完全匹配

triageBlood(["O", "A", "B", "AB"], ["O", "A", "B", "AB"]) // => "4 of 4 patients served"

每种血型库存 1 单位、需求 1 人，一一对应，4 位患者全部服务，返回"4 of 4 patients served"。

用例 2：缺乏 O 血导致的缺口

triageBlood(["A", "A", "B", "B", "AB"], ["O", "A", "B", "B", "B"]) // => "3 of 5 patients served"

库存中没有"O"，因此"O"患者无法被服务；"A"患者消耗 1 单位"A"，两位"B"患者各消耗 1 单位"B"后，第 3 位"B"患者无血可输（"O"库存为 0）。最终只服务 3 人，验证了"O 患者必须优先、且无 O 血即无法服务"的规则。

用例 3：全 AB 患者吃干库存

triageBlood(["O", "A", "B", "AB"], ["AB", "AB", "AB", "AB", "AB"]) // => "4 of 5 patients served"

5 位"AB"患者面对 4 单位任意血型库存。由于"O"、"A"、"B"患者数为 0，前两步跳过，最后"AB"患者按AB → A → B → O顺序把 4 单位库存全部消耗，服务 4 人、1 人无血，验证了"AB 患者最灵活、最后服务"的设计。

用例 4：只有 O 血却能服务所有患者

triageBlood(["O", "O", "O", "O", "O"], ["O", "A", "B", "AB"]) // => "4 of 4 patients served"

5 单位"O"血依次服务 1 位"O"、1 位"A"、1 位"B"、1 位"AB"患者，4 人全部满足，返回"4 of 4 patients served"，直观展示了"O"作为通用供血者的价值。

用例 5：混合场景下的资源竞争

triageBlood(["A", "O", "B", "AB", "B", "AB", "O", "A", "A"], ["O", "A", "B", "AB", "A", "B", "A", "A", "B", "A", "B"]) // => "8 of 11 patients served"

库存统计为 A:3、O:2、B:2、AB:2；需求为 O:1、A:5、B:4、AB:1。按优先级：O 患者消耗 1 单位 O；A 患者先消耗 3 单位 A、再消耗 1 单位 O（共 4 人）；B 患者消耗 2 单位 B（共 2 人）；AB 患者消耗 1 单位 AB。合计 8 人，剩余 3 位患者（1 位 A、2 位 B）无血可输。

用例 6：长数组的完整调度

triageBlood(["O", "B", "AB", "AB", "O", "A", "A", "AB", "O", "B", "B", "AB", "A", "B", "AB"], ["O", "A", "B", "B", "A", "B", "AB", "A", "B", "A", "O", "AB", "AB", "O"]) // => "13 of 14 patients served"

库存为 O:3、A:3、B:4、AB:5；需求为 O:3、A:4、B:4、AB:3。O 患者消耗全部 3 单位 O；A 患者消耗 3 单位 A 后仍缺 1 人（O 已耗尽）；B 患者消耗 4 单位 B 全部满足；AB 患者消耗 3 单位 AB。合计 13 人，仅剩 1 位 A 患者无法服务。若在 A 患者之前就消耗 O 血，服务人数只会更少，这组用例验证了"O 血必须留给最需要的场景"的贪心正确性。

复杂度分析

• 时间复杂度：统计阶段各遍历一次bank与patients，为O(n + m)（n为库存长度、m为患者长度）；服务阶段对 4 类患者各迭代至多 4 种供体，为常数O(16)。总体为线性时间。
• 空间复杂度：两个计数对象最多各含 4 个键，为O(1)额外空间，与输入规模无关。

边界情况与扩展思考

• 空数组：bank或patients为空时，循环不执行，saved为 0，返回如"0 of 0 patients served"（空库存配空需求）或"0 of 3 patients served"（有需求无库存），行为由代码自然保证。
• 库存充足但血型错配：例如只有"A"血而患者全为"O"时，服务数为 0，符合"O 只能接受 O"的规则。
• 通用受血者的兜底价值："AB"患者几乎不会成为瓶颈（除非完全没有库存），这使它在调度中天然处于"吃剩余"位置。
• 算法推广：把血型换成"通用组件 + 专用组件"、把患者换成"需求规格"，同一套"受限优先 + 通用资源保底"的贪心框架即可复用到库存管理、座位分配、带宽预留等真实业务。

在 freeCodeCamp 项目中的落地链路

「Blood Bank」不是孤立的一道题，它背后是 freeCodeCamp 每日编程挑战的完整工程链路，仓库中可找到以下实现证据：

1. 课程块与顺序定义

curriculum/structure/blocks/daily-coding-challenges-javascript.json 定义了块的 365 道题顺序，"Challenge 320: Blood Bank"及其 id6a15cadf5f240d05a264955e位于其中。块的元数据"usesMultifileEditor": true、"disableLoopProtectTests": true等字段需要符合 curriculum/schema/challenge-schema.js 中的 Joi 校验规则（如blockLayout合法取值、helpCategory枚举、challengeType范围等）。

2. 类型与语言映射

packages/shared/src/config/challenge-types.ts 中dailyChallengeJs = 28、dailyChallengePy = 29，并由getIsDailyCodingChallenge与getDailyCodingChallengeLanguage提供"是否每日挑战、对应哪种语言"的判定，客户端据此渲染 JavaScript/Python 双语言编辑器。

3. 数据库播种

tools/daily-challenges/seed-daily-challenges.ts 是每日挑战的播种脚本：通过 GraphQL 从 dev-playground 超级块拉取题目数据，校验 JavaScript 与 Python 题目数量一致且等于 365，然后按固定的起始日期（2025-08-11，脚本内硬校验不可更改）逐日分配date，写入 MongoDB 的DailyCodingChallenges集合。

4. API 查询层

api/src/daily-coding-challenge/routes/daily-coding-challenge.ts 暴露了GET /daily-coding-challenge/date/:date、/day/:day、/today、/month/:month、/all、/newest等只读接口；响应结构（id、date、challengeNumber、title、description、javascript、python）由 api/src/daily-coding-challenge/schemas/daily-coding-challenge.ts 中的 TypeBox schema 约束，其中javascript.tests与challengeFiles正是本题# --hints--与# --seed-contents--在运行时系统中的载体。

5. 客户端校验与端到端测试

客户端通过 client/src/utils/daily-coding-challenge-validator.ts 对 API 返回的挑战数据做 Joi 二次校验（含tests、challengeFiles结构）；e2e/daily-coding-challenge.spec.ts 则以 Playwright 模拟真实浏览器流程，验证每日挑战页面的加载、JavaScript/Python 切换等行为。

因此，阅读这道 Blood Bank 题目时，你看到的不只是 6 组断言和一个参考解法，而是 freeCodeCamp"Markdown 题库 → 结构化校验 → 数据库播种 → API 下发 → 前端作答"的完整工程闭环中的一个环节。理解这道题的贪心思想后，你也可以沿着上述文件路径继续探索其余 364 道每日挑战的解法风格，或深入每日挑战 API 的查询与缓存机制。

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