--- url: /ai-agent-skills/index.md --- # Agent Skills ## 概述 Agent Skills 是 一种简单、开放的格式,用于为智能体提供新能力和专业知识。 Agent Skills 是包含指令、脚本和资源的文件夹,智能体可以发现并使用它们来更准确、更高效地完成任务。 ::: tip 本文档 **翻译自** [Agent Skills](https://agentskills.io/)。仅供个人学习使用。 翻译版本仓库提交节点为 [75287b2](https://github.com/agentskills/agentskills/commit/75287b28fb7a8106d7798de99e13189f7bea5ca0) ::: ## 仓库地址 ## Skills 搜索 ## CLI 工具 ## 相关文章 [使用 **Agent Skills** 为真实世界装备代理 —— Anthropic 官方博客](https://www.anthropic.com/engineering/equipping-agents-for-the-real-world-with-agent-skills){.readmore} [**Agent Skills** ——Claude Docs](https://platform.claude.com/docs/zh-CN/agents-and-tools/agent-skills/overview){.readmore} --- --- url: /ai-agent-skills/5-agent-skills-design-patterns/index.md --- # 每位ADK开发者都应掌握的5种智能体技能设计模式 > **原文来源**: [Google Cloud Tech on X (Twitter)](https://x.com/GoogleCloudTech/status/2033953579824758855) > **作者**: [@Saboo\_Shubham\_](https://x.com/Saboo_Shubham_) 和 [@lavinigam](https://x.com/lavinigam) 当谈到 **SKILL.md** 时,开发者往往执着于格式——写好 YAML、整理目录结构、遵循规范。但随着超过 30 个 Agent 工具(如 Claude Code、Gemini CLI 和 Cursor)采用相同的布局,格式问题实际上已经过时了。 真正的挑战在于 **内容设计**。规范解释了如何打包一个 Skill,但对如何结构化内部逻辑完全没有指导。例如,一个封装 FastAPI 约定的 Skill 与一个四步文档管道的运作方式完全不同,尽管它们表面的 SKILL.md 文件看起来一模一样。 通过对生态系统中 Skill 构建方式的研究——从 Anthropic 的代码库到 Vercel 和 Google 的内部指南——我们发现了 **5 种常见的设计模式**,可以帮助开发者构建 Agent。 本文将结合实际的 ADK 代码详细介绍每种模式: * **Tool Wrapper**:让 Agent 立即成为任何库的专家 * **Generator**:从可复用模板生成结构化文档 * **Reviewer**:按严重性对代码进行评分审查 * **Inversion**:Agent 在行动前先询问你 * **Pipeline**:通过检查点强制执行严格的多步骤工作流 ![design-patterns](../assets/5as-1.png) ## 模式一:Tool Wrapper(工具包装器) Tool Wrapper 为 Agent 提供按需获取特定库的上下文。与其将 API 约定硬编码到系统提示中,不如将它们打包成一个 Skill。Agent 只在实际使用该技术时加载这些上下文。 ![design-wrapper](../assets/5as-2.png) 这是最简单的实现模式。SKILL.md 文件监听用户提示中的特定库关键词,动态从 `references/` 目录加载内部文档,并将这些规则作为绝对真理应用。这正是你将团队内部编码指南或特定框架最佳实践直接分发到开发者工作流程中的机制。 以下是一个教 Agent 如何编写 FastAPI 代码的 Tool Wrapper 示例。注意指令如何明确告诉 Agent **只在开始审查或编写代码时才加载 `conventions.md` 文件**: ```markdown title="skills/api-expert/SKILL.md" --- name: api-expert description: FastAPI 开发最佳实践和约定。用于构建、审查或调试 FastAPI 应用、REST API 或 Pydantic 模型。 metadata: pattern: tool-wrapper domain: fastapi --- 你是 FastAPI 开发专家。将这些约定应用到用户的代码或问题中。 ## 核心约定 加载 'references/conventions.md' 获取完整的 FastAPI 最佳实践列表。 ## 审查代码时 1. 加载约定参考 2. 根据每个约定检查用户代码 3. 对每个违规,引用具体规则并建议修复 ## 编写代码时 1. 加载约定参考 2. 严格遵循每个约定 3. 为所有函数签名添加类型注解 4. 使用 Annotated 风格进行依赖注入 ``` ## 模式二:Generator(生成器) Generator 负责应用知识,而 Generator 负责强制执行一致的输出。如果你苦于 Agent 每次运行生成不同的文档结构,Generator 通过编排填空过程来解决这个问题。 ![design-generator](../assets/5as-3.png) 它利用两个可选目录:`assets/` 存放输出模板,`references/` 存放样式指南。指令充当项目经理,告诉 Agent 加载模板、阅读样式指南、询问用户缺失的变量,然后填充文档。这对于生成可预测的 API 文档、标准化提交信息或脚手架项目架构都很实用。 在这个技术报告生成器示例中,Skill 文件不包含实际的布局或语法规则。它只是协调这些资产的检索,并强制 Agent 逐步执行: ```markdown title="skills/report-generator/SKILL.md" --- name: report-generator description: 生成结构化技术报告(Markdown 格式)。当用户要求编写、创建或起草报告、摘要或分析文档时使用。 metadata: pattern: generator output-format: markdown --- 你是一个技术报告生成器。严格按以下步骤执行: 步骤 1: 加载 'references/style-guide.md' 获取语调和格式规则。 步骤 2: 加载 'assets/report-template.md' 获取所需的输出结构。 步骤 3: 询问用户填写模板所需的任何缺失信息: - 主题或议题 - 主要发现或数据点 - 目标读者(技术性、管理层、通用) 步骤 4: 按照样式指南规则填充模板。模板中的每个部分都必须出现在输出中。 步骤 5: 将完成的报告作为单个 Markdown 文档返回。 ``` ## 模式三:Reviewer(审查器) Reviewer 模式将"检查什么"与"如何检查"分离。与其编写冗长的系统提示详细说明每种代码异味,不如将模块化的评分标准存储在 `references/review-checklist.md` 文件中。 ![design-reviewer](../assets/5as-4.png) 当用户提交代码时,Agent 加载这个检查清单,系统地评分提交,按严重性分组其发现。 如果你将 Python 风格检查清单换成 OWASP 安全检查清单,使用完全相同的 Skill 基础设施就能获得完全不同的专业化审计。这是一种在人工审查代码之前自动进行 PR 审查或 catch 安全漏洞的高效方式。 以下代码审查器 Skill 演示了这种分离。指令保持静态,但 Agent 动态加载特定的审查标准,强制生成基于严重性的结构化输出: ```markdown title="skills/code-reviewer/SKILL.md" --- name: code-reviewer description: 审查 Python 代码的质量、风格和常见 bug。当用户提交代码供审查、要求代码反馈或希望代码审计时使用。 metadata: pattern: reviewer severity-levels: error,warning,info --- 你是一个 Python 代码审查员。严格按以下审查协议执行: 步骤 1: 加载 'references/review-checklist.md' 获取完整的审查标准。 步骤 2: 仔细阅读用户代码。理解其目的后再进行批评。 步骤 3: 将检查清单中的每条规则应用到代码中。对发现的每个违规: - 记录行号(或大致位置) - 分类严重性:error(必须修复)、warning(应该修复)、info(建议考虑) - 解释为什么这是一个问题,而不只是指出什么问题 - 用更正后的代码提出具体修复建议 步骤 4: 生成结构化审查,包含以下部分: - **摘要**:代码功能、整体质量评估 - **发现**:按严重性分组(错误优先,然后是警告,最后是信息) - **评分**:1-10 分并简要说明理由 - **前 3 条建议**:最有影响力的改进 ``` ## 模式四:Inversion(反转模式) Agent 本质上倾向于立即猜测和生成。Inversion 模式翻转了这种动态。不是由用户驱动提示并由 Agent 执行,而是让 Agent 充当面试官。 ![design-inversion](../assets/5as-5.png) Inversion 依赖于明确的、不可协商的门控指令(如"在所有阶段完成之前不要开始构建"),强制 Agent 首先收集上下文。它按顺序提出结构化问题,并在每个答案后等待你的回复。Agent 不会综合最终输出,直到它对你的需求和部署约束有了完整了解。 要查看实际效果,请看这个项目规划器 Skill。这里的关键要素是严格的阶段划分和明确的门控提示,阻止 Agent 综合最终计划,直到收集到所有用户答案: ```markdown title="skills/project-planner/SKILL.md" --- name: project-planner description: 通过结构化问题收集需求后再生成计划。当用户说"我想构建"、"帮我计划"、"设计一个系统"或"启动一个新项目"时使用。 metadata: pattern: inversion interaction: multi-turn --- 你正在进行结构化的需求访谈。在所有阶段完成之前,不要开始构建或设计。 ## 阶段 1 — 问题发现(一次问一个问题,等待每个答案) 按顺序提问,不要跳过任何问题。 - Q1: "这个项目为用户解决什么问题?" - Q2: "谁是主要用户?他们的技术水平如何?" - Q3: "预期的规模是多少?(每天用户数、数据量、请求率)" ## 阶段 2 — 技术约束(仅在阶段 1 完全回答后) - Q4: "你将使用什么部署环境?" - Q5: "你对技术栈有什么要求或偏好?" - Q6: "有哪些不可协商的要求?(延迟、正常运行时间、合规性、预算)" ## 阶段 3 — 综合(仅在所有问题回答后) 1. 加载 'assets/plan-template.md' 获取输出格式 2. 使用收集的需求填充模板的每个部分 3. 向用户展示完成的计划 4. 询问:"这个计划准确捕捉了你的需求吗?你想改变什么?" 5. 根据反馈迭代,直到用户确认 ``` ## 模式五:Pipeline(管道模式) 对于复杂任务,你不能承担跳过步骤或忽略指令的代价。Pipeline 模式强制执行严格的顺序工作流和硬检查点。 指令本身充当工作流定义。通过实现明确的菱形门条件(如"在从文档字符串生成转到最终组装之前需要用户批准"),Pipeline 确保 Agent 不能绕过复杂任务并呈现未验证的最终结果。 ![design-pipeline](../assets/5as-6.png) 这个模式利用所有可选目录,只在特定步骤需要时才拉取不同的参考文件和模板,保持上下文窗口简洁。 在这个文档管道示例中,注意明确的门控条件。Agent 被明确禁止在用户确认上一步生成的文档字符串之前进入组装阶段: ```markdown title="skills/doc-pipeline/SKILL.md" --- name: doc-pipeline description: 通过多步骤管道从 Python 源代码生成 API 文档。当用户要求记录模块、生成 API 文档或从代码创建文档时使用。 metadata: pattern: pipeline steps: "4" --- 你正在运行一个文档生成管道。按顺序执行每个步骤。不要跳过步骤或在步骤失败时继续。 ## 步骤 1 — 解析和清单 分析用户的 Python 代码,提取所有公共类、函数和常量。将清单呈现为检查列表。询问:"这是您想要文档化的完整公共 API 吗?" ## 步骤 2 — 生成文档字符串 对于每个缺少文档字符串的函数: - 加载 'references/docstring-style.md' 获取所需的格式 - 严格遵循样式指南生成文档字符串 - 呈现每个生成的文档字符串供用户批准 在用户确认之前不要进入步骤 3。 ## 步骤 3 — 组装文档 加载 'assets/api-doc-template.md' 获取输出结构。将所有类、函数和文档字符串编译成单个 API 参考文档。 ## 步骤 4 — 质量检查 对照 'references/quality-checklist.md' 进行审查: - 每个公共符号都已文档化 - 每个参数都有类型和描述 - 每个函数至少有一个使用示例 报告结果。在呈现最终文档之前修复问题。 ``` ## 如何选择正确的 Agent Skill 模式 每种模式回答不同的问题。使用这个决策树找到适合你用例的模式: ![design-decision-tree](../assets/5as-7.png) ## 最后,模式可以组合 这些模式不是互斥的。它们可以组合。 Pipeline Skill 可以在最后包含一个 Reviewer 步骤来双重检查自己的工作。 Generator 可以在开始时依赖 Inversion 来收集填充模板所需的变量。 得益于 ADK 的 `SkillToolset` 和渐进式披露,你的 Agent 只在运行时花费上下文 token 在它实际需要的精确模式上。 不要再试图将复杂而脆弱的指令塞进一个系统提示中了。分解你的工作流,应用正确的结构模式,构建可靠的 Agent。 ## 立即开始 Agent Skills 规范是开源的,原生支持 ADK。你已经知道如何打包格式了。现在你知道了如何设计内容。用 **Google Agent Development Kit** 构建更智能的 Agent 吧。 --- --- url: >- /ai-agent-skills/equipping-agents-for-the-real-world-with-agent-skills/index.md --- # 使用 Agent Skills 为真实世界装备代理 Claude 功能强大,但实际工作需要流程知识与组织情境。 现推出智能体技能——一种通过文件与文件夹构建专业智能体的全新方式。 *更新:我们已发布 [Agent Skills](https://agentskills.io/) 作为跨平台可移植性的开放标准。(2025年12月18日)* 随着模型能力的提升,我们现在可以构建能够与成熟计算环境交互的通用智能体。 例如,[Claude Code](https://claude.com/product/claude-code) 就能通过本地代码执行和文件系统完成跨领域的复杂任务。 但随着这些智能体日益强大,我们需要更可组合、可扩展且可移植的方式来为它们配备领域专业知识。 这促使我们创建了 [**Agent Skills**](https://www.anthropic.com/news/skills): 即组织有序的指令、脚本和资源文件夹,智能体能够动态发现并加载这些内容,从而在特定任务中表现更佳。 Skills 通过将您的专业知识打包成可供 Claude 使用的可组合资源,扩展了 Claude 的能力,将通用智能体转化为符合您需求的专用智能体。 为智能体构建一项 Skills,就如同为新员工编写入职指南。 如今,任何人都无需为每个用例零散地定制专属智能体,而是可以通过捕捉和分享流程性知识,用可组合的能力来专业化自己的智能体。 在本文中,我们将解释什么是 Skills ,展示其运作方式,并分享构建自有技能的最佳实践。 ::: center ![image](../assets/ea-1.png) Skills 是一个包含 `SKILL.md` 文件的目录,该文件内含结构化的指令、脚本和资源文件夹,用于为智能体提供额外能力。 ::: ## Skills 结构剖析 为直观展示 Skills 运作机制,让我们通过真实案例逐步解析:这是实现 [Claude 近期上线的文档编辑功能](https://www.anthropic.com/news/create-files) 的核心技能之一。 Claude 本身已具备丰富的PDF解析能力,但在直接操作PDF方面存在局限(例如填写表格)。 这项 [PDF Skill](https://github.com/anthropics/skills/tree/main/document-skills/pdf) 使我们能够赋予 Claude 此类新能力。 最基础的 Skills 形式是一个包含 `SKILL.md` file 的目录。 该文件必须以包含必要元数据的 YAML frontmatter:`name` 与 `description`。 Agent 程序在启动时,会预先将所有已安装 Skills 的 `name` 与 `description` 加载至系统提示中。 此元数据属于 **渐进式披露** 的第一层级:仅提供足够信息让 Claude 知晓何时应调用各项 Skills,而无需将所有内容载入上下文。 该文件的实际主体内容构成**第二层级**的详细信息。 若 Claude 判定某项 Skills 与当前任务相关,将通过读取完整的 `SKILL.md` 文件将其载入上下文。 ::: center ![image](../assets/ea-2.png) `SKILL.md` 文件必须以包含文件名和描述的YAML Frontmatter开头,这些信息会在启动时加载到其系统提示中。 ::: 随着 Skills 复杂度的增加,其内容可能过多而无法容纳在单个 `SKILL.md` 中,或者某些内容仅在特定场景下相关。 在这种情况下,Skills 可以在 Skills 目录中捆绑附加文件,并通过名称在 `SKILL.md` 中引用它们。 这些附加的链接文件是**第三层**(及更深入)的细节,Claude 可以根据需要选择性地浏览和发现。 在下方展示的PDF技能中,`SKILL.md` 引用了 Skills 作者选择与核心 `SKILL.md` 捆绑的 两个附加文件(`reference.md` 和 `forms.md`)。 通过将填写表单的说明移至单独的文件(`forms.md`),Skills 作者能够保持 Skills 核心的简洁性, 并相信 Claude 仅在填写表单时才会读取 `forms.md` 。 ::: center ![image](../assets/ea-3.png) 您可以在 Skills 中融入更多上下文(通过附加文件),Claude 随后可根据系统提示触发这些内容。 ::: **渐进式披露** 是使 Agent Skills 灵活且可扩展的核心设计原则。 它如同一本编排精良的手册,从目录开始,到具体章节,再到详细附录,技能让Claude能够按需加载信息: ![image](../assets/ea-4.png) 拥有文件系统和代码执行工具的智能体在处理特定任务时,无需将整个技能内容读入其上下文窗口。 这意味着可以捆绑到 Skills 中的上下文量实际上是无限的。 ## Skills 与上下文窗口 下图展示了当 Skills 被用户消息触发时,上下文窗口的变化情况。 ::: center ![image](../assets/ea-5.png) Skills 通过系统提示在上下文窗口中被触发。 ::: 所示的操作序列: ::: steps * 开始时,上下文窗口包含核心系统提示、每个已安装 Skills 的元数据以及用户的初始消息; * Claude 通过调用 Bash 工具读取 `pdf/SKILL.md` 的内容来触发 PDF Skill; * Claude 选择读取与该 SKill 捆绑的 `forms.md` 文件; * 最终,Claude 在从 PDF Skill 加载了相关指令后,继续处理用户的任务。 ::: ## Skills 与代码执行 Skills 也可以包含代码,供 Claude 自行决定作为工具执行。 大语言模型擅长处理多种任务,但某些操作更适合通过传统代码执行。 例如,通过令牌生成对列表进行排序,远比直接运行排序算法成本高昂。 除了效率考量外,许多应用需要只有代码才能提供的确定性可靠保障。 在我们的示例中,PDF Skill 包含一个预先编写的 Python 脚本,用于读取 PDF 并提取所有表单字段。 Claude 可以运行此脚本,而无需将脚本或 PDF 加载到上下文中。 由于代码具有确定性,这一工作流程是稳定且可重复的。 ::: center ![image](../assets/ea-6.png) Skills 还可以包含代码,供Claude根据任务性质自行决定是否作为工具执行。 ::: ## 开发与评估 Skills 以下是一些关于如何开始创作和测试 Skills 的实用指南: * **从评估入手**: 通过在代表性任务中运行智能体并观察其薄弱环节或需要补充上下文的场景,来识别能力缺口。 随后通过渐进式构建 Skills 来弥补这些不足。 * **构建可扩展结构**: 当 `SKILL.md` 文件变得臃肿时,将其内容拆分至独立文件并建立引用关系。 若某些上下文互斥或很少同时使用,保持独立路径可减少令牌消耗。 最后,代码既可充当可执行工具,也可作为文档。 应明确区分 Claude 应直接运行脚本还是将其作为参考上下文读取。 * **从 Claude 视角思考**: 在实际场景中观察 Claude 如何使用您的 Skills ,并根据观察结果进行迭代: 留意意外操作轨迹或对特定上下文的过度依赖。 请特别关注 Skills 的 `name` 和 `description` ,Claude 将根据这些信息决定是否针对当前任务触发该 Skill。 * **与Claude协同迭代**: 在使用 Claude 处理任务时,可要求 Claude 将其成功方法和常见错误总结为可复用的上下文及代码并整合到技能中。 若 Claude 使用 Skills 执行任务时出现偏差,可要求其自我反思问题所在。 此过程有助于发现 Claude 实际需要的上下文,而非预先猜测。 ## 使用 Skills 时的安全考量 Skills 通过指令和代码为 Claude 赋予新能力。 虽然这使得 Skills 功能强大,但也意味着恶意技能可能在使用环境中引入安全漏洞,或诱导 Claude 泄露数据并执行非预期操作。 建议仅从可信来源安装 Skills 。 若从可信度较低的来源安装 Skills ,请在使用前彻底审核其内容。 首先阅读技能包内文件,了解其功能,特别注意代码依赖项及捆绑资源(如图像或脚本)。 同时,需留意 Skills 中指示 Claude 连接可能不可信外部网络资源的指令或代码。 ## Skills 的未来展望 Agent Skills 目前已 [全面支持](https://www.anthropic.com/news/skills), 覆盖 [Claude.ai](http://claude.ai/redirect/website.v1.cb6e2017-f868-4af8-a0e9-2e618a4fc002) 、Claude Code 、Claude 智能体 SDK 以及 Claude 开发者平台。 在接下来的几周里,我们将持续新增功能,以支持技能从创建、编辑、发现、分享到使用的完整生命周期。 我们尤其期待 Skills 能帮助组织和个人与 Claude 共享其背景信息和工作流程。 我们还将探索 Skills 如何通过教导智能体掌握涉及外部工具和软件的更复杂工作流,来补充 [模型上下文协议](https://modelcontextprotocol.io/)(MCP)服务器。 展望未来,我们希望能让智能体自主创建、编辑和评估 Skills ,使它们能够将自身的行为模式固化为可复用的能力。 Skills 是一个简单的概念,对应着同样简洁的格式。 这种简洁性让组织、开发者和终端用户能更轻松地构建定制化智能体,并赋予其新的能力。 我们期待看到大家运用 Skills 创造出怎样的成果。立即查看我们的 Skills [文档](https://docs.claude.com/en/docs/agents-and-tools/agent-skills/overview) 和 [示例库](https://github.com/anthropics/claude-cookbooks/tree/main/skills),开启您的探索之旅。 ## 致谢 本文由 Barry Zhang、Keith Lazuka 和 Mahesh Murag 共同撰写,他们都对文件夹情有独钟。 特别感谢 Anthropic 公司内外众多支持、倡导并参与构建 Skills 体系的同仁。 --- --- url: /ai-agent-skills/integrate/index.md --- # 集成 Skills **将 Skills 集成到你的 智能体 中**。 如何为您的智能体或工具添加 Agent Skills 支持。 本指南说明如何为 AI智能体或开发工具添加 Skills 支持。 ## 集成方法 {#integration-approaches} 集成技能的两种主要方法: **基于文件系统的智能体** 在计算机环境(bash/unix)中运行,代表 Skills 最全面的选项。 当模型发出如 `cat /path/to/my-skill/SKILL.md` 的 Shell 命令时,Skills 即被激活。 捆绑资源通过 Shell 命令访问。 **基于工具的智能体** 无需专用计算机环境即可运行。 它们通过实现工具来允许模型触发 Skills 并访问捆绑资源。具体工具的实现由开发者决定。 ## 概述 {#overview} 支持 Skills 的智能体需要: * **发现** 配置目录中的 Skills * **加载元数据**(名称和描述)于启动时 * **匹配** 用户任务至相关 Skills * **激活** Skills:通过加载完整指令 * **执行** 脚本并按需访问资源 ## Skills 发现 {#skill-discovery} 技能是包含 `SKILL.md` 文件的文件夹。您的智能体应扫描配置目录以发现有效 Skills 。 ## 加载元数据 {#loading-metadata} 启动时仅解析每个 `SKILL.md` 文件的 frontmatter ### 解析 frontmatter {#parsing-frontmatter} ```txt function parseMetadata(skillPath): content = readFile(skillPath + "/SKILL.md") frontmatter = extractYAMLFrontmatter(content) return { name: frontmatter.name, description: frontmatter.description, path: skillPath } ``` ### 注入上下文 {#injecting-context} 在系统提示中包含 Skill 元数据,以便模型了解可用的 Skills 。 遵循您所在平台关于系统提示更新的指导。例如,对于 Claude 模型,推荐使用 XML 格式: ```xml pdf-processing Extracts text and tables from PDF files, fills forms, merges documents. /path/to/skills/pdf-processing/SKILL.md data-analysis Analyzes datasets, generates charts, and creates summary reports. /path/to/skills/data-analysis/SKILL.md ``` 对于基于文件系统的智能体,需包含 location 字段并指定 `SKILL.md` 文件的绝对路径。 基于工具的智能体则可省略此位置信息。 保持元数据简洁。每个技能添加到上下文中的内容应控制在约50-100个 tokens ## 安全注意事项 {security-considerations} 脚本执行会引入安全风险。需考虑: * **沙箱隔离**:在隔离环境中运行脚本 * **白名单机制**: 仅运行来自可信技能的脚本 * **确认**: 在执行可能危险的操作前询问用户 * **日志记录**: 记录所有脚本执行情况以供审计 ## 参考实现 {#reference-implementation} [skills-ref](https://github.com/agentskills/agentskills/tree/main/skills-ref) 库提供了用于处理 Skills 的 Python 实用工具和命令行界面。 例如: **验证 Skills 目录**: ```sh skills-ref validate ``` **为智能体提示生成 `` XML**: ```sh skills-ref to-prompt ... ``` 以库源代码作为参考实现。 --- --- url: /ai-agent-skills/overview/index.md --- # 概述 一种简单、开放的格式,用于为智能体提供新能力和专业知识。 Agent Skills 是包含指令、脚本和资源的文件夹,智能体可以发现并使用它们来更准确、更高效地完成任务。 ## 为什么选择 Agent Skills ? {#why-agent-skills} 智能体能力日益增强,但常常缺乏可靠执行实际工作所需的上下文信息。 Skills 机制通过为智能体提供程序性知识及公司、团队和用户特定上下文(可按需加载),有效解决了这一问题。 配备 Skills 集的智能体能够根据当前处理的任务动态扩展其能力。 **面向技能开发者**:一次构建能力,即可部署到多个智能体产品中。 **面向兼容智能体**:支持技能让终端用户能够为智能体开箱即用地添加新能力。 **面向团队和企业**:将组织知识封装成可移植、版本控制的包。 ## Agent Skills 能实现什么 ?{#what-can-agent-skills-enable} * **领域专业知识**:将专业知识打包成可复用的指令,从法律审查流程到数据分析流水线。 * **新能力**:为智能体赋予新能力(例如创建演示文稿、构建 MCP 服务器、分析数据集)。 * **可重复的工作流程**:将多步骤任务转化为一致且可审计的工作流程。 * **互操作性**:在不同的技能兼容智能体产品中复用同一技能。 ## 采用情况 {#adoption} Agent Skills 受到领先的 AI 开发工具支持。 ## 开放开发 {#open-development} Agent Skills 格式最初由 [Anthropic](https://www.anthropic.com/) 开发,作为开放标准发布, 并已被越来越多的智能体产品采用。该标准欢迎更广泛的生态系统参与者贡献内容。 [在 **github** 上查看](https://github.com/agentskills/agentskills){.readmore} ## 开始使用 {#get-started} :::card-grid `Skill.md` 文件的完整格式规范。 ::: :::card-grid 验证 Skills 并生成 Prompt XML。 ::: --- --- url: /ai-agent-skills/specification/index.md --- # 规范说明 Agent Skills 的完整格式规范。 本文档定义了 Agent Skills 的格式。 ## 目录结构 {#directory-structure} Skill 是一个至少包含 `SKILL.md` 文件的目录: :::file-tree * skill-name * SKILL.md # 必须 ::: ::: tip 您可以选择性地包含 [额外目录](#optional-directories),例如 `scripts/`、`references/` 和 `assets/`,以支持您的 Skill 。 ::: ## SKILL.md 格式 {#skill-md-format} `SKILL.md` 文件必须包含 YAML frontmatter,后跟 Markdown 内容。 ### frontmatter (必须) {#frontmatter-required} ```md title="SKILL.md" --- name: skill-name description: 此 Skill 的功能描述及适用场景说明。 --- ``` 可选字段包括: ```md title="SKILL.md" --- name: pdf-processing description: 从PDF文件中提取文本和表格,填写表单,合并文档。 license: Apache-2.0 metadata: author: example-org version: "1.0" --- ``` | 字段 | 必填 | 描述 | | :-------------: | :---: | :------------------------------------------------------------------- | | `name` | 是 | 最多64个字符。仅允许小写字母、数字和连字符。不能以连字符开头或结尾。 | | `description` | 是 | 最多1024个字符。非空。描述该 Skill 的功能及适用场景。 | | `license` | 否 | 许可证名称或引用的捆绑许可证文件。 | | `compatibility` | 否 | 最多500个字符。说明环境要求(目标产品、系统包、网络访问权限等)。 | | `metadata` | 否 | 用于附加元数据的任意键值映射。 | | `allowed-tools` | 否 | Skill 可使用的预批准工具列表(空格分隔)。(实验性功能) | #### `name` 字段 {#name-field} 必需的 `name` 字段: * 长度必须为 **1-64** 个字符 * 只能包含 Unicode 小写字母数字字符和连字符(`a-z` 和 `-`) * 不能以 `-` 开头或结尾 * 不能包含连续连字符(`--`) * 必须与父目录名称匹配 有效示例: ```yaml name: pdf-processing ``` ```yaml name: data-analysis ``` ```yaml name: code-review ``` 无效示例: ```yaml name: PDF-Processing # 不允许使用大写字母 [!code error] ``` ```yaml name: -pdf # 不能以连字符开头 [!code error] ``` ```yaml name: pdf--processing # 不允许使用连续连字符 [!code error] ``` #### `description` 字段 {#description-field} 必需的 `description` 字段: * 长度须为 **1-1024** 个字符 * 应同时描述 Skill 的功能及适用场景 * 应包含帮助智能体识别相关任务的关键词 优秀示例: ```yaml description: 从PDF文件中提取文本和表格,填写PDF表单,并合并多个PDF文件。适用于处理PDF文档或当用户提及PDF、表单或文档提取时。 ``` ```yaml description: Extracts text and tables from PDF files, fills PDF forms, and merges multiple PDFs. Use when working with PDF documents or when the user mentions PDFs, forms, or document extraction. ``` 反面示例 ```yaml description: Helps with PDFs. ``` #### `license` 字段 {#license-field} 可选的 `license` 字段: * 指定应用于 Skill 的许可证 * 建议保持简短(可以是许可证名称或捆绑许可证文件的名称) 示例: ```yaml license: Proprietary. LICENSE.txt has complete terms ``` #### `compatibility` 字段 {#compatibility-field} 可选的 `compatibility` 字段: * 若提供,长度须为 **1-500** 个字符 * 仅当 Skill 有特定环境要求时才应包含此字段 * 可注明目标产品、所需系统包、网络访问需求等 示例: ```yaml compatibility: Designed for Claude Code (or similar products) ``` ```yaml compatibility: Requires git, docker, jq, and access to the internet ``` ::: info 大多数 Skills 无需 `compatibility` 字段 ::: #### `metadata` 字段 {#metadata-field} 可选的 `metadata` 字段: * 从字符串键到字符串值的映射 * 客户端可用此字段存储 Agent Skills 规范未定义的其他属性 * 建议使用相对唯一的键名以避免意外冲突 示例: ```yaml metadata: author: example-org version: '1.0' ``` #### `allowed-tools` 字段 {#allowed-tools-field} 可选的 `allowed-tools` 字段: * 以空格分隔的预批准运行工具列表 * 实验性功能。不同 Agent 实现对该字段的支持可能有所差异 示例: ```yaml allowed-tools: Bash(git:*) Bash(jq:*) Read ``` ### 正文内容 {#body-content} frontmatter 之后的 Markdown 正文包含 Skill 说明。格式无限制。 撰写任何有助于智能体有效执行任务的内容即可。 推荐章节: * 分步操作指南 * 输入与输出示例 * 常见边界情况 请注意,一旦决定激活某个 Skill,Agent 将完整加载此文件。 建议将较长的 `SKILL.md` 内容拆分为引用文件。 ## 可选目录 {#optional-directories} ### scripts/ 包含 Agents 可执行的代码。脚本应满足: * 保持内容自包含或明确记录依赖关系 * 提供有用的错误提示信息 * 优雅处理边界情况 支持的语言取决于 Agent 的具体实现。常见选项包括 Python、Bash 和 JavaScript。 ### references/ 包含 Agent 在需要时可以阅读的额外文档: * **REFERENCE.md** - 详细技术参考 * **FORMS.md** - 表单模板或结构化数据格式 * 领域特定文件(**finance.md**、**legal.md** 等) 保持单个[参考文件](#file-references) 内容聚焦。Agent 按需加载这些文件,较小的文件意味着更少占用上下文。 ### assets/ 包含静态资源: * 模板(文档模板、配置模板) * 图像(图表、示例) * 数据文件(查找表、模式) ## 渐进式披露 {#progressive-disclosure} Skills 应结构化以便高效利用上下文: * **元数据 Metadata**(约100个tokens):`name` 和 `description` 字段在启动时为所有技能加载 * **使用说明 Instructions**(建议少于5000 tokens):完整的 `SKILL.md` 内容在技能激活时加载 * **资源**(按需):文件(例如位于 `scripts/`、`references/` 或 `assets/` 中的文件)仅在需要时加载 主 `SKILL.md` 文件应保持在500行以内。将详细参考资料移至单独文件。 ## 文件引用 {#file-references} 在 Skills 中引用其他文件时,请使用相对于技能根目录的相对路径: ```md title="SKILL.md" See [the reference guide](references/REFERENCE.md) for details. Run the extraction script: scripts/extract.py ``` 文件引用应保持在 `SKILL.md` 下一级深度。避免深层嵌套的引用链。 ## 验证 {#validation} 使用 [skills-ref](https://github.com/agentskills/agentskills/tree/main/skills-ref) 验证您的 Skills: ```sh skills-ref validate ./my-skill ``` 此操作会检查您的 `SKILL.md` frontmatter 是否有效并遵循所有命名约定。 --- --- url: /ai-agent-skills/what-are-skills/index.md --- Agent Skills 是一种轻量级、开放的格式,用于通过专业知识和工作流扩展AI智能体的能力。 Skills 的核心是一个包含 `SKILL.md` 文件的文件夹。 该文件包含元数据(至少包含 `name` 和 `description`)以及指导智能体执行特定任务的指令。 Skills 还可以捆绑脚本、模板和参考资料。 :::file-tree * my-skill * SKILL.md # 必需:说明 + 元数据 * scripts/ # 可选:可执行代码 * references/ # 可选:文档 * assets/ # 可选:模板、资源 ::: ## Skills 如何运作 {#how-skills-work} 技能采用 **渐进式披露** 来高效管理上下文: 1. **发现**:启动时,智能体仅加载每个可用技能的名称和描述,仅够判断何时可能相关。 2. **激活**:当任务与技能描述匹配时,智能体会将完整的SKILL.md指令读入上下文。 3. **执行**:智能体遵循指令,根据需要选择性加载引用文件或执行捆绑代码。 这种方法既保持了智能体的快速响应,又使其能按需获取更多上下文。 ## SKILL.md 文件 {#skill-md-file} 每个 Skills 都始于一个包含 YAML frontmatter 和 Markdown 内容的 `SKILL.md` 文件: ```md title="SKILL.md" --- name: pdf-processing description: 从PDF文件中提取文本和表格,填写表单,合并文档。 --- # PDF处理 ## 何时使用此 skill 当用户需要处理PDF文件时使用此 skill... ## 如何提取文本 1. 使用 pdfplumber 进行文本提取... ## 如何填写表格 ... ``` 在 `SKILL.md` 文件顶部必须包含以下 frontmatter: * `name`:简短标识符 * `description`:使用此 Skill 的时机 Markdown 正文包含实际说明内容,对结构和内容没有特定限制。 这种简单格式具有若干关键优势: * **自文档化**:Skill 作者或用户通过阅读 `SKILL.md` 即可理解其功能,便于 Skills 审计与改进。 * **可扩展性**:Skill 复杂度可涵盖从纯文本说明到可执行代码、资源文件和模板。 * **便携性**:Skills 仅由文件构成,便于编辑、版本管理和共享。 ## 后续步骤 {#next-steps} :::card-grid `Skill.md` 文件的完整格式规范。 ::: :::card-grid 验证 Skills 并生成 Prompt XML。 ::: --- --- url: /ai/index.md --- # AI 导航 ## 大模型在线应用 AI 模型网页版对话应用,通常免费使用 ## 模型服务商 通过 AI 服务商提供的 **访问接口** 和 **API KEY**,获得模型的访问权限 ### API 直供 由模型开发商直接提供的 API 接口 ### API 聚合平台 聚合多个不同的模型,提供统一的 API 接口 ## AI 搜索 ## AI 开发平台 ## 音频模型 ### 语音 ### 音乐 ## 视觉模型 ### 图像 ### 视频 ### 3D ### 数字人 ### 设计 ## 工业级模型 ## 数据集 ## 实用集成 ### 应用程序 ### MCP 市场 ### RAG 框架 ### Office 插件 ### 代码编辑器 ### CLI AI 工具 *** ## 优质开源项目 ## 相关优质文章 * [**《LLM Powered Autonomous Agents》 by Lilian Weng (OpenAI)** - 深入理解 LLM 驱动的自主 Agent 设计框架](https://lilianweng.github.io/posts/2023-06-23-agent/) * [**Prompt Engineering Guide** - 学习如何更好地设计提示词以提升 LLM 表现](https://www.promptingguide.ai/zh) * [Best 100+ Stable Diffusion Prompts - 100+ 最美的 Stable Diffusion 提示词](https://mpost.io/best-100-stable-diffusion-prompts-the-most-beautiful-ai-text-to-image-prompts) * [awesome-chatgpt-prompts - 优质的 ChatGPT 提示词](https://github.com/f/awesome-chatgpt-prompts) ## 其它 {.readmore} --- --- url: /algorithm/index.md --- # 数据结构与算法 --- --- url: /algorithm/backtracking/index.md --- # 回溯算法 ## 概述 \==回溯算法== 是一种通过尝试所有可能的候选解来解决问题的通用算法。 当发现当前候选解不可能满足条件时,会回退(回溯)到上一步,尝试其他选择。 它本质上是 **深度优先搜索(DFS)** 的一种优化形式,通过剪枝减少不必要的搜索。 ## 核心思想 * **试错**:逐步构建候选解 * **剪枝**:发现无效解时立即回溯 * **状态管理**:记录当前路径,回溯时撤销选择 ```ts function backtrack(路径: 解的部分, 选择列表: 可用选项): void { if (满足结束条件) { 结果集.push(路径副本) // 保存有效解 return } for (选择 of 选择列表) { if (无效选择) continue // 剪枝 做选择 backtrack(新路径, 新选择列表) 撤销选择 // 关键:状态重置 } } ``` ## 实现 ### 子集问题(无重复元素) ```ts function subsets(nums: number[]): number[][] { const res: number[][] = [] const backtrack = (start: number, path: number[]) => { res.push([...path]) // 保存当前子集 for (let i = start; i < nums.length; i++) { path.push(nums[i]) // 做选择 backtrack(i + 1, path) // 递归 path.pop() // 撤销选择 } } backtrack(0, []) return res } // 示例:subsets([1,2,3]) // 输出:[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] ``` ### 全排列(无重复元素) ```ts function permute(nums: number[]): number[][] { const res: number[][] = [] const used: boolean[] = Array.from({ length: nums.length }).fill(false) const backtrack = (path: number[]) => { if (path.length === nums.length) { res.push([...path]) return } for (let i = 0; i < nums.length; i++) { if (used[i]) continue // 剪枝:已使用 used[i] = true path.push(nums[i]) backtrack(path) path.pop() used[i] = false // 关键:撤销状态 } } backtrack([]) return res } // 示例:permute([1,2,3]) // 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` ## 优化技巧 * **剪枝策略**: * 提前终止无效路径(如组合总和中的 `sum > target`) * 跳过重复解(排序后判断 `if (i > start && nums[i] === nums[i-1])` ) * **状态存储**: * 使用索引(`start`)避免重复组合 * 使用布尔数组(`used[]`)标记已选元素 * **迭代代替递归**: * 对于深度大的问题,可用栈模拟递归 * **记忆化搜索**: * 缓存中间结果(适用于重叠子问题) ## 相关问题 [**LeetCode** - 回溯算法](https://leetcode.cn/problem-list/backtracking/){.read-more} ### 组合与求和问题 * **39. 组合总和**([LeetCode](https://leetcode.cn/problems/combination-sum/)) * **40. 组合总和 II**([LeetCode](https://leetcode.cn/problems/combination-sum-ii/)) * **216. 组合总和 III**([LeetCode](https://leetcode.cn/problems/combination-sum-iii/)) ### 子集与排列问题 * **78. 子集**([LeetCode](https://leetcode.cn/problems/subsets/)) * **90. 子集 II**([LeetCode](https://leetcode.cn/problems/subsets-ii/)) * **46. 全排列**([LeetCode](https://leetcode.cn/problems/permutations/)) * **47. 全排列 II**([LeetCode](https://leetcode.cn/problems/permutations-ii/)) ### 字符串与构造问题 * **22. 括号生成**([LeetCode](https://leetcode.cn/problems/generate-parentheses/)) * **51. N 皇后**([LeetCode](https://leetcode.cn/problems/n-queens/)) --- --- url: /algorithm/binary-search/index.md --- # 二分查找 ## 概述 \==二分查找(Binary Search)==,也称 **折半搜索(half-interval search)**、**对数搜索(logarithmic search)** 。 是一种高效的搜索算法,适用于已排序的数据集(如数组)。 它通过不断将搜索范围减半来定位目标值,时间复杂度为 $O(log n)$ ,远优于线性查找的 $O(n)$ 。 ## 核心思想 * **分而治之**:每次比较目标值与数组中间元素。 * **缩小范围**:根据比较结果,将搜索范围缩小一半。 * **终止条件**:找到目标值或范围为空(未找到)。 ## 过程 以在一个升序数组中查找一个数为例。 1. 它每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程; 2. 如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找; 3. 如果中间元素大于所查找的值同理,只需到左侧查找。 ## 实现 * **循环条件**:`left <= right` 确保当 `left === right` 时(只剩一个元素)仍会检查。 * **中间索引计算**: * `mid = Math.floor((left + right) / 2)` 防止小数索引 建议写作 `mid = (left + right) >> 1` 。 * 大数安全写法:`mid = left + Math.floor((right - left) / 2)`(避免溢出) 建议写作 `mid = left + ((right - left) >> 1)`。 * **边界更新**: * 目标在右侧:`left = mid + 1`(跳过已检查的 mid)。 * 目标在左侧:`right = mid - 1`(同上)。 * **终止条件**: * 找到:`arr[mid] === target`。 * 未找到:`left > right`(范围无效)。 ### 迭代实现 ```ts function binarySearch(arr: number[], target: number): number { let left = 0 let right = arr.length - 1 while (left <= right) { const mid = left + ((right - left) >> 1) // 中间索引 if (arr[mid] === target) { return mid // 找到目标 } else if (arr[mid] < target) { left = mid + 1 // 目标在右半部分 } else { right = mid - 1 // 目标在左半部分 } } return -1 // 未找到 } ``` ### 递归实现 ```ts function binarySearchRecursive( arr: number[], target: number, left: number = 0, right: number = arr.length - 1 ): number { if (left > right) return -1 // 终止条件 const mid = left + ((right - left) >> 1) if (arr[mid] === target) { return mid } else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, right) // 搜索右半 } else { return binarySearchRecursive(arr, target, left, mid - 1) // 搜索左半 } } ``` ## 最大值最小化 注意,这里的有序是广义的有序,如果一个数组中的左侧或者右侧都满足某一种条件, 而另一侧都不满足这种条件,也可以看作是一种有序(如果把满足条件看做 1,不满足看做 0, 至少对于这个条件的这一维度是有序的)。换言之,二分搜索法可以用来查找满足某种条件的最大(最小)的值。 要求满足某种条件的最大值的最小可能情况(最大值最小化),首先的想法是从小到大枚举这个作为答案的「最大值」, 然后去判断是否合法。若答案单调,就可以使用二分搜索法来更快地找到答案。 因此,要想使用二分搜索法来解这种「最大值最小化」的题目,需要满足以下三个条件: * 答案在一个固定区间内; * 可能查找一个符合条件的值不是很容易,但是要求能比较容易地判断某个值是否是符合条件的; * 可行解对于区间满足一定的单调性。换言之,如果 x 是符合条件的,那么有 x + 1 或者 x - 1 也符合条件。(这样下来就满足了上面提到的单调性) 当然,最小值最大化是同理的。 ## 适用场景 * 有序数据(数组、列表等)。 * 需要高效搜索(如数据库索引、大型数据集)。 * 变体问题:找边界、插入位置)。 ## 相关问题 [**LeetCode** - 二分查找](https://leetcode.cn/problem-list/binary-search/){.read-more} ### 基础分治应用 * **169. 多数元素**([LeetCode](https://leetcode.cn/problems/majority-element/)) * **50. Pow(x, n)**([LeetCode](https://leetcode.cn/problems/powx-n/)) ### 最大子数组问题 * **53. 最大子序和**([LeetCode](https://leetcode.cn/problems/maximum-subarray/)) ### 进阶问题 * **4. 寻找两个有序数组的中位数**([LeetCode](https://leetcode.cn/problems/median-of-two-sorted-arrays/)) * **23. 合并 K 个升序链表**([LeetCode](https://leetcode.cn/problems/merge-k-sorted-lists/)) ### 经典变体(分治思想延伸) * **215. 数组中的第K个最大元素**([LeetCode](https://leetcode.cn/problems/kth-largest-element-in-an-array/)) * **240. 搜索二维矩阵 II**([LeetCode](https://leetcode.cn/problems/search-a-2d-matrix-ii/)) --- --- url: /algorithm/breadth-first-search/index.md --- # 广度优先搜索 ## 概述 \==广度优先搜索(Breadth-First Search)(BFS)== 是一种用于遍历或搜索树/图数据结构的算法。 是图上最基础、最重要的搜索算法之一。 所谓广度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。 这样做的结果是,BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之,这条路径所包含的边数最小。 在 BFS 结束时,每个节点都是通过从起点到该点的最短路径访问的。 ## 核心思想 核心思想是 **逐层遍历**: * 从起点开始,先访问所有直接邻居 * 再访问邻居的邻居 * 使用队列(FIFO)管理待访问节点 * 避免重复访问(通过记录已访问节点) ## 实现 ### 图结构定义 ```ts type Graph = Record // 邻接表表示法 // 示例图结构 const graph: Graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] } // A → B → C // B → D → E // C → F ← E ``` ### BFS基础实现 ```ts function bfs(graph: Graph, start: string): string[] { const visited = new Set() // 记录已访问节点 const queue: string[] = [start] // 初始化队列 const result: string[] = [] // 存储遍历结果 visited.add(start) while (queue.length > 0) { const current = queue.shift()! // 从队列头部取出节点 result.push(current) // 遍历当前节点的所有邻居 for (const neighbor of graph[current]) { if (!visited.has(neighbor)) { visited.add(neighbor) queue.push(neighbor) // 新节点加入队列尾部 } } } return result } // 测试执行 console.log(bfs(graph, 'A')) // 输出: ['A', 'B', 'C', 'D', 'E', 'F'] ``` ### 最短路径实现(无权图) ```ts function shortestPath( graph: Graph, start: string, target: string ): string[] | null { const visited = new Set([start]) const queue: string[] = [start] const predecessor: Record = {} // 记录前驱节点 const distance: Record = { [start]: 0 } // 记录距离 while (queue.length > 0) { const current = queue.shift()! if (current === target) { // 回溯构建路径 const path = [target] let node = target while (node !== start) { node = predecessor[node] path.unshift(node) } return path } for (const neighbor of graph[current]) { if (!visited.has(neighbor)) { visited.add(neighbor) predecessor[neighbor] = current distance[neighbor] = distance[current] + 1 queue.push(neighbor) } } } return null // 未找到路径 } // 测试最短路径 console.log(shortestPath(graph, 'A', 'F')) // 输出: ['A', 'C', 'F'](最短路径) ``` ### 执行过程示例(从A开始) | 步骤 | 队列状态 | 当前节点 | 新访问节点 | 访问顺序 | | :---: | :--------- | :------: | :--------: | :------------------ | | 1 | \[A] | A | B, C | \[A] | | 2 | \[B, C] | B | D, E | \[A, B] | | 3 | \[C, D, E] | C | F | \[A, B, C] | | 4 | \[D, E, F] | D | (无新节点) | \[A, B, C, D] | | 5 | \[E, F] | E | (F已访问) | \[A, B, C, D, E] | | 6 | \[F] | F | - | \[A, B, C, D, E, F] | ## 关键解析 * **队列(Queue)**: * 使用数组模拟队列(push()入队,shift()出队) * 确保先进先出(FIFO)的访问顺序 * **访问记录(Visited Set)**: * 防止重复访问和循环 * 空间换时间(O(1)时间复杂度检查) * **前驱记录(Predecessor Map)**: * 存储节点的来源节点 * 用于回溯构建完整路径 ## 性能优化 * **双向BFS**:从起点和终点同时搜索(适合已知终点的场景) * **层级记录**:使用level变量替代距离字典减少内存 * **队列选择**:使用链表实现真正O(1)出队的队列 * **剪枝策略**:提前终止不符合条件的路径 ## 适用场景 * **社交网络**:查找N度好友关系 * **路径规划**:迷宫最短路径(无权图) * **网络爬虫**:分层抓取网页 * **连通性检测**:判断岛屿数量(网格BFS) * **状态转换**:解决华容道/八数码问题 ## 相关问题 [**LeetCode** - 广度优先搜索 - Breadth-First Search](https://leetcode.cn/problem-list/breadth-first-search/){.read-more} ### 基础图遍历 * **LCP 07. 传递信息** ([LeetCode](https://leetcode.cn/problems/chuan-di-xin-xi/)) * **547. 朋友圈**([LeetCode](https://leetcode.cn/problems/friend-circles/)) ### 网格类问题(矩阵BFS) * **542. 01 矩阵**([LeetCode](https://leetcode.cn/problems/01-matrix/)) * **994. 腐烂的橘子**([LeetCode](https://leetcode.cn/problems/rotting-oranges/)) * **1162. 地图分析(最短路径)**([LeetCode](https://leetcode.cn/problems/maximum-distance-in-arrays/)) ### 二叉树层序遍历 * **199. 二叉树的右视图**([LeetCode](https://leetcode.cn/problems/binary-tree-right-side-view/)) * **1609. 奇偶树**([LeetCode](https://leetcode.cn/problems/even-odd-tree/)) ### 进阶挑战题 * **127. 单词接龙**([LeetCode](https://leetcode.cn/problems/word-ladder/)) * **417. 太平洋大西洋水流问题**([LeetCode](https://leetcode.cn/problems/pacific-atlantic-water-flow/)) --- --- url: /algorithm/bubble-sort/index.md --- # 冒泡排序 ## 概述 \==冒泡排序(Bubble sort)== 一种基础的比较排序算法。 ### 核心思想 **重复遍历数组,依次比较相邻元素,将较大值向后交换**,如同气泡上浮的过程。 ## 算法步骤 1. **外层循环**:控制遍历轮数(n-1 轮) 2. **内层循环**:比较相邻元素,将较大值后移 3. **优化点**:每轮结束后,末尾元素已有序,可减少比较范围 4. **提前终止**:当某轮无交换时,说明数组已有序,提前结束 ## 时间复杂度 * 在序列完全有序时,冒泡排序只需遍历一遍数组,不用执行任何交换操作,时间复杂度为 $O(n)$。 * 在最坏情况下,冒泡排序要执行 $\frac{(n-1)n}{2}$ 次交换操作,时间复杂度为 $O(n^2)$。 * 冒泡排序的平均时间复杂度为 $O(n^2)$。 ## 空间复杂度 $O(1)$(原地排序) ## 稳定性 **稳定**(相同元素顺序不变) ## 伪代码 $$ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & flag\gets True\\ 5 & \textbf{while }flag\\ 6 & \qquad flag\gets False\\ 7 & \qquad\textbf{for }i\gets1\textbf{ to }n-1\\ 8 & \qquad\qquad\textbf{if }A\[i]>A\[i + 1]\\ 9 & \qquad\qquad\qquad flag\gets True\\ 10 & \qquad\qquad\qquad \text{Swap } A\[i]\text{ and }A\[i + 1] \end{array} $$ ## 实现 ```ts function bubbleSort(arr: number[]): number[] { const n = arr.length // 复制数组以避免修改原数组(可选) const sortedArr = [...arr] // 外层循环:控制遍历轮数(n-1轮) for (let i = 0; i < n - 1; i++) { let swapped = false // 优化标记 // 内层循环:比较相邻元素(每轮减少i个已排序元素) for (let j = 0; j < n - 1 - i; j++) { // 如果前一个元素大于后一个元素 if (sortedArr[j] > sortedArr[j + 1]) { // 交换元素(ES6解构赋值) [sortedArr[j], sortedArr[j + 1]] = [sortedArr[j + 1], sortedArr[j]] swapped = true // 标记发生交换 } } // 如果本轮无交换,说明数组已有序,提前终止 if (!swapped) break } return sortedArr } // 测试示例 const unsortedArray = [64, 34, 25, 12, 22, 11, 90] const sortedArray = bubbleSort(unsortedArray) console.log('排序前:', unsortedArray) // [64, 34, 25, 12, 22, 11, 90] console.log('排序后:', sortedArray) // [11, 12, 22, 25, 34, 64, 90] ``` ### 执行过程示例 (`[5, 3, 8, 4]`) * 第一轮: * 比较 $5 > 3$ → 交换 → `[3, 5, 8, 4]` * 比较 $5 < 8$ → 不交换 * 比较 $8 > 4$ → 交换 → `[3, 5, 4, 8]` * 第二轮: * 比较 $3 < 5$ → 不交换 * 比较 $5 > 4$ → 交换 → `[3, 4, 5, 8]` * 检查发现无交换 → 提前终止 ## 优化 * **优化内层循环范围** ```ts for (let j = 0; j < n - 1 - i; j++) { // ... } ``` 每轮结束后,末尾 i 个元素已有序,无需再比较。 * **提前终止** ```ts if (!swapped) break ``` 当数组在中间轮次已有序时,避免无效遍历。 --- --- url: /algorithm/bucket-sort/index.md --- # 桶排序 ## 概述 \==桶排序(Bucket Sort)== 是一种分布式排序算法,适用于数据分布均匀的场景。 ### 核心思想 将数据分散到多个有序的桶中,对每个桶单独排序,最后合并所有桶。 ## 基本原理 * **分桶**:根据元素范围创建固定数量的桶,将元素分配到对应的桶中。 * **桶内排序**:对每个非空桶单独排序(通常用插入排序等简单算法)。 * **合并结果**:按桶顺序合并所有元素。 ## 过程 桶排序按下列步骤进行: 1. 设置一个定量的数组当作空桶; 2. 遍历序列,并将元素一个个放到对应的桶中; 3. 对每个不是空的桶进行排序; 4. 从不是空的桶里把元素再放回原来的序列中。 ## 时间复杂度 桶排序的平均时间复杂度为 $O(n + n^2/k + k)$(将值域平均分成 $n$ 块 + 排序 + 重新合并元素),当 $k\approx n$ 时为 $O(n)$。 桶排序的最坏时间复杂度为 $O(n^2)$。 ## 空间复杂度 桶排序的空间复杂度为 $O(n + k)$。 (需额外存储桶) ## 稳定性 如果使用稳定的内层排序,并且将元素插入桶中时不改变元素间的相对顺序,那么桶排序就是一种稳定的排序算法。 由于每块元素不多,一般使用插入排序。此时桶排序是一种稳定的排序算法。 ## 实现 ```ts function bucketSort(arr: number[], bucketSize: number = 5): number[] { if (arr.length === 0) return arr // 1. 计算数组最小/最大值 let min = arr[0] let max = arr[0] for (let i = 1; i < arr.length; i++) { if (arr[i] < min) min = arr[i] else if (arr[i] > max) max = arr[i] } // 2. 初始化桶 const bucketCount = Math.floor((max - min) / bucketSize) + 1 const buckets: number[][] = Array.from({ length: bucketCount }) for (let i = 0; i < bucketCount; i++) { buckets[i] = [] } // 3. 元素分配到桶中 for (let num of arr) { const bucketIndex = Math.floor((num - min) / bucketSize) buckets[bucketIndex].push(num) } // 4. 对每个桶排序并合并 const sortedArr: number[] = [] for (let bucket of buckets) { if (bucket.length > 0) { // 使用插入排序(可替换为其他排序) insertionSort(bucket) sortedArr.push(...bucket) } } return sortedArr } // 插入排序辅助函数 function insertionSort(arr: number[]): void { for (let i = 1; i < arr.length; i++) { const key = arr[i] let j = i - 1 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j] j-- } arr[j + 1] = key } } // 测试用例 const arr = [0.42, 0.32, 0.75, 0.12, 0.98, 0.63] console.log(bucketSort(arr)) // 输出: [0.12, 0.32, 0.42, 0.63, 0.75, 0.98] ``` ## 优化 * **动态桶大小**:根据数据分布动态调整 `bucketSize` 。 * **桶内排序算法**:对大数据桶使用 ==快速排序(QuickSort)== 提升效率。 * **空桶处理**:跳过空桶减少不必要的遍历。 --- --- url: /algorithm/data-structure/array/index.md --- # 数组 ## 概述 \==数组(Array)== 是一种有序的线性数据结构,它的每个元素都是一个独立的数据项,可以通过下标快速访问。 ## 核心特性 * **有序性**:数组中的元素按照一定的顺序排列,可以通过下标访问特定位置的元素。 * **线性性**:数组中的元素是连续存储的,可以通过下标访问特定位置的元素。 * **可变性**:数组可以动态增加或删除元素,可以根据需要调整数组的大小。 ## 相关问题 [**LeetCode** - 数组](https://leetcode.cn/problem-list/array/){.read-more} ### 基础操作与双指针 * **1. 两数之和**([LeetCode](https://leetcode.cn/problems/two-sum/)) * **283. 移动零**([LeetCode](https://leetcode.cn/problems/move-zeroes/)) * **11. 盛最多水的容器**([LeetCode](https://leetcode.cn/problems/container-with-most-water/)) * **15. 三数之和**([LeetCode](https://leetcode.cn/problems/3sum/)) ### 二分查找与滑动窗口 * **704. 二分查找**([LeetCode](https://leetcode.cn/problems/binary-search/)) * **35. 搜索插入位置**([LeetCode](https://leetcode.cn/problems/search-insert-position/)) * **209. 长度最小的子数组**([LeetCode](https://leetcode.cn/problems/minimum-size-subarray-sum/)) * **2653. 滑动子数组的美丽值**([LeetCode](https://leetcode.cn/problems/sliding-subarray-beauty/)) ### 经典多维数组 * **59. 螺旋矩阵 II**([LeetCode](https://leetcode.cn/problems/spiral-matrix-ii/)) * **724. 寻找数组的中心索引**([LeetCode](https://leetcode.cn/problems/find-pivot-index/)) * **18. 四数之和**([LeetCode](https://leetcode.cn/problems/4sum/)) * **26. 删除有序数组中的重复项**([LeetCode](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)) --- --- url: /algorithm/data-structure/binary-tree/index.md --- # 二叉树 ## 概述 \==二叉树(Binary Tree)== 是一种非线性数据结构,每个节点最多有两个子节点(左子节点和右子节点)。 ## 核心特性 * **度**:节点拥有的子树数(二叉树节点度 ≤ 2) * **层次**:根节点为第 1 层,逐级递增 * **深度**:从根到节点的路径长度 * **高度**:从节点到最深叶子的路径长度 ## 二叉树基础节点实现 ```ts class TreeNode { val: T left: TreeNode | null right: TreeNode | null constructor( val: T, left: TreeNode | null = null, right: TreeNode | null = null ) { this.val = val this.left = left this.right = right } } ``` ## 特殊二叉树 * **完全二叉树**:除最后一层外全满,最后一层左对齐 * **满二叉树**:所有非叶子节点都有两个子节点 * **二叉搜索树 (BST)**:左子树所有值 < 根 < 右子树所有值 ## 二叉搜索树的实现 ```ts // 满二叉树:所有非叶子节点都有两个子节点 class FullBinaryTree { /* 实现 */ } // 完全二叉树:除最后一层外全满,最后一层左对齐 class CompleteBinaryTree { /* 实现 */ } // 二叉搜索树 (BST):左子树所有值 < 根 < 右子树所有值 class BinarySearchTree { root: TreeNode | null = null insert(val: T): void { const newNode = new TreeNode(val) if (!this.root) { this.root = newNode return } let current = this.root while (true) { if (val < current.val) { if (!current.left) { current.left = newNode break } current = current.left } else { if (!current.right) { current.right = newNode break } current = current.right } } } } ``` ## 二叉树的遍历 访问树的所有节点有三种遍历方式:中序,先序和后序。 * **中序遍历**:以从最小到最大的顺序访问所有节点 * **先序遍历**:以优先于后代节点的顺序访问每个节点 * **后序遍历**:先访问节点的后代节点再访问节点本身 属于何种遍历方式,通常可以根据 根节点 所在的位置: * **先序遍历**:**根** --> 左子树 --> 右子树 * **中序遍历**:左子树 --> **根** --> \*\*右子树 * **后序遍历**:左子树 --> 右子树 -- > **根** ### 先序遍历(Preorder Traversal) **访问顺序**:根节点 → 左子树 → 右子树 **应用场景**:创建树副本、序列化树结构、前缀表达式生成 ```ts // 递归实现 function preorder(root: TreeNode | null): T[] { if (!root) return [] return [ root.val, ...preorder(root.left), ...preorder(root.right) ] } // 迭代实现(使用栈) function preorderIterative(root: TreeNode | null): T[] { if (!root) return [] const stack: TreeNode[] = [root] const result: T[] = [] while (stack.length) { const node = stack.pop()! result.push(node.val) if (node.right) stack.push(node.right) // 右子先入栈 if (node.left) stack.push(node.left) // 左子后入栈(后进先出) } return result } ``` ### 中序遍历 (Inorder Traversal) **访问顺序**:左子树 → 根节点 → 右子树 **应用场景**:二叉搜索树排序输出、表达式树中缀表示 ```ts // 递归实现 function inorder(root: TreeNode | null): T[] { if (!root) return [] return [ ...inorder(root.left), root.val, ...inorder(root.right) ] } // 迭代实现(使用指针+栈) function inorderIterative(root: TreeNode | null): T[] { const stack: TreeNode[] = [] const result: T[] = [] let curr = root while (curr || stack.length) { // 深入左子树 while (curr) { stack.push(curr) curr = curr.left } // 回溯访问节点 curr = stack.pop()! result.push(curr.val) // 转向右子树 curr = curr.right } return result } ``` ### 后序遍历(Postorder Traversal) **访问顺序**:左子树 → 右子树 → 根节点 **应用场景**:释放树内存、计算目录大小、后缀表达式求值 ```ts // 递归实现 function postorder(root: TreeNode | null): T[] { if (!root) return [] return [ ...postorder(root.left), ...postorder(root.right), root.val ] } // 迭代实现(反转法) function postorderIterative(root: TreeNode | null): T[] { if (!root) return [] const stack: TreeNode[] = [root] const result: T[] = [] while (stack.length) { const node = stack.pop()! result.push(node.val) if (node.left) stack.push(node.left) if (node.right) stack.push(node.right) } return result.reverse() // 反转先序变体结果 } // 迭代实现(双栈法) function postorderTwoStacks(root: TreeNode | null): T[] { if (!root) return [] const stack1: TreeNode[] = [root] const stack2: TreeNode[] = [] const result: T[] = [] while (stack1.length) { const node = stack1.pop()! stack2.push(node) if (node.left) stack1.push(node.left) if (node.right) stack1.push(node.right) } while (stack2.length) { result.push(stack2.pop()!.val) } return result } ``` ### 遍历过程 ```mermaid --- title: 示例树 --- graph TD A --> B A --> C B --> D B --> E C --> F C --> G ``` | 遍历方式 | 访问顺序 | 输出结果 | | -------- | -------------- | --------------- | | 先序遍历 | A→B→D→E→C→F->G | `[A,B,D,E,C,F]` | | 中序遍历 | D→B→E→A→C→F->G | `[D,B,E,A,C,F]` | | 后序遍历 | D→E→B→F→G->C→A | `[D,E,B,F,C,A]` | ## 二叉树的搜索 在二叉树中搜索值是树操作中最基础和重要的操作之一。 ### 普通二叉树搜索 ::: code-tabs @tab 递归实现 ```ts function searchBinaryTree( root: TreeNode | null, target: T ): TreeNode | null { if (!root) return null // 检查当前节点 if (root.val === target) return root // 递归搜索左子树 const leftResult = searchBinaryTree(root.left, target) if (leftResult) return leftResult // 递归搜索右子树 return searchBinaryTree(root.right, target) } ``` @tab 迭代实现(使用栈) ```ts function searchBinaryTreeIterative( root: TreeNode | null, target: T ): TreeNode | null { if (!root) return null const stack: TreeNode[] = [root] while (stack.length) { const node = stack.pop()! // 检查当前节点 if (node.val === target) return node // 将子节点压入栈 if (node.right) stack.push(node.right) if (node.left) stack.push(node.left) } return null } ``` ::: ### 二叉搜索树(BST)搜索 二叉搜索树具有有序特性,可以高效搜索: ::: code-tabs @tab 递归实现 ```ts function searchBST( root: TreeNode | null, target: T, comparator: (a: T, b: T) => number = (a, b) => a === b ? 0 : a > b ? 1 : -1 ): TreeNode | null { if (!root) return null const comp = comparator(target, root.val) if (comp === 0) return root // 找到目标 if (comp < 0) return searchBST(root.left, target, comparator) // 目标小于当前值,搜索左子树 return searchBST(root.right, target, comparator) // 目标大于当前值,搜索右子树 } ``` @tab 迭代实现 ```ts function searchBSTIterative( root: TreeNode | null, target: T, comparator: (a: T, b: T) => number = (a, b) => a === b ? 0 : a > b ? 1 : -1 ): TreeNode | null { let current = root while (current) { const comp = comparator(target, current.val) if (comp === 0) return current // 找到目标 if (comp < 0) current = current.left // 目标小于当前值,转向左子树 else current = current.right // 目标大于当前值,转向右子树 } return null // 未找到 } ``` ::: ### 搜索路径记录 有时我们需要记录搜索路径而不仅仅是找到节点: ```ts function searchWithPath( root: TreeNode | null, target: T ): TreeNode[] | null { if (!root) return null const path: TreeNode[] = [] let found = false function dfs(node: TreeNode | null): boolean { if (!node || found) return false path.push(node) if (node.val === target) { found = true return true } if (dfs(node.left)) return true if (dfs(node.right)) return true path.pop() return false } dfs(root) return found ? path : null } ``` ## 时间复杂度 | 操作 | 平均 | 最差 | | --------- | ---------- | ------ | | 访问/搜索 | $O(log n)$ | $O(n)$ | | 插入/删除 | $O(log n)$ | $O(n)$ | | 空间 | $O(n)$ | $O(n)$ | ## 适用场景 * **数据库索引**:B/B+ 树(二叉树变种) * **文件系统**:目录树结构 * **编译器**:语法分析树 * **游戏 AI**:决策树 * **数据压缩**:哈夫曼编码树 ## 相关问题 [**LeetCode** - 二叉树](https://leetcode.cn/problem-list/tree/){.read-more} ### 基础操作 * **101. 对称二叉树**([LeetCode](https://leetcode.cn/problems/symmetric-tree/)) * **104. 二叉树的最大深度**([LeetCode](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)) * **226. 翻转二叉树**([LeetCode](https://leetcode.cn/problems/invert-binary-tree/)) * **102. 二叉树的层序遍历**([LeetCode](https://leetcode.cn/problems/binary-tree-level-order-traversal/)) * **199. 二叉树的右视图**([LeetCode](https://leetcode.cn/problems/binary-tree-right-side-view/)) ### 路径、深度与综合应用 * **112. 路径总和**([LeetCode](https://leetcode.cn/problems/path-sum/)) * **543. 二叉树的直径**([LeetCode](https://leetcode.cn/problems/diameter-of-binary-tree/)) * **110. 平衡二叉树**([LeetCode](https://leetcode.cn/problems/balanced-binary-tree/)) * **114. 二叉树展开为链表**([LeetCode](https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/)) ### 二叉搜索树(BST)专项 * **98. 验证二叉搜索树**([LeetCode](https://leetcode.cn/problems/validate-binary-search-tree/)) * **230. 二叉搜索树中第K小的元素**([LeetCode](https://leetcode.cn/problems/kth-smallest-element-in-a-bst/)) * **538. 把二叉搜索树转换为累加树**([LeetCode](https://leetcode.cn/problems/convert-bst-to-greater-tree/)) * **701. 二叉搜索树中的插入操作**([LeetCode](https://leetcode.cn/problems/insert-into-a-binary-search-tree/)) --- --- url: /algorithm/data-structure/graph/index.md --- # 图 [**维基百科** - 图论](https://zh.wikipedia.org/wiki/%E5%9B%BE%E8%AE%BA){.read-more} ::: warning 受限于篇幅和作者个人水平,本篇仅粗略的介绍 **图** 的一些基本概念,有兴趣的读者可以自行了解更多的知识。 ::: ## 概述 \==图(Graph)== 是一种表示多对多关系的非线性数据结构,由 **顶点(Vertex)** 和 **边(Edge)** 组成。 ## 图的核心概念 * **顶点(Vertex)**:图中的基本元素(节点) * **边(Edge)**:连接两个顶点的关系(可带权重) * **类型**: * **无向图**:边无方向(A-B 表示双向关系) * **有向图**:边有方向(A→B 表示单向关系) * **术语**: * **度(Degree)**:顶点连接的边数 * **路径(Path)**:顶点序列通过边连接 * **环(Cycle)**:起点=终点的路径 * **连通图**:任意两顶点间存在路径 ## 图的表示方法 ### 邻接矩阵(Adjacency Matrix) ```ts class GraphMatrix { private matrix: number[][] private vertices: string[] constructor(vertices: string[]) { this.vertices = vertices this.matrix = Array.from({ length: vertices.length }) .fill(0) .map(() => Array.from({ length: vertices.length }).fill(0)) } // 添加边(无向图) addEdge(v1: string, v2: string, weight: number = 1) { const i = this.vertices.indexOf(v1) const j = this.vertices.indexOf(v2) this.matrix[i][j] = weight this.matrix[j][i] = weight // 有向图时删除此行 } // 打印矩阵 print() { console.log(` ${this.vertices.join(' ')}`) this.matrix.forEach((row, i) => { console.log(`${this.vertices[i]} ${row.join(' ')}`) }) } } // 使用示例 const graph = new GraphMatrix(['A', 'B', 'C']) graph.addEdge('A', 'B', 3) graph.addEdge('B', 'C', 2) graph.print() /* 输出: A B C A 0 3 0 B 3 0 2 C 0 2 0 */ ``` ### 邻接表(Adjacency List) ```ts interface Edge { vertex: string, weight: number } class GraphList { private adjacencyList: Map = new Map() addVertex(vertex: string): void { if (!this.adjacencyList.has(vertex)) { this.adjacencyList.set(vertex, []) } } addEdge(v1: string, v2: string, weight: number = 1): void { this.adjacencyList.get(v1)?.push({ vertex: v2, weight }) // 无向图需添加反向边(有向图时删除) this.adjacencyList.get(v2)?.push({ vertex: v1, weight }) } getNeighbors(vertex: string): Edge[] { return this.adjacencyList.get(vertex) || [] } print() { this.adjacencyList.forEach((edges, vertex) => { const edgeStr = edges.map(e => `${e.vertex}(${e.weight})`).join(', ') console.log(`${vertex} -> ${edgeStr}`) }) } } // 使用示例 const graph = new GraphList() graph.addVertex('A') graph.addVertex('B') graph.addVertex('C') graph.addEdge('A', 'B', 3) graph.addEdge('B', 'C', 2) graph.print() /* 输出: A -> B(3) B -> A(3), C(2) C -> B(2) */ ``` ## 图的应用场景 * **社交网络**:好友关系(顶点=用户,边=关注) * **路径规划**:地图导航(顶点=地点,边=道路权重) * **依赖分析**:编译顺序(有向无环图拓扑排序) * **推荐系统**:用户-商品二部图 ## 相关问题 [**LeetCode** - 图](https://leetcode.cn/problem-list/graph/){.read-more} ### 基础遍历与连通性问题 * **200. 岛屿数量**([LeetCode](https://leetcode.cn/problems/number-of-islands/)) * **133. 克隆图**([LeetCode](https://leetcode.cn/problems/clone-graph/)) ### 环检测与树结构判断 * **261. 以图判树**([LeetCode](https://leetcode.cn/problems/graph-valid-tree/)) * **207. 课程表**([LeetCode](https://leetcode.cn/problems/course-schedule/)) ### 最短路径与多源遍历 * **743. 网络延迟时间**([LeetCode](https://leetcode.cn/problems/network-delay-time/)) * **994. 腐烂的橘子**([LeetCode](https://leetcode.cn/problems/oranges-rotting/)) ### 拓扑排序与应用 * **210.课程表 II**([LeetCode](https://leetcode.cn/problems/course-schedule-ii/)) * **310. 最小高度树**([LeetCode](https://leetcode.cn/problems/minimum-height-trees/)) ### 矩阵与隐式图转换 * **417. 太平洋大西洋水流问题**([LeetCode](https://leetcode.cn/problems/pacific-atlantic-water-flow/)) * **127. 单词接龙**([LeetCode](https://leetcode.cn/problems/word-ladder/)) --- --- url: /algorithm/data-structure/hash-table/index.md --- # 哈希表 ## 概述 \==哈希表(Hash Table)== 是一种基于键值对(key-value)存储的高效数据结构,通过哈希函数将键映射到存储位置, 实现平均时间复杂度 $O(1)$ 的插入、删除和查找操作。 ::: center ![hash-table](/images/algorithm/hashtable.svg) ::: 以 `key-value` 形式存储数据,是指任意的键值 key 都唯一对应到内存中的某个位置。 只需要输入查找的键值,就可以快速地找到其对应的 value。 可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数,浮点数,字符串甚至结构体。 ## 核心特性 ### 哈希函数 (Hash Function) **将任意大小的数据(键)映射到固定大小的值(哈希值)。** 要让键值对应到内存中的位置,就要为键值计算索引,也就是计算这个数据应该放到哪里。 这个根据键值计算索引的函数就叫做哈希函数,也称散列函数。 举个例子,如果键值是一个人的身份证号码,哈希函数就可以是号码的后四位,当然也可以是号码的前四位。 生活中常用的「手机尾号」也是一种哈希函数。 在实际的应用中,键值可能是更复杂的东西,比如浮点数、字符串、结构体等,这时候就要根据具体情况设计合适的哈希函数。 哈希函数应当易于计算,并且尽量使计算出来的索引均匀分布。 **对于 哈希函数,应该满足以下要求**: * **一致性**:相同的键总是产生相同的哈希值。 * **高效性**:计算速度快。 * **均匀性**:尽可能均匀地分布哈希值,以减少冲突。 ### 冲突解决 (Collision Resolution) 如果对于任意的键值,哈希函数计算出来的索引都不相同,那只用根据索引把 $(key, value)$ 放到对应的位置就行了。 但实际上,常常会出现两个不同的键值,他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。 **常见的冲突解决方法包括**: * **开散列法(Open hashing)**:也称 **拉链法**,在每个存放数据的地方开一个链表,如果有多个键值索引到同一个地方, 只用把他们都放到那个位置的链表里就行了。 查询的时候需要把对应位置的链表整个扫一遍,对其中的每个数据比较其键值与查询的键值是否一致。 如果索引的范围是 $1\ldots M$,哈希表的大小为 $N$,那么一次 插入/查询 需要进行期望 $O(\frac{N}{M})$ 次比较。 * **闭散列法(Closed hashing)**:把所有记录直接存储在散列表中,如果发生冲突则根据某种方式继续进行探查。 比如线性探查法:如果在 `d` 处发生冲突,就依次检查 `d + 1`,`d + 2` …… ### 动态扩容 (Rehashing) 当负载因子(元素数/桶数)超过阈值(如 0.75)时,扩容并重新哈希所有元素。 ## 哈希表的实现 ```ts type Bucket = Array<[K, V]> // 桶结构:存储键值对元组的数组 class HashTable { private buckets: Array> private capacity: number private size: number private loadFactor: number = 0.75 constructor(initialCapacity: number = 16) { this.capacity = initialCapacity this.size = 0 this.buckets = Array.from({ length: initialCapacity }, () => []) } // 哈希函数(简化版,实际需更健壮) private hash(key: K): number { const keyString = String(key) let hash = 0 for (let i = 0; i < keyString.length; i++) { hash = (hash << 5) + keyString.charCodeAt(i) hash = hash & hash // 转为32位整数 hash = Math.abs(hash) } return hash % this.capacity } // 插入/更新键值对 put(key: K, value: V): void { const index = this.hash(key) const bucket = this.buckets[index] // 检查是否已存在相同key for (const pair of bucket) { if (pair[0] === key) { pair[1] = value // 更新值 return } } // 新增键值对 bucket.push([key, value]) this.size++ // 检查扩容 if (this.size / this.capacity > this.loadFactor) { this.resize() } } // 获取值 get(key: K): V | undefined { const index = this.hash(key) const bucket = this.buckets[index] for (const [k, v] of bucket) { if (k === key) return v } return undefined } // 删除键值对 remove(key: K): boolean { const index = this.hash(key) const bucket = this.buckets[index] for (let i = 0; i < bucket.length; i++) { if (bucket[i][0] === key) { bucket.splice(i, 1) this.size-- return true } } return false } // 动态扩容 private resize(): void { const oldBuckets = this.buckets this.capacity *= 2 this.buckets = Array.from({ length: this.capacity }, () => []) this.size = 0 // 重新哈希所有元素 for (const bucket of oldBuckets) { for (const [key, value] of bucket) { this.put(key, value) // 插入到新桶 } } } // 当前元素数量 getSize(): number { return this.size } } ``` ## 时间复杂度 | 操作 | 时间复杂度 | 说明 | | -------- | ------------------------- | ----------------------- | | put() | 平均 $O(1)$ ,最坏 $O(n)$ | 哈希计算 + 桶内线性扫描 | | get() | 平均 $O(1)$ ,最坏 $O(n)$ | 桶内线性查找 | | remove() | 平均 $O(1)$ ,最坏 $O(n)$ | 桶内查找后删除 | | resize() | $O(n)$ | 所有元素重新哈希 | ## 适用场景 * 高频插入/删除且需快速查找 * 缓存实现(如 LRU Cache) * 数据库索引 * 字典类应用(词频统计) ## 相关问题 [**LeetCode** - 哈希表](https://leetcode.cn/problem-list/hash-table/){.read-more} [**LeetCode** - 哈希函数](https://leetcode.cn/problem-list/hash-function/){.read-more} ### 基础操作(数组/集合/映射) * **1. 两数之和**([LeetCode](https://leetcode.cn/problems/two-sum/)) * **242. 有效的字母异位词**([LeetCode](https://leetcode.cn/problems/valid-anagram/)) * **349. 两个数组的交集**([LeetCode](https://leetcode.cn/problems/intersection-of-two-arrays/)) * **202. 快乐数**([LeetCode](https://leetcode.cn/problems/happy-number/)) ### 复杂数据结构与策略 * **146. LRU 缓存**([LeetCode](https://leetcode.cn/problems/lru-cache/)) * **49. 字母异位词分组**([LeetCode](https://leetcode.cn/problems/group-anagrams/)) * **974. 和可被 K 整除的子数组**([LeetCode](https://leetcode.cn/problems/subarray-sums-divisible-by-k/)) ### 多步骤哈希优化 * **454. 四数相加 II**([LeetCode](https://leetcode.cn/problems/4sum-ii/)) * **347. 前 K 个高频元素**([LeetCode](https://leetcode.cn/problems/top-k-frequent-elements/)) * **128. 最长连续序列**([LeetCode](https://leetcode.cn/problems/longest-consecutive-sequence/)) --- --- url: /algorithm/data-structure/heap/index.md --- # 堆 ::: info 本篇仅讨论 **二叉堆** ::: ## 概述 \==堆(heap)== 是一种完全二叉树结构,满足以下性质: * **堆序性**:每个节点的值必须满足特定顺序关系 * **最大堆**:父节点值 ≥ 子节点值(根节点最大) * **最小堆**:父节点值 ≤ 子节点值(根节点最小) * **结构完整性**:除最后一层外,其他层节点必须全满,且最后一层节点靠左排列 ## 堆的实现 ### 插入操作 **插入操作** 是指向二叉堆中插入一个元素,要保证插入后也是一棵完全二叉树。 最简单的方法就是,最下一层最右边的叶子之后插入。如果最下一层已满,就新增一层。 插入之后如果不满足堆性质,则采用 **向上调整** : 如果这个节点的权值大于它父节点的权值,就交换,重复此过程直到不满足或者到根。 可以证明,插入之后向上调整后,没有其他接点会不满足堆性质。 **向上调整** 的时间复杂度是 $O(\log n)$ 。 :::center ![插入操作](/images/algorithm/binary-heap-insert.svg) ::: ### 删除操作 **删除操作** 指删除堆中最大的元素,即删除根结点。 但是如果直接删除,则变成了两个堆,难以处理。 所以不妨考虑 **插入操作的逆过程**,设法将根节点移到最后一个结点,然后直接删掉。 然而实际上不好做,我们通常采用的方法是,把根节点和最后一个节点直接交换。 于是直接删掉(在最后一个节点处的)根结点,但是新的根节点可能不满足堆性质。 这时候可以采用 **向下调整** : 在该节点的子节点中,找一个最大的,与该节点交换,重复此过程直到底层。 可以证明,删除并向下调整后,没有其他节点不满足堆性质。 时间复杂度 $O(\log n)$ 。 ### 核心特性 * **数组表示**:堆通常使用数组存储(利用完全二叉树特性) 索引计算(设当前索引为 i): ```ts parentIndex = Math.floor((i - 1) / 2) leftChildIndex = 2 * i + 1 rightChildIndex = 2 * i + 2 ``` ### 最大堆实现 ```ts :collapsed-lines class MaxHeap { private heap: number[] constructor() { this.heap = [] } // 获取父节点索引 private getParentIndex(index: number): number { return Math.floor((index - 1) / 2) } // 获取左子节点索引 private getLeftChildIndex(index: number): number { return 2 * index + 1 } // 获取右子节点索引 private getRightChildIndex(index: number): number { return 2 * index + 2 } // 交换元素 private swap(i: number, j: number): void { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]] } // 上浮操作(插入后维护堆) private siftUp(): void { let currentIndex = this.heap.length - 1 while (currentIndex > 0) { const parentIndex = this.getParentIndex(currentIndex) if (this.heap[currentIndex] > this.heap[parentIndex]) { this.swap(currentIndex, parentIndex) currentIndex = parentIndex } else { break } } } // 下沉操作(删除后维护堆) private siftDown(): void { let currentIndex = 0 const size = this.heap.length while (this.getLeftChildIndex(currentIndex) < size) { const leftChildIndex = this.getLeftChildIndex(currentIndex) const rightChildIndex = this.getRightChildIndex(currentIndex) let largerChildIndex = leftChildIndex // 选择较大的子节点 if (rightChildIndex < size && this.heap[rightChildIndex] > this.heap[leftChildIndex]) { largerChildIndex = rightChildIndex } // 与当前节点比较 if (this.heap[currentIndex] < this.heap[largerChildIndex]) { this.swap(currentIndex, largerChildIndex) currentIndex = largerChildIndex } else { break } } } // 插入元素 insert(value: number): void { this.heap.push(value) this.siftUp() } // 删除并返回堆顶元素 extractMax(): number | null { if (this.heap.length === 0) return null const max = this.heap[0] const last = this.heap.pop()! if (this.heap.length > 0) { this.heap[0] = last this.siftDown() } return max } // 获取堆顶元素(不删除) peek(): number | null { return this.heap[0] ?? null } // 获取堆大小 size(): number { return this.heap.length } // 堆排序(原地排序) static heapSort(arr: number[]): number[] { const heap = new MaxHeap() // 构建堆 for (const num of arr) heap.insert(num) // 依次提取最大值 const sorted: number[] = [] while (heap.size() > 0) { sorted.unshift(heap.extractMax()!) } return sorted } } ``` ### 最小堆实现 最小堆实现进需要在 最大堆 的基础上进行修改,调整比较逻辑: ```ts class MinHeap { private heap: number[] = [] // ...(索引计算和swap方法同MaxHeap) private siftUp() { let index = this.heap.length - 1 while (index > 0) { const parentIndex = this.getParentIndex(index) if (this.heap[index] < this.heap[parentIndex]) { this.swap(index, parentIndex) index = parentIndex } else { break } } } private siftDown() { let index = 0 const length = this.heap.length while (true) { const leftChildIndex = this.getLeftChildIndex(index) const rightChildIndex = this.getRightChildIndex(index) let smallest = index if (leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallest]) { smallest = leftChildIndex } if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallest]) { smallest = rightChildIndex } if (smallest !== index) { this.swap(index, smallest) index = smallest } else { break } } } // 其他方法与MaxHeap类似 } ``` ## 时间复杂度 | 操作 | 时间复杂度 | 说明 | | -------------- | ------------ | ----------------------------- | | `insert()` | $O(log n)$ | 最坏情况下上浮整棵树高度 | | `extractMax()` | $O(log n)$ | 最坏情况下下沉整棵树高度 | | `peek()` | $O(1) $ | 直接访问数组首元素 | | `buildHeap()` | $O(n)$ | Floyd 算法自底向上堆化 | | `heapSort()` | $O(n log n)$ | 每次 extractMax 为 $O(log n)$ | :::warning 注意 虽然单个插入操作是 $O(log n)$ ,但将 n 个元素插入空堆的总体时间复杂度是 $O(n log n)$ ,而 Floyd 建堆算法只需 $O(n)$ 。 ::: ## 适用场景 * **优先队列**: ```ts class PriorityQueue { private heap = new MaxHeap() enqueue(val: number) { this.heap.insert(val) } dequeue() { return this.heap.extractMax() } } ``` * **堆排序**: * 时间复杂度:O(n log n) * 空间复杂度:O(1)(原地排序) ```ts const arr = [4, 10, 3, 5, 1] const sorted = MaxHeap.heapSort(arr) // [1, 3, 4, 5, 10] ``` * **Top K 问题**: ```ts function findTopK(nums: number[], k: number): number[] { const minHeap = new MinHeap() // 最小堆实现类似 for (const num of nums) { minHeap.insert(num) if (minHeap.size() > k) minHeap.extractMin() } return minHeap.toArray() } ``` * **Dijkstra 算法**:优先队列优化最短路径搜索 ## 相关问题 [**LeetCode** - 堆(优先队列)](https://leetcode.cn/problem-list/heap-priority-queue/){.read-more} ### 堆排序与选择问题 * **703. 数据流中的第 K 大元素**([LeetCode](https://leetcode.cn/problems/kth-largest-element-in-a-stream/)) * **215. 数组中的第K个最大元素**([LeetCode](https://leetcode.cn/problems/kth-largest-element-in-an-array/)) * **347. 前 K 个高频元素**([LeetCode](https://leetcode.cn/problems/top-k-frequent-elements/)) ### 多堆结构与复杂规则处理 * **23. 合并 K 个升序链表**([LeetCode](https://leetcode.cn/problems/merge-k-sorted-lists/)) * **295. 数据流的中位数**([LeetCode](https://leetcode.cn/problems/find-median-from-data-stream/)) * **239. 滑动窗口最大值**([LeetCode](https://leetcode.cn/problems/sliding-window-maximum/)) ### 综合场景 * **313. 超级丑数**([LeetCode](https://leetcode.cn/problems/super-ugly-number/)) * **786. 第 K 个最小的素数分数**([LeetCode](https://leetcode.cn/problems/k-th-smallest-prime-fraction/)) * **871. 最低加油次数**([LeetCode](https://leetcode.cn/problems/minimum-number-of-refueling-stops/)) --- --- url: /algorithm/data-structure/linked-list/index.md --- # 链表 ## 概述 链表是一种用于存储数据的数据结构,通过如链条一般的指针来连接元素。 它的特点是插入与删除数据十分方便,但寻找与读取数据的表现欠佳。 ## 核心特性 * **节点(Node)**: * 存储数据(value) * 指向下一个节点的指针(next) * 双向链表额外包含指向前一个节点的指针(prev) * **头指针(Head)**: * 指向链表的第一个节点 * 链表入口点 * **尾节点(Tail)**: * 最后一个节点,其 next 指向 null ## 单向链表 单向链表中包含数据域和指针域,其中数据域用于存放数据,指针域用来连接当前结点和下一节点。 :::center ![linked list](/images/algorithm/linked-list.svg) ::: ### 插入数据 单向链表插入数据的流程大致如下: ::: steps 1. 初始化待插入的数据 node ![insert node](/images/algorithm/linked-list-insert-1.svg) 2. 将 node 的 next 指针指向 p 的下一个结点 ![insert node](/images/algorithm/linked-list-insert-2.svg) 3. 将 p 的 next 指针指向 node ![insert node](/images/algorithm/linked-list-insert-3.svg) ::: 对于 **单向循环链表** ,由于链表首尾相连,在插入数据时需要判断原链表是否为空:为空则自身循环,不为空则正常插入数据。 大致流程如下: 1. 初始化待插入的数据 node; 2. 判断给定链表 p 是否为空; 3. 若为空,则将 node 的 next 指针和 p 都指向自己; 4. 否则,将 node 的 next 指针指向 p 的下一个结点; 5. 将 p 的 next 指针指向 node。 ::: steps * ![insert node](/images/algorithm/linked-list-insert-cyclic-1.svg) * ![insert node](/images/algorithm/linked-list-insert-cyclic-2.svg) * ![insert node](/images/algorithm/linked-list-insert-cyclic-3.svg) ::: ### 删除数据 设待删除结点为 p,从链表中删除它时,将 p 的下一个结点 p->next 的值覆盖给 p 即可,与此同时更新 p 的下下个结点。 流程大致如下: 1. 将 p 下一个结点的值赋给 p,以抹掉 p->value; 2. 新建一个临时结点 t 存放 p->next 的地址; 3. 将 p 的 next 指针指向 p 的下下个结点,以抹掉 p->next; 4. 删除 t。此时虽然原结点 p 的地址还在使用,删除的是原结点 p->next 的地址,但 p 的数据被 p->next 覆盖,p 名存实亡。 **参考**: ::: steps * ![delete node](/images/algorithm/linked-list-delete-1.svg) * ![delete node](/images/algorithm/linked-list-delete-2.svg) * ![delete node](/images/algorithm/linked-list-delete-3.svg) ::: ### 单向链表实现 1. 定义节点类 ```ts class ListNode { value: T next: ListNode | null constructor(value: T) { this.value = value this.next = null } } ``` 2. 定义链表类 ```ts :collapsed-lines class SinglyLinkedList { private head: ListNode | null private size: number constructor() { this.head = null this.size = 0 } // 插入到尾部 (O(n)) append(value: T): void { const newNode = new ListNode(value) if (!this.head) { this.head = newNode } else { let current = this.head while (current.next) { current = current.next } current.next = newNode } this.size++ } // 插入到头部 (O(1)) prepend(value: T): void { const newNode = new ListNode(value) newNode.next = this.head this.head = newNode this.size++ } // 删除节点 (O(n)) delete(value: T): void { if (!this.head) return if (this.head.value === value) { this.head = this.head.next this.size-- return } let current = this.head while (current.next) { if (current.next.value === value) { current.next = current.next.next this.size-- return } current = current.next } } // 查找节点 (O(n)) find(value: T): ListNode | null { let current = this.head while (current) { if (current.value === value) return current current = current.next } return null } // 获取长度 (O(1)) getLength(): number { return this.size } // 转换为数组 (O(n)) toArray(): T[] { const result: T[] = [] let current = this.head while (current) { result.push(current.value) current = current.next } return result } } ``` ## 双向链表 双向链表中同样有数据域和指针域。不同之处在于,指针域有左右(或上一个、下一个)之分,用来连接上一个结点、当前结点、下一个结点。 :::center ![double linked list](/images/algorithm/double-linked-list.svg) ::: ### 插入数据 在向双向(循环)链表插入数据时,除了要判断给定链表是否为空外,还要同时修改左、右两个指针。 大致流程如下: 1. 初始化待插入的数据 node; 2. 判断给定链表 p 是否为空; 3. 若为空,则将 node 的 left 和 right 指针,以及 p 都指向自己; 4. 否则,将 node 的 left 指针指向 p; 5. 将 node 的 right 指针指向 p 的右结点; 6. 将 p 右结点的 left 指针指向 node; 7. 将 p 的 right 指针指向 node。 ### 删除数据 流程大致如下: 1. 将 p 左结点的右指针指向 p 的右节点; 2. 将 p 右结点的左指针指向 p 的左节点; 3. 新建一个临时结点 t 存放 p 的地址; 4. 将 p 的右节点地址赋给 p,以避免 p 变成悬垂指针; 5. 删除 t。 ### 双向链表实现 1. 定义节点类 ```ts class DoublyListNode { value: T next: DoublyListNode | null prev: DoublyListNode | null constructor(value: T) { this.value = value this.next = null this.prev = null } } ``` 2. 定义双向链表类 ```ts :collapsed-lines class DoublyLinkedList { private head: DoublyListNode | null private tail: DoublyListNode | null private size: number constructor() { this.head = null this.tail = null this.size = 0 } // 尾部插入 (O(1)) append(value: T): void { const newNode = new DoublyListNode(value) if (!this.tail) { this.head = newNode this.tail = newNode } else { this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } this.size++ } // 头部插入 (O(1)) prepend(value: T): void { const newNode = new DoublyListNode(value) if (!this.head) { this.head = newNode this.tail = newNode } else { newNode.next = this.head this.head.prev = newNode this.head = newNode } this.size++ } // 删除节点 (O(n)) delete(value: T): void { if (!this.head) return let current: DoublyListNode | null = this.head while (current) { if (current.value === value) { if (current === this.head) { this.head = current.next if (this.head) this.head.prev = null } else if (current === this.tail) { this.tail = current.prev if (this.tail) this.tail.next = null } else { current.prev!.next = current.next current.next!.prev = current.prev } this.size-- return } current = current.next } } } ``` ## 时间复杂度 | 操作 | 单向链表 | 双向链表 | | -------- | -------- | -------- | | 插入头部 | $O(1)$ | $O(1)$ | | 插入尾部 | $O(n)$ | $O(1)$ | | 删除头部 | $O(1)$ | $O(1)$ | | 删除尾部 | $O(n)$ | $O(1)$ | | 随机访问 | $O(n)$ | $O(n)$ | | 查找元素 | $O(n)$ | $O(n)$ | ## 与数组的区别 链表和数组都可用于存储数据。与链表不同,数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势: * 链表因其链状的结构,能方便地删除、插入数据,操作次数是 $O(1)$ 。 但也因为这样,寻找、读取数据的效率不如数组高,在随机访问数据中的操作次数是 $O(n)$ 。 * 数组可以方便地寻找并读取数据,在随机访问中操作次数是 $O(1)$ 。但删除、插入的操作次数是 $O(n)$ 次。 | 特性 | 链表 | 数组 | | ------------- | ------------------ | ----------------- | | 内存分配 | 动态分配(非连续) | 静态/连续内存 | | 插入/删除效率 | $O(1)$ 在已知位置 | $O(n)$ 需移动元素 | | 随机访问 | $O(n)$ 需要遍历 | $O(1)$ 通过索引 | | 内存开销 | 额外存储指针 | 无额外开销 | | 缓存友好度 | 差(内存不连续) | 好(局部性原理) | ## 应用场景 * **实现栈/队列**: ```ts // 基于链表的队列 class Queue { private list = new SinglyLinkedList() enqueue(value: T) { this.list.append(value) } dequeue(): T | undefined { /* ... */ } } ``` * **LRU缓存淘汰算法**: 使用双向链表 + HashMap 实现 O(1) 的插入/删除 * **大文件处理**: 避免数组连续内存限制,分段处理数据 * **撤销操作历史记录**: 双向链表实现前进/后退功能 ## 链表使用技巧 * **虚拟头节点**: ```ts // 简化边界处理 const dummyHead = new ListNode(0) dummyHead.next = head // ...操作后返回 dummyHead.next ``` * **快慢指针**: ```ts // 检测环/找中点 let slow = head let fast = head while (fast && fast.next) { slow = slow.next! fast = fast.next.next! } ``` * **反转链表**: ```ts function reverseList(head: ListNode | null): ListNode | null { let prev = null let current = head while (current) { const next = current.next current.next = prev prev = current current = next } return prev } ``` ## 相关问题 [**LeetCode** - 链表](https://leetcode.cn/problem-list/linked-list/){.read-more} ### 基础操作 * **206. 反转链表**([LeetCode](https://leetcode.cn/problems/reverse-linked-list/)) * **21. 合并两个有序链表**([LeetCode](https://leetcode.cn/problems/merge-two-sorted-lists/)) * **83. 删除排序链表中的重复元素**([LeetCode](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/)) * **203. 移除链表元素**([LeetCode](https://leetcode.cn/problems/remove-linked-list-elements/)) ### 双指针技巧 * **141. 环形链表**([LeetCode](https://leetcode.cn/problems/linked-list-cycle/)) * **19. 删除链表的倒数第 N 个结点**([LeetCode](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)) * **876. 链表的中间结点**([LeetCode](https://leetcode.cn/problems/middle-of-the-linked-list/)) ### 递归与归并 * **24. 两两交换链表中的节点**([LeetCode](https://leetcode.cn/problems/swap-nodes-in-pairs/)) * **23. 合并 K 个升序链表**([LeetCode](https://leetcode.cn/problems/merge-k-sorted-lists/)) * **148. 排序链表**([LeetCode](https://leetcode.cn/problems/sort-list/)) ### 其它 * **138. 复制带随机指针的链表**([LeetCode](https://leetcode.cn/problems/copy-list-with-random-pointer/)) * **234. 回文链表**([LeetCode](https://leetcode.cn/problems/palindrome-linked-list/)) * **143. 重排链表**([LeetCode](https://leetcode.cn/problems/reorder-list/)) --- --- url: /algorithm/data-structure/overview/index.md --- # 介绍 数据结构是在计算机中存储、组织数据的方式。小到变量、数组,大到线段树、平衡树,都是数据结构。 程序运行离不开数据结构,不同的数据结构又各有优劣,能够处理的问题各不相同,而根据具体问题选取合适的数据结构, 可以大大提升程序的效率。 一般你可以从两个维度来理解它,逻辑结构和存储结构。 ## 逻辑结构 逻辑结构指数据之间的关系,逻辑结构大概统一的可以分成两种:线性结构、非线性结构。 * **线性结构** 一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。 常用的线性结构有: 栈,队列,链表,线性表。 ```mermaid block-beta A B C D E F G H ``` * **非线性结构** 各个数据元素不再保持在一个线性序列中,每个数据元素可能与零个或者多个其他数据元素发生联系。 常见的非线性结构有 二维数组,树等。 ```mermaid flowchart TD A --> B A --> C B --> D B --> E C --> F C --> G ``` ## 存储结构 逻辑结构指的是数据间的关系,而存储结构是逻辑结构用计算机语言的实现。 常见的存储结构有顺序存储、链式存储、索引存储以及散列存储。 例如: * 数组在内存中的位置是连续的,它就属于顺序存储; * 链表是主动建立数据间的关联关系的,在内存中却不一定是连续的,它属于链式存储; * 还有顺序和逻辑上都不存在顺序关系,但是你可以通过一定的方式去放问它的哈希表,数据散列存储。 --- --- url: /algorithm/data-structure/queue/index.md --- # 队列 ## 概述 \==队列(Queue)== 是一种 先进先出(FIFO: First-In-First-Out) 的线性数据结构,类似于现实生活中的排队场景。 在队列中,元素从一端(队尾)添加,从另一端(队首)移除。 :::center ![stack](/images/algorithm/queue.svg) ::: ::: tip 提示 当我们在排队买票时,排在队首的人先买票,然后离开队伍。 新来的人需要排到队伍尾部,等待前面的人买完票再轮到他。 ::: ## 核心特性 * **操作受限**:只允许在两端操作 * **先进先出**:最早入队的元素最先出队 * **动态大小**:长度随操作变化(非固定容量) ## 时间复杂度 | 操作 | 描述 | TypeScript 实现示例 | |-------------|------------------------|----------------------------| | `enqueue()` | 元素入队(添加到队尾) | `queue.push(item)` | | `dequeue()` | 元素出队(移除队首元素)| `queue.shift()` | | `peek()` | 查看队首元素(不移除) | `queue[0]` | | `isEmpty()` | 检查队列是否为空 | `queue.length === 0` | | `size()` | 获取队列长度 | `queue.length` | ## 队列的实现 ### 数组实现 **注意**:`shift()` 操作需要移动所有元素(时间复杂度 O(n)) ```ts class ArrayQueue { private items: T[] = [] enqueue(item: T): void { this.items.push(item) } dequeue(): T | undefined { return this.items.shift() } peek(): T | undefined { return this.items[0] } get size(): number { return this.items.length } isEmpty(): boolean { return this.items.length === 0 } clear(): void { this.items = [] } } ``` ### 链表实现 所有操作时间复杂度均为 O(1) ```ts class QueueNode { constructor( public value: T, public next: QueueNode | null = null ) {} } class LinkedListQueue { private front: QueueNode | null = null private rear: QueueNode | null = null private _size = 0 enqueue(item: T): void { const newNode = new QueueNode(item) if (this.isEmpty()) { this.front = newNode } else { this.rear!.next = newNode } this.rear = newNode this._size++ } dequeue(): T | undefined { if (this.isEmpty()) return undefined const removed = this.front! this.front = this.front!.next this._size-- if (this.isEmpty()) this.rear = null return removed.value } peek(): T | undefined { return this.front?.value } get size(): number { return this._size } isEmpty(): boolean { return this._size === 0 } clear(): void { this.front = null this.rear = null this._size = 0 } } ``` ### 循环队列实现 解决数组实现的性能问题,使用环形缓冲区,适用于 **固定容量优化** 的场景 ```ts class CircularQueue { private items: (T | undefined)[] private front = 0 private rear = -1 private count = 0 constructor(private capacity: number) { this.items = Array.from({ length: capacity }) } enqueue(item: T): boolean { if (this.isFull()) return false this.rear = (this.rear + 1) % this.capacity this.items[this.rear] = item this.count++ return true } dequeue(): T | undefined { if (this.isEmpty()) return undefined const item = this.items[this.front] this.front = (this.front + 1) % this.capacity this.count-- return item } peek(): T | undefined { return this.isEmpty() ? undefined : this.items[this.front] } isFull(): boolean { return this.count === this.capacity } isEmpty(): boolean { return this.count === 0 } get size(): number { return this.count } } ``` ## 应用场景 * **任务调度**:CPU 进程调度、打印机任务队列 * **广度优先搜索**:树/图的层级遍历 * **消息传递**:消息队列(RabbitMQ/Kafka) * **缓冲区管理**:网络数据包处理 * **撤销操作栈**:编辑器中的撤销历史记录 ## 复杂度对比 | 操作 | 数组实现 | 链表实现 | 循环队列 | |-------------|----------|----------|----------| | **enqueue** | O(1)\* | O(1) | O(1) | | **dequeue** | O(n) | O(1) | O(1) | | **peek** | O(1) | O(1) | O(1) | | **空间** | O(n) | O(n) | O(n) | ::: warning 注:数组的 push() 平均 O(1),但动态扩容时可能 O(n) ::: ## 相关问题 [**LeetCode** - 队列](https://leetcode.cn/problem-list/queue/){.read-more} ### 基础操作 * **232. 用栈实现队列**([LeetCode](https://leetcode.cn/problems/implement-queue-using-stacks/)) * **622. 设计循环队列**([LeetCode](https://leetcode.cn/problems/design-circular-queue/)) ### 广度优先搜索 (BFS) * **102. 二叉树的层序遍历**([LeetCode](https://leetcode.cn/problems/binary-tree-level-order-traversal/)) * **752. 打开转盘锁**([LeetCode](https://leetcode.cn/problems/open-the-lock/)) * **994. 腐烂的橘子**([LeetCode](https://leetcode.cn/problems/rotting-oranges/)) ### 单调队列 * **239. 滑动窗口最大值**([LeetCode](https://leetcode.cn/problems/sliding-window-maximum/)) * **862. 和至少为 K 的最短子数组**([LeetCode](https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/)) --- --- url: /algorithm/data-structure/stack/index.md --- # 栈 ## 概述 \==栈== 是一种遵循 **后进先出(LIFO) 原则** 的线性数据结构,类似于现实中的一摞盘子或书籍。 ::: center ![stack](/images/algorithm/stack.svg) ::: ::: tip 提示 想象一下,我们把盘子从上到下依次摆放在桌子上,当我们要用到盘子时,就从最上面取走一个盘子, 放回盘子时,则是把盘子放在最上面。 ::: ## 核心特性 * **后进先出(LIFO)**:最后添加的元素最先被移除 * **单端操作**:所有操作(插入/删除/访问)仅在栈顶(Top)进行 ## 时间复杂度 * **压栈(Push)**: O(1) * **弹栈(Pop)**: O(1) * **查看栈顶(Peek)**: O(1) ## 栈的实现 ### 使用数组模拟栈 ```ts class ArrayStack { private items: T[] constructor() { this.items = [] } // 压栈 push(element: T): void { this.items.push(element) } // 弹栈 pop(): T | undefined { return this.items.pop() } // 查看栈顶元素 peek(): T | undefined { return this.items[this.items.length - 1] } // 判断空栈 isEmpty(): boolean { return this.items.length === 0 } // 获取栈大小 size(): number { return this.items.length } // 清空栈 clear(): void { this.items = [] } // 打印栈内容 print(): string { return this.items.toString() } } ``` ### 使用链表模拟栈 ```ts class LinkedNode { constructor( public value: T, public next: LinkedNode | null = null ) {} } class LinkedListStack { private top: LinkedNode | null = null private count: number = 0 push(element: T): void { const newNode = new LinkedNode(element) newNode.next = this.top this.top = newNode this.count++ } pop(): T | undefined { if (!this.top) return undefined const value = this.top.value this.top = this.top.next this.count-- return value } peek(): T | undefined { return this.top?.value } isEmpty(): boolean { return this.count === 0 } size(): number { return this.count } clear(): void { this.top = null this.count = 0 } } ``` ## 应用场景 * **函数调用栈**(程序执行上下文管理) * **括号匹配校验**(编译器语法检查) * **撤销操作(Undo)**(编辑器历史记录) * **深度优先搜索(DFS)**(图遍历算法) * **表达式求值**(中缀转后缀表达式) * **浏览器历史记录**(前进/后退功能) ::: important 掌握 **栈** 的关键在于理解其 **LIFO 特性** 和 **受限的操作方式**, 这种特性使其在需要"撤销"或"回溯"的场景中具有天然优势。 ::: ## 相关题目 [**LeetCode** - 栈](https://leetcode.cn/problem-list/stack/){.read-more} ### 基础操作 * **20. 有效的括号**([LeetCode](https://leetcode.cn/problems/valid-parentheses/)) * **225. 用队列实现栈**([LeetCode](https://leetcode.cn/problems/implement-stack-using-queues/)) * **155. 最小栈**([LeetCode](https://leetcode.cn/problems/min-stack/)) ### 表达式求值 * **150. 逆波兰表达式求值**([LeetCode](https://leetcode.cn/problems/evaluate-reverse-polish-notation/)) * **227. 基本计算器 II**([LeetCode](https://leetcode.cn/problems/basic-calculator-ii/)) ### 单调栈 * **496. 下一个更大元素 I**([LeetCode](https://leetcode.cn/problems/next-greater-element-i/)) * **503. 下一个更大元素 II**([LeetCode](https://leetcode.cn/problems/next-greater-element-ii/)) * **739. 每日温度**([LeetCode](https://leetcode.cn/problems/daily-temperatures/)) * **42. 接雨水**([LeetCode](https://leetcode.cn/problems/trapping-rain-water/)) ### 深度优先搜索(DFS) * **94. 二叉树的中序遍历**([LeetCode](https://leetcode.cn/problems/binary-tree-inorder-traversal/)) * **144. 二叉树的前序遍历**([LeetCode](https://leetcode.cn/problems/binary-tree-preorder-traversal/)) * **341. 扁平化嵌套列表迭代器**([LeetCode](https://leetcode.cn/problems/flatten-nested-list-iterator/)) ### 特殊栈应用 * **316. 去除重复字母**([LeetCode](https://leetcode.cn/problems/remove-duplicate-letters/)) * **394. 字符串解码**([LeetCode](https://leetcode.cn/problems/decode-string/)) * **456. 132 模式**([LeetCode](https://leetcode.cn/problems/132-pattern/)) --- --- url: /algorithm/depth-first-search/index.md --- # 深度优先搜索 ## 概述 \==深度优先搜索(Depth-First Search)(DFS)== 是一种用于遍历或搜索树或图的算法。 其核心思想是尽可能深地探索分支,直到达到末端,然后回溯并探索其他分支。 ::: note 该算法常常与 BFS 并列,但两者除了都能遍历图的连通块以外,用途完全不同,很少有能混用两种算法的情况。 ::: ## 过程 DFS 最显著的特征在于其 **递归调用自身**。 同时与 BFS 类似,DFS 会对其访问过的点打上访问标记,在遍历图时跳过已打过标记的点,以确保 **每个点仅访问一次** 。 符合以上两条规则的函数,便是广义上的 DFS。 具体地说,DFS 大致结构如下: ```txt title="伪代码" DFS(v) // v 可以是图中的一个顶点,也可以是抽象的概念,如 dp 状态等。 在 v 上打访问标记 for u in v 的相邻节点 if u 没有打过访问标记 then DFS(u) end end end ``` ## 核心原理 * **深度优先**:从起始节点开始,沿一条路径不断深入直到末端,再回溯探索其他路径。 * **递归/栈结构**:天然适合递归实现(隐式栈),也可用显式栈迭代实现。 * **回溯机制**:当节点无未访问邻居时,回退到上一个节点。 * **避免重复访问**:需记录已访问节点(通常用 Set 或数组)。 ## 复杂度分析 该算法通常的时间复杂度为 $O(n+m)$,空间复杂度为 $O(n)$,其中 $n$ 表示点数,$m$ 表示边数。 注意空间复杂度包含了栈空间,栈空间的空间复杂度是 $O(n)$ 的。 在平均 $O(1)$ 遍历一条边的条件下才能达到此时间复杂度,例如用前向星或邻接表存储图; 如果用邻接矩阵则不一定能达到此复杂度。 ## 实现方式 ### 递归实现 ```ts type Graph = Record function dfsRecursive( graph: Graph, node: string, visited: Set = new Set() ): void { // 1. 访问当前节点 console.log(node) visited.add(node) // 2. 递归访问所有未访问的邻居 for (const neighbor of graph[node] || []) { if (!visited.has(neighbor)) { dfsRecursive(graph, neighbor, visited) } } } ``` ### 迭代实现(显式栈) ```ts function dfsIterative(graph: Graph, start: string): void { const stack: string[] = [start] const visited = new Set() while (stack.length > 0) { const node = stack.pop()! // 从栈顶弹出节点 if (visited.has(node)) continue // 访问节点 console.log(node) visited.add(node) // 将邻居逆序入栈(保持与递归相同顺序) const neighbors = graph[node] || [] for (let i = neighbors.length - 1; i >= 0; i--) { if (!visited.has(neighbors[i])) { stack.push(neighbors[i]) } } } } ``` ## 注意事项 * **栈溢出**:深度过大时递归可能导致栈溢出,可改用迭代法。 * **环检测**:在递归中若遇到已访问节点且非父节点,说明存在环。 * **非连通图**:需遍历所有未访问节点作为新起点。 ## 相关题目 [**LeetCode** - 深度优先搜索 Depth-First Search](https://leetcode.cn/problem-list/depth-first-search/){.read-more} ### 矩阵遍历类(二维网格DFS) * **200. 岛屿数量**([LeetCode](https://leetcode.cn/problems/number-of-islands/)) * **417. 太平洋大西洋水流问题**([LeetCode](https://leetcode.cn/problems/pacific-atlantic-water-flow/)) * **LCR 129. 字符迷宫** ([LeetCode](https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/)) ### 树与图遍历类(递归/隐式栈) * **1038. 从二叉搜索树到更大树**([LeetCode](https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/)) * **100. 相同的树**([LeetCode](https://leetcode.cn/problems/same-tree/)) * **105. 从前序与中序遍历序列构造二叉树**([LeetCode](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)) ### 回溯与组合类(路径/状态管理) * **39. 组合总和**([LeetCode](https://leetcode.cn/problems/combination-sum/)) * **40. 组合总和 II**([LeetCode](https://leetcode.cn/problems/combination-sum-ii/)) * **LCP 07. 传递信息** ([LeetCode](https://leetcode.cn/problems/chuan-di-xin-xi/)) ### 进阶挑战题 * **79. 单词搜索**([LeetCode](https://leetcode.cn/problems/word-search/)) * **301. 删除无效的括号**([LeetCode](https://leetcode.cn/problems/remove-invalid-parentheses/)) * **694. 不同的岛屿数量**([LeetCode](https://leetcode.cn/problems/number-of-distinct-islands/)) --- --- url: /algorithm/divide-and-conquer/index.md --- # 分治算法 ## 概述 \==分治算法(Divide and Conquer)== , 字面上的解释是「分而治之」。 把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 **核心流程包含三步**: * **分解(Divide)**:将原问题拆分为独立子问题 * **解决(Conquer)**:递归求解子问题 * **合并(Combine)**:将子问题的解合并为原问题的解 ## 算法特征 * 该问题的规模缩小到一定的程度就可以容易地解决。 * 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质,利用该问题分解出的子问题的解可以合并为该问题的解。 * 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 ::: warning 如果各子问题是不独立的,则分治法要重复地解公共的子问题,也就做了许多不必要的工作。 此时虽然也可用分治法,但一般用 ==动态规划== 较好。 ::: ## 过程 以归并排序为例。 假设实现归并排序的函数名为 `mergeSort`。明确该函数的职责,即 **对传入的一个数组排序**。 这个问题显然可以分解。给一个数组排序等于给该数组的左右两半分别排序,然后合并成一个数组。 ```ts function mergeSort(一个数组) { if (可以很容易处理) return mergeSort(左半个数组) mergeSort(右半个数组) merge(左半个数组, 右半个数组) } ``` 传给它半个数组,那么处理完后这半个数组就已经被排好了。 注意到,`mergeSort` 与二叉树的后序遍历模板极其相似。 因为分治算法的套路是 **分解 -> 解决(触底)-> 合并(回溯)**,先左右分解,再处理合并,回溯就是在退栈,即相当于后序遍历。 `merge` 函数的实现方式与两个有序链表的合并一致。 ## 分治示例 ### 归并排序(经典分治) * **时间复杂度**:$O(n log n)$ * **空间复杂度**:$O(n)$ ```ts function mergeSort(arr: number[]): number[] { if (arr.length <= 1) return arr // 终止条件 // 分解阶段 const mid = Math.floor(arr.length / 2) const left = mergeSort(arr.slice(0, mid)) const right = mergeSort(arr.slice(mid)) // 合并阶段 return merge(left, right) } function merge(left: number[], right: number[]): number[] { let result: number[] = [] let i = 0 let j = 0 // 合并两个有序数组 while (i < left.length && j < right.length) { if (left[i] < right[j]) { result.push(left[i++]) } else { result.push(right[j++]) } } // 处理剩余元素 return result.concat(left.slice(i)).concat(right.slice(j)) } // 测试 const arr = [38, 27, 43, 3, 9, 82, 10] console.log(mergeSort(arr)) // [3, 9, 10, 27, 38, 43, 82] ``` ## 分治算法优化技巧 * **避免重复计算**:使用记忆化存储中间结果 * **尾递归优化**:减少递归栈深度 * **迭代替代递归**:降低空间复杂度 * **并行计算**:子问题独立时可并行处理 ## 适用场景 * 问题可分解为独立子问题(归并排序、快速排序) * 子问题结构相似(二叉树遍历) * 合并操作复杂度低于暴力求解(矩阵乘法) * 问题具有递归特性(汉诺塔、斐波那契数列) ## 相关问题 [**LeetCode** - 分治](https://leetcode.cn/tag/divide-and-conquer/){.read-more} ### 基础分治应用 * **169. 多数元素**([LeetCode](https://leetcode.cn/problems/majority-element/)) * **50. Pow(x, n)**([LeetCode](https://leetcode.cn/problems/powx-n/)) ### 子问题合并技巧 * **53. 最大子序和**([LeetCode](https://leetcode.cn/problems/maximum-subarray/)) * **493. 翻转对**([LeetCode](https://leetcode.cn/problems/reverse-pairs/)) ### 分治优化:三路划分 * **215. 数组中的第K个最大元素**([LeetCode](https://leetcode.cn/problems/kth-largest-element-in-an-array/)) * **75. 颜色分类**([LeetCode](https://leetcode.cn/problems/sort-colors/)) ### 进阶问题 * **4. 寻找两个有序数组的中位数**([LeetCode](https://leetcode.cn/problems/median-of-two-sorted-arrays/)) --- --- url: /algorithm/dynamic-programming/index.md --- # 动态规划 ::: important **动态规划** 学习需要长时间的练习和强化,此篇目前仅处于 ==草稿=={.warning} 状态,在未来会引入更多的 DP 问题进行更为深入的学习。 ::: ## 概述 \==动态规划(Dynamic Programming== 一种 **通过将复杂问题分解为重叠子问题,并存储子问题解以避免重复计算的优化技术**。 它适用于具有 **最优子结构** 和 **重叠子问题** 特性的问题。 ## 动态规划原理 能用动态规划解决的问题,需要满足三个条件:**最优子结构** ,**无后效性** 和 **子问题重叠** 。 ### 最优子结构 具有最优子结构也可能是适合用贪心的方法求解。 注意要确保我们考察了最优解中用到的所有子问题。 1. 证明问题最优解的第一个组成部分是做出一个选择; 2. 对于一个给定问题,在其可能的第一步选择中,假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择; 3. 给定可获得的最优解的选择后,确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间; 4. 证明作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解。方法是反证法,考虑加入某个子问题的解不是其自身的最优解,那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解,从而得到原问题的一个更优的解,从而与原问题最优解的假设矛盾。 要保持子问题空间尽量简单,只在必要时扩展。 最优子结构的不同体现在两个方面: 1. 原问题的最优解中涉及多少个子问题; 2. 确定最优解使用哪些子问题时,需要考察多少种选择。 子问题图中每个定点对应一个子问题,而需要考察的选择对应关联至子问题顶点的边。 ### 无后效性 已经求解的子问题,不会再受到后续决策的影响。 ### 子问题重叠 如果有大量的重叠子问题,我们可以用空间将这些子问题的解存储下来,避免重复求解相同的子问题,从而提升效率。 ### 基本思路 对于一个能用动态规划解决的问题,一般采用如下思路解决: 1. 将原问题划分为若干 **阶段**,每个阶段对应若干个子问题,提取这些子问题的特征(称之为 **状态**); 2. 寻找每一个状态的可能 **决策**,或者说是各状态间的相互转移方式(用数学的语言描述就是 **状态转移方程**)。 3. 按顺序求解每一个阶段的问题。 ## 示例 ### 斐波那契数列(基础入门) ```ts // 自底向上(迭代) function fib(n: number): number { if (n < 2) return n const dp: number[] = [0, 1] for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] } return dp[n] } // 空间优化(滚动数组) function fibOpt(n: number): number { if (n < 2) return n let prev = 0 let curr = 1 for (let i = 2; i <= n; i++) { [prev, curr] = [curr, prev + curr] } return curr } ``` ### 背包问题(0-1 Knapsack) :::info 有 $n$ 个物品和一个容量为 $W$ 的背包,每个物品有重量 $w\_{i}$ 和价值 $v\_{i}$ 两种属性,要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。 ::: ```ts function knapSack( capacity: number, // 背包的最大容量 weights: number[], // 每个物品的重量 values: number[], // 每个物品的价值 n: number // 物品个数 ): number { // dp[i][w] 表示前i个物品在容量w时的最大价值 const dp: number[][] = Array.from({ length: n + 1 }) .fill(0) .map(() => Array.from({ length: capacity + 1 }).fill(0)) for (let i = 1; i <= n; i++) { for (let w = 1; w <= capacity; w++) { if (weights[i - 1] <= w) { dp[i][w] = Math.max( values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w] ) } else { dp[i][w] = dp[i - 1][w] } } } return dp[n][capacity] } // 使用示例 const values = [60, 100, 120] const weights = [10, 20, 30] const capacity = 50 console.log(knapSack(capacity, weights, values, values.length)) // 220 ``` ### 最长公共子序列(LCS) :::info 给定一个长度为 $n$ 的序列 $A$ 和一个 长度为 $m$ 的序列 $B \text{(}n,m \leq 5000\text{)}$,求出一个最长的序列,使得该序列既是 $A$ 的子序列,也是 $B$ 的子序列。 ::: ```ts function lcs(text1: string, text2: string): number { const m = text1.length const n = text2.length // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度 const dp: number[][] = Array.from({ length: m + 1 }) .fill(0) .map(() => Array.from({ length: n + 1 }).fill(0)) for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i - 1] === text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) } } } return dp[m][n] } ``` ## 记忆化搜索 \==记忆化搜索== 是一种通过记录已经遍历过的状态的信息,从而避免对同一状态重复遍历的搜索实现方式。 因为记忆化搜索确保了每个状态只访问一次,它也是一种常见的动态规划实现方式。 ```ts const memo: number[] = [] function fib(n: number): number { if (n < 2) return n if (memo[n] !== undefined) return memo[n] memo[n] = fib(n - 1) + fib(n - 2) return memo[n] } ``` ## 相关问题 [**LeetCode** - 动态规划](https://leetcode.cn/problem-list/dynamic-programming/){.read-more} ### 基础 * **70. 爬楼梯**([LeetCode](https://leetcode.cn/problems/climbing-stairs/)) * **509. 斐波那契数列**([LeetCode](https://leetcode.cn/problems/fibonacci-number/)) * **LCR 127. 跳跃训练**([LeetCode](https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof)) * **118. 杨辉三角**([LeetCode](https://leetcode.cn/problems/pascals-triangle/)) * **198. 打家劫舍**([LeetCode](https://leetcode.cn/problems/house-robber/)) * **53. 最大子序和**([LeetCode](https://leetcode.cn/problems/maximum-subarray/)) ### 二维DP (路径、序列) * **62. 不同路径**([LeetCode](https://leetcode.cn/problems/unique-paths/)) * **63. 不同路径 II**([LeetCode](https://leetcode.cn/problems/unique-paths-ii/)) * **64. 最小路径和**([LeetCode](https://leetcode.cn/problems/minimum-path-sum/)) * **1143. 最长公共子序列**([LeetCode](https://leetcode.cn/problems/longest-common-subsequence/)) * **72. 编辑距离**([LeetCode](https://leetcode.cn/problems/edit-distance/)) * **5. 最长回文子串**([LeetCode](https://leetcode.cn/problems/longest-palindromic-substring/)) * **300. 最长递增子序列**([LeetCode](https://leetcode.cn/problems/longest-increasing-subsequence/)) ### 背包问题 (组合优化) * **416. 分割等和子集**([LeetCode](https://leetcode.cn/problems/partition-equal-subset-sum/)) * **322. 零钱兑换**([LeetCode](https://leetcode.cn/problems/coin-change/)) * **518. 零钱兑换 II**([LeetCode](https://leetcode.cn/problems/coin-change-2/)) * **139. 单词拆分**([LeetCode](https://leetcode.cn/problems/word-break/)) ### 状态机DP (复杂状态转移) * **121. 买卖股票的最佳时机**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/)) * **122. 买卖股票的最佳时机 II**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)) * **123. 买卖股票的最佳时机 III**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/)) * **188. 买卖股票的最佳时机 IV**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/)) * **309. 最佳买卖股票时机含冷冻期**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/)) * **714. 最佳买卖股票时机含手续费**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)) ### 其他经典问题 * **322. 零钱兑换**([LeetCode](https://leetcode.cn/problems/coin-change/)) * **96. 不同的二叉搜索树**([LeetCode](https://leetcode.cn/problems/unique-binary-search-trees/)) * **211. 添加与搜索单词**([LeetCode](https://leetcode.cn/problems/add-and-search-word-data-structure-design/)) * **337. 打家劫舍 III**([LeetCode](https://leetcode.cn/problems/house-robber-iii/)) --- --- url: /algorithm/greedy/index.md --- # 贪心算法 ## 概述 \==贪心算法(Greedy Algorithm)== 是用计算机来模拟一个 **贪心** 的人做出决策的过程。 这个人十分贪婪,每一步行动总是按某种指标选取最优的操作。而且他目光短浅,总是只看眼前,并不考虑以后可能造成的影响。 可想而知,并不是所有的时候贪心法都能获得最优解,所以一般使用贪心法的时候,都要确保自己能证明其正确性。 ### 适用范围 贪心算法在 **有最优子结构的问题** 中尤为有效。 最优子结构的意思是 **问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解** 。 ### 证明 贪心算法有两种证明方法:反证法和归纳法。一般情况下,一道题只会用到其中的一种方法来证明。 * **反证法**:如果交换方案中任意两个元素/相邻的两个元素后,答案不会变得更好,那么可以推定目前的解已经是最优解了。 * **归纳法**:先算得出边界情况(例如 $n = 1$ )的最优解 $F\_{1}$, 然后再证明:对于每个 $n$,$F\_{n+1}$ 都可以由 $F\_{n}$ 推导出结果。 ## 核心特点 * **局部最优 → 全局最优**:通过局部最优决策的累积达到全局最优 * **不可回溯**:一旦做出选择不再改变 * **高效性**:通常时间复杂度较低 * **不保证全局最优**:仅适用于特定问题类型 ## 设计步骤 * **建立数学模型**:明确优化目标 * **分解子问题**:将问题分解为多个决策阶段 * **制定贪心策略**:确定局部最优的选择标准 * **证明正确性**:验证问题具有贪心选择性质 * **实现算法**:编写高效代码实现 ## 示例 ### 找零问题 用最少硬币数凑出指定金额(假设硬币无限供应) ```ts function minCoins(coins: number[], amount: number): number { coins.sort((a, b) => b - a) // 降序排列 let count = 0 let remaining = amount for (const coin of coins) { while (remaining >= coin) { remaining -= coin count++ } if (remaining === 0) break } return remaining === 0 ? count : -1 } // 测试 const coins = [1, 2, 5, 10, 20] console.log(minCoins(coins, 36)) // 输出:3 (20+10+5+1) ``` ### 活动选择问题 在竞争活动中选择最大兼容活动子集 ```ts interface Activity { start: number end: number } function selectActivities(activities: Activity[]): Activity[] { activities.sort((a, b) => a.end - b.end) // 按结束时间排序 const selected: Activity[] = [activities[0]] let lastEnd = activities[0].end for (let i = 1; i < activities.length; i++) { if (activities[i].start >= lastEnd) { selected.push(activities[i]) lastEnd = activities[i].end } } return selected } // 测试 const activities: Activity[] = [ { start: 1, end: 4 }, { start: 3, end: 5 }, { start: 0, end: 6 }, { start: 5, end: 7 }, { start: 8, end: 9 } ] console.log(selectActivities(activities)) // 输出:[ {start:1, end:4}, {start:5, end:7}, {start:8, end:9} ] ``` ## 局限性 * **非全局最优**:如0-1背包问题无法使用贪心 * **证明困难**:需要严格数学证明正确性 * **策略敏感**:排序方式直接影响结果 ## 区别 ### 与动态规划的区别 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。 动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。 ## 相关问题 [**LeetCode** - 贪心算法](https://leetcode.cn/problem-list/greedy/){.read-more} ### 基础(掌握贪心选择策略) * **455. 分发饼干**([LeetCode](https://leetcode.cn/problems/assign-cookies/)) * **860. 柠檬水找零**([LeetCode](https://leetcode.cn/problems/lemonade-change/)) * **122. 买卖股票的最佳时机 II**([LeetCode](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)) ### 进阶(区间处理与路径选择) * **435. 无重叠区间**([LeetCode](https://leetcode.cn/problems/non-overlapping-intervals/)) * **452. 用最少数量的箭引爆气球**([LeetCode](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/)) * **55. 跳跃游戏**([LeetCode](https://leetcode.cn/problems/jump-game/)) * **45. 跳跃游戏 II**([LeetCode](https://leetcode.cn/problems/jump-game-ii/)) ### 挑战 (多维度贪心策略) * **135. 分发糖果**([LeetCode](https://leetcode.cn/problems/candy/)) * **406. 根据身高重建队列**([LeetCode](https://leetcode.cn/problems/queue-reconstruction-by-height/)) * **765. 情侣牵手**([LeetCode](https://leetcode.cn/problems/couples-holding-hands/)) --- --- url: /algorithm/heap-sort/index.md --- # 堆排序 ## 概述 \==堆排序(Heap Sort)== 是一种基于 **二叉堆** 数据结构的高效排序算法。 ## 核心思想 * **构建最大堆(Max-Heap)**:将无序数组转换为满足堆性质的结构(父节点 ≥ 子节点)。 * **反复提取最大值**:将堆顶(最大值)与末尾元素交换,缩小堆范围,重新调整堆。 * **重复调整**:直到堆大小为1,数组即有序。 ## 时间复杂度 堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 $O(n\log n)$。 ## 空间复杂度 由于可以在输入数组上建立堆,所以这是一个原地算法。 ## 稳定性 同选择排序一样,由于其中交换位置的操作,所以是不稳定的排序算法。 ## 实现 ```ts function heapSort(arr: number[]): number[] { const n = arr.length // 构建最大堆(从最后一个非叶子节点开始) for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i) } // 逐个提取最大值并调整堆 for (let i = n - 1; i > 0; i--) { // 交换堆顶(最大值)与当前末尾元素 [arr[0], arr[i]] = [arr[i], arr[0]] // 调整剩余元素为最大堆 heapify(arr, i, 0) } return arr } // 堆调整函数(确保以i为根的子树满足最大堆性质) function heapify(arr: number[], heapSize: number, i: number): void { let largest = i // 初始化最大元素为根节点 const left = 2 * i + 1 // 左子节点索引 const right = 2 * i + 2 // 右子节点索引 // 若左子节点大于根,更新最大值索引 if (left < heapSize && arr[left] > arr[largest]) { largest = left } // 若右子节点大于当前最大值,更新最大值索引 if (right < heapSize && arr[right] > arr[largest]) { largest = right } // 如果最大值不是根节点,则交换并递归调整 if (largest !== i) { [arr[i], arr[largest]] = [arr[largest], arr[i]] heapify(arr, heapSize, largest) // 递归调整受影响子树 } } // 测试示例 const array = [12, 11, 13, 5, 6, 7] console.log('排序前:', array) console.log('排序后:', heapSort(array)) ``` ### 执行示例(`[12, 11, 13, 5, 6, 7]`) * `构建堆`: ```txt [13, 11, 12, 5, 6, 7] // 初始堆 ``` * **首轮交换**:13(堆顶)与 7(末尾)交换 → `[7, 11, 12, 5, 6, 13]` 调整堆:`[12, 11, 7, 5, 6]` → 新堆顶 12 * **次轮交换**:12 与 6 交换 → `[6, 11, 7, 5, 12, 13]` 调整堆:`[11, 6, 7, 5]` → 新堆顶 11 * **持续交换与调整**:直到堆大小为 1,得到有序数组。 --- --- url: /algorithm/insertion-sort/index.md --- # 插入排序 ## 概述 \==插入排序(Insertion sort)== 是一种简单直观的排序算法。 ### 核心思想 将数组分为 **已排序区间** 和 **未排序区间** ,每次从未排序区间取出一个元素, 在已排序区间中找到合适的位置插入(类似整理扑克牌)。 ## 时间复杂度 插入排序的最优时间复杂度为 $O(n)$,在数列几乎有序时效率很高。 插入排序的最坏时间复杂度和平均时间复杂度都为 $O(n^2)$。 ## 空间复杂度 原地排序, $O(1)$ ,不需要额外空间。 ## 稳定性 插入排序是一种稳定的排序算法 ## 伪代码 $$ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for } i\gets 2\textbf{ to }n\\ 5 & \qquad key\gets A\[i]\\ 6 & \qquad j\gets i-1\\ 7 & \qquad\textbf{while }j>0\textbf{ and }A\[j]>key\\ 8 & \qquad\qquad A\[j + 1]\gets A\[j]\\ 9 & \qquad\qquad j\gets j - 1\\ 10 & \qquad A\[j + 1]\gets key \end{array} $$ ## 实现 ```ts function insertionSort(arr: number[]): number[] { // 遍历未排序区间(从第二个元素开始) for (let i = 1; i < arr.length; i++) { const current = arr[i] // 当前待插入元素 let j = i - 1 // 从已排序区末尾开始比较 // 在已排序区间中寻找插入位置 while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j] // 元素后移 j-- } arr[j + 1] = current // 插入到正确位置 } return arr } // 测试示例 const testArr = [5, 2, 4, 6, 1, 3] console.log(insertionSort([...testArr])) // 输出: [1, 2, 3, 4, 5, 6] ``` ### 执行过程示例 (`[5, 2, 4, 6, 1, 3]`) * 初始状态 ```txt 已排序区 [5] | 未排序区 [2, 4, 6, 1, 3] ``` * 第一轮(插入 $2$ ): * 比较 $5 > 2$ → $5$ 后移 * 插入 $2$ 到首位 → `[2, 5] | [4, 6, 1, 3]` * 第二轮(插入 $4$ ): * $5 > 4$ → $5$ 后移 * $2 < 4$ → 插入到 $5$ 前 → `[2, 4, 5] | [6, 1, 3]` * 第三轮(插入 $6$ ): * $5 < 6$ → 直接插入末尾 → `[2, 4, 5, 6] | [1, 3]` * 第四轮(插入 $1$ ): * 依次与 $6/5/4/2$ 比较 → 全部后移 * 插入到首位 → `[1, 2, 4, 5, 6] | [3]` * 第五轮(插入 $3$ ): * $6/5/4 > 3$ → 后移,$2 < 3$ → 插入 $4$ 前 * 最终结果:`[1, 2, 3, 4, 5, 6]` ## 优化 二分查找优化 ```ts // 二分查找优化(查找插入位置) function insertionSortOptimized(arr: number[]) { for (let i = 1; i < arr.length; i++) { const current = arr[i] const pos = binarySearch(arr, 0, i - 1, current) // 整体后移元素 for (let j = i - 1; j >= pos; j--) { arr[j + 1] = arr[j] } arr[pos] = current } return arr } ``` 二分插入排序:将比较操作优化至 $O(log n)$,但移动操作仍为 $O(n²)$ --- --- url: /algorithm/intro/index.md --- # 概述 ::: info 这篇笔记将介绍数据结构与算法的基础知识,包括数据结构的概念、算法的概念,以及常见的数据结构和算法的实现。 ::: ## 数据结构 数据结构是在计算机中存储、组织数据的方式。小到变量、数组,大到线段树、平衡树,都是数据结构。 程序运行离不开数据结构,不同的数据结构又各有优劣,能够处理的问题各不相同,而根据具体问题选取合适的数据结构, 可以大大提升程序的效率。 ## 算法 算法,顾名思义,即计算的方法。 算法通常用于解决特定的计算任务,但与可以直接在计算机上运行的程序不同, 算法使用数学化的描述,更加侧重于思想,可以被看作抽象的程序。 ## 为什么学习数据结构和算法? 数据结构和算法是计算机科学中的基础,学习这些知识可以帮助我们理解计算机科学的基本原理,更好地解决实际问题。 > 设计出数据结构, 在施加以算法就行了。 --- --- url: /algorithm/merge-sort/index.md --- # 归并排序 ## 概述 \==归并排序(merge sort)== 是高效的基于比较的稳定排序算法 ### 核心思想 **将数组递归拆分为最小单元,再逐步合并有序子序列。** ## 基本原理 ### 分解(Divide) 将长度为 n 的数组递归地拆分为两个长度为 n/2 的子数组,直到子数组长度为 1(天然有序)。 ### 合并(Merge) 归并排序最核心的部分是合并(merge)过程:将两个有序的数组 `a[i]` 和 `b[j]` 合并为一个有序数组 `c[k]`。 从左往右枚举 `a[i]` 和 `b[j]`,找出最小的值并放入数组 `c[k]`;重复上述过程直到 `a[i]` 和 `b[j]` 有一个为空时,将另一个数组剩下的元素放入 `c[k]`。 为保证排序的稳定性,前段首元素小于或等于后段首元素时(`a[i] <= b[j]`)而非小于时(`a[i] < b[j]`)就要作为最小值放入 `c[k]`。 ## 时间复杂度 归并排序基于分治思想将数组分段排序后合并,时间复杂度在最优、最坏与平均情况下均为 $O(n \log n)$,空间复杂度为 $O(n)$。 ## 空间复杂度 归并排序可以只使用 $O(1)$ 的辅助空间,但为便捷通常使用与原数组等长的辅助数组 $O(n)$。 ## 稳定性 归并排序是 稳定的。(合并时左子数组元素优先保证相等元素的原始顺序) ## 实现 ```ts /** * 合并两个有序数组 * @param left 左有序数组 * @param right 右有序数组 * @returns 合并后的有序数组 */ function merge(left: number[], right: number[]): number[] { const result: number[] = [] let leftIndex = 0 let rightIndex = 0 // 双指针遍历比较元素 while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]) leftIndex++ } else { result.push(right[rightIndex]) rightIndex++ } } // 处理剩余元素(左或右数组有剩余) return result.concat(left.slice(leftIndex), right.slice(rightIndex)) } /** * 归并排序主函数 * @param arr 待排序数组 * @returns 排序后的数组 */ function mergeSort(arr: number[]): number[] { // 递归终止条件:数组长度为1时天然有序 if (arr.length <= 1) return arr // 分解数组 const mid = Math.floor(arr.length / 2) const left = arr.slice(0, mid) // 左子数组 const right = arr.slice(mid) // 右子数组 // 递归分解 + 合并有序子数组 return merge(mergeSort(left), mergeSort(right)) } // 测试示例 const array = [38, 27, 43, 3, 9, 82, 10] console.log('排序前:', array) console.log('排序后:', mergeSort(array)) // 输出: [3, 9, 10, 27, 38, 43, 82] ``` ### 执行过程示例(`[38, 27, 43, 3]`) ```txt 分解过程: [38, 27, 43, 3] → [38, 27] 和 [43, 3] → [38] [27] | [43] [3] 合并过程: merge([38], [27]) → [27, 38] merge([43], [3]) → [3, 43] merge([27, 38], [3, 43]) → [3, 27, 38, 43] ``` ## 优化 ### 小数组切换插入排序 当子数组长度较小时(如 `< 15`),插入排序的常数因子更优: ```ts if (arr.length <= 15) return insertionSort(arr) ``` ### 避免重复分配内存 预分配一个全局临时数组,减少递归中多次创建数组的开销。 ### 有序性检测优化 若 `left` 的最大值 `<= right` 的最小值,可直接拼接数组: ```ts if (left[left.length - 1] <= right[0]) { return left.concat(right) } ``` --- --- url: /algorithm/overview/index.md --- # 介绍 ## 概述 \==算法== ,顾名思义,即计算的方法。 算法通常用于解决特定的计算任务,但与可以直接在计算机上运行的程序不同,算法使用数学化的描述,更加侧重于思想,可以被看作抽象的程序。 同一个算法可以有许多种不同的实现方式,两个不同的程序里也可能使用了同一种算法。 ## 复杂度 \==时间复杂度== 和 ==空间复杂度== 是衡量一个算法效率的重要标准。 ### 基本操作数 同一个算法在不同的计算机上运行的速度会有一定的差别,并且实际运行速度难以在理论上进行计算, 实际去测量又比较麻烦,所以我们通常考虑的不是算法运行的实际用时,而是算法运行所需要进行的基本操作的数量。 ::: note 在普通的计算机上,加减乘除、访问变量(基本数据类型的变量,下同)、给变量赋值等都可以看作基本操作。 ::: 对基本操作的计数或是估测可以作为评判算法用时的指标。 ### 时间复杂度 衡量一个算法的快慢,一定要考虑数据规模的大小。 所谓数据规模,一般指输入的数字个数、输入中给出的图的点数与边数等等。一般来说,数据规模越大,算法的用时就越长。 我们衡量一个算法的效率时,最重要的不是看它在某个数据规模下的用时, 而是 ==看它的用时随数据规模而增长的趋势==,即 **时间复杂度**。 当然,算法的运行用时并非完全由输入规模决定,而是也与输入的内容相关。所以,时间复杂度又分为几种,例如: * **最坏时间复杂度**,即每个输入规模下用时最长的输入对应的时间复杂度。在算法竞赛中,由于输入可以在给定的数据范围内任意给定,我们为保证算法能够通过某个数据范围内的任何数据,一般考虑最坏时间复杂度。 * **平均(期望)时间复杂度**,即每个输入规模下所有可能输入对应用时的平均值的复杂度(随机输入下期望用时的复杂度)。 ### 空间复杂度 类似地,算法 ==所使用的空间随输入规模变化的趋势== 可以用 **空间复杂度** 来衡量。 --- --- url: /algorithm/quick-sort/index.md --- # 快速排序 ## 概述 \==快速排序(Quick sort)==,又称为 分区交换排序(partition-exchange sort),简称 **快排**,是一种被广泛运用的排序算法。 ### 核心思想是 **选择一个基准值,将数组分成两个子数组(小于基准值和大于基准值),然后递归排序子数组。** ## 基本原理 快速排序的工作原理是通过 ==分治== 的方式来将一个数组排序。 快速排序分为三个过程: * **选择基准值(Pivot)**:从数组中任选一个元素作为基准 * **分区(Partition)**: * 将小于基准的元素移到基准左侧 * 将大于基准的元素移到基准右侧 * 基准值此时位于最终排序位置 * **递归**:对左右子数组重复上述过程 和 **归并排序**不同,第一步并不是直接分成前后两个序列,而是在分的过程中要保证相对大小关系。 具体来说,第一步要是要把数列分成两个部分,然后保证前一个子数列中的数都小于后一个子数列中的数。 为了保证平均时间复杂度,一般是随机选择一个数 $m$ 来当做两个子数列的分界。 之后,维护一前一后两个指针 $p$ 和 $q$,依次考虑当前的数是否放在了应该放的位置(前还是后)。 如果当前的数没放对,比如说如果后面的指针 $q$ 遇到了一个比 $m$ 小的数,那么可以交换 $p$ 和 $q$ 位置上的数, 再把 $p$ 向后移一位。当前的数的位置全放对后,再移动指针继续处理,直到两个指针相遇。 快速排序没有指定应如何具体实现第一步,不论是选择 $m$ 的过程还是划分的过程,都有不止一种实现方法。 第三步中的序列已经分别有序且第一个序列中的数都小于第二个数,所以直接拼接起来就好了。 ## 时间复杂度 快速排序的最优时间复杂度和平均时间复杂度为 $O(n\log n)$,最坏时间复杂度为 $O(n^2)$。 对于最优情况,每一次选择的分界值都是序列的中位数,此时算法时间复杂度满足的递推式为 $T(n) = 2T(\dfrac{n}{2}) + \Theta(n)$,由主定理,$T(n) = \Theta(n\log n)$。 对于最坏情况,每一次选择的分界值都是序列的最值,此时算法时间复杂度满足的递推式为 $T(n) = T(n - 1) + \Theta(n)$,累加可得 $T(n) = \Theta(n^2)$。 对于平均情况,每一次选择的分界值可以看作是等概率随机的。 ## 空间复杂度 $O(log n)$(递归栈空间) ## 稳定性 快速排序是一种不稳定的排序算法。 ## 实现 ```ts function quickSort(arr: number[]): number[] { if (arr.length <= 1) return arr // 基线条件:数组为空或只有一个元素时直接返回 // 选择基准值(此处取中间元素避免最坏情况) const pivotIndex = Math.floor(arr.length / 2) const pivot = arr[pivotIndex] // 创建左右分区 const left: number[] = [] const right: number[] = [] // 分区操作(跳过基准元素) for (let i = 0; i < arr.length; i++) { if (i === pivotIndex) continue // 跳过基准值本身 arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]) } // 递归排序并合并结果 return [...quickSort(left), pivot, ...quickSort(right)] } // 测试用例 const testArr = [3, 7, 2, 5, 1, 4, 9, 6] console.log(quickSort(testArr)) // 输出: [1, 2, 3, 4, 5, 6, 7, 9] ``` ## 优化 ### 避免最坏情况 * 三数取中法(选首、尾、中的中位数) 通过 **三数取中(即选取第一个、最后一个以及中间的元素中的中位数)** 的方法来选择两个子序列的分界元素(即比较基准)。这样可以避免极端数据(如升序序列或降序序列)带来的退化; ```ts // 三数取中法选择基准 const mid = Math.floor((low + high) / 2) if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]] if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]] if (arr[low] < arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]] return arr[low] // 此时arr[low]是三者的中位数 ``` --- --- url: /algorithm/recursion/index.md --- # 递归 ## 概述 \==递归== ,在数学和计算机科学中是指在函数的定义中使用函数自身的方法, 在计算机科学中还额外指一种 **通过重复将问题分解为同类的子问题而解决问题的方法**。 递归的基本思想是某个函数直接或者间接地调用自身,这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。 求解时只需要关注如何把原问题划分成符合条件的子问题,而不需要过分关注这个子问题是如何被解决的。 ## 如何理解递归? 请看下面的例子: * 点击:递归 * 在 google 中 搜索 **递归** 时,会得到如下结果: ![递归](/images/algorithm/recursion-1.png) * 给一堆数字排序?分成两半,先排左半边再排右半边,最后进行合并。而怎么排左边和右边,重新阅读这句话。 ## 递归的要素 * **基线条件(Base Case)** 递归终止的条件,防止无限递归(栈溢出)。 * **递归条件(Recursive Case)** 将问题分解为更小的子问题,并调用自身。 * **递归方向(Progress)** 每次递归必须向基线条件靠近。 ## 递归示例 ### 阶乘计算 ```ts function factorial(n: number): number { // 基线条件:0! = 1, 1! = 1 if (n <= 1) return 1 // 递归条件:n! = n * (n-1)! return n * factorial(n - 1) } console.log(factorial(5)) // 120 ``` ### 斐波那契数列 ```ts function fibonacci(n: number): number { // 基线条件 if (n === 0) return 0 if (n === 1) return 1 // 递归条件:F(n) = F(n-1) + F(n-2) return fibonacci(n - 1) + fibonacci(n - 2) } console.log(fibonacci(6)) // 8 ``` ## 递归的优化策略 ### 记忆化(Memoization) 缓存计算结果,避免重复递归(适合有重叠子问题的情况)。 ```ts const memo = new Map() function fibonacciMemo(n: number): number { if (n <= 1) return n // 检查缓存 if (memo.has(n)) return memo.get(n)! // 计算并缓存结果 const result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2) memo.set(n, result) return result } ``` ### 尾递归优化(Tail Recursion) 将递归操作置于函数末尾,编译器可优化为迭代(TypeScript 需手动转换)。 ```ts // 阶乘的尾递归实现 function factorialTail(n: number, acc: number = 1): number { return n <= 1 ? acc : factorialTail(n - 1, n * acc) } ``` ## 递归的典型应用场景 * **分治算法** 如归并排序、快速排序。 * **树/图遍历** 如深度优先搜索(DFS)。 * **回溯算法** 如八皇后问题、迷宫求解。 * **动态规划** 通常基于递归定义状态转移方程。 ## 递归的优缺点 | 优点 | 缺点 | | -------------------------- | ------------------------ | | 代码简洁直观,贴近数学定义 | 栈溢出风险(深度过大) | | 简化复杂问题的实现 | 重复计算(需记忆化优化) | | 天然适合处理嵌套结构 | 函数调用开销比循环大 | ## 写递归的要点 * **明确基线条件**:确保递归最终会终止。 * **信任递归**:假设子问题已解决,聚焦当前逻辑。 * **缩小问题规模**:每次递归必须更接近基线条件。 * **避免重复计算**:对重叠子问题使用记忆化。 :::important 明白一个函数的作用并相信它能完成这个任务,千万不要跳进这个函数里面企图探究更多细节,否则就会陷入无穷的细节无法自拔。 ::: ## 递归与分治的区别 递归是一种编程技巧,一种解决问题的思维方式;分治算法很大程度上是基于递归的,解决更具体问题的算法思想。 ## 相关问题 [**LeetCode - 递归**](https://leetcode.cn/tag/recursion/){.read-more} ### 基础递归问题 * **509. 斐波那契数**([LeetCode](https://leetcode.cn/problems/fibonacci-number/)) * **70. 爬楼梯**([LeetCode](https://leetcode.cn/problems/climbing-stairs/)) * **50. Pow(x, n)**([LeetCode](https://leetcode.cn/problems/powx-n/)) ### 链表与树结构递归 * **206. 反转链表**([LeetCode](https://leetcode.cn/problems/reverse-linked-list/)) * **112. 路径总和**([LeetCode](https://leetcode.cn/problems/path-sum/)) * **236. 二叉树的最近公共祖先**([LeetCode](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/)) * **230. 二叉搜索树中第K小的元素**([LeetCode](https://leetcode.cn/problems/kth-smallest-element-in-a-bst/)) ### 分治与回溯问题 * **169. 多数元素**([LeetCode](https://leetcode.cn/problems/majority-element/)) * **22. 括号生成**([LeetCode](https://leetcode.cn/problems/generate-parentheses/)) * **46. 全排列**([LeetCode](https://leetcode.cn/problems/permutations/)) --- --- url: /algorithm/selection-sort/index.md --- # 选择排序 ## 概述 \==选择排序(Selection sort)== 是一种简单直观的排序算法。 ### 核心思想 **每次从未排序部分中选择最小(或最大)元素,将其与未排序部分的起始位置交换。** 重复此过程直到所有元素有序。 ## 算法步骤 1. 将数组分为 已排序区(左侧)和 未排序区(右侧) 2. 初始状态:已排序区为空,未排序区为整个数组 3. 遍历未排序区,找到最小元素的索引 4. 将最小元素与未排序区的第一个元素交换 5. 将已排序区向右扩展一位 6. 重复步骤 3-5 直到未排序区为空 ## 时间复杂度 选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 $O(n^2)$。 ## 空间复杂度 $O(1)$(原地排序,不需要额外空间) ## 稳定性 **不稳定排序**(交换操作可能改变相等元素的原始顺序) ## 伪代码 $$ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for } i\gets 1\textbf{ to }n-1\\ 5 & \qquad ith\gets i\\ 6 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\\ 7 & \qquad\qquad\textbf{if }A\[j]\ arr[max]) max = i } [arr[left], arr[min]] = [arr[min], arr[left]] // 修正最大值被交换的情况 if (max === left) max = min; [arr[right], arr[max]] = [arr[max], arr[right]] left++ right-- } return arr } ``` ### 加入有序检查 提前终止已排序数组的遍历 --- --- url: /algorithm/shell-sort/index.md --- # 希尔排序 ## 概述 \==希尔排序(Shell sort)==,也称为缩小增量排序法,是 [插入排序](./3.插入排序.md) 的一种改进版本。 希尔排序以它的发明者 希尔(Donald Shell)命名。 ### 核心思想 **让距离较远的元素先部分有序,减少后续插入排序的工作量。** ### 核心概念 * **增量序列 (Gap Sequence)** 决定如何划分子序列。初始间隔较大,逐步缩小至 1(最后一次为标准的插入排序)。 **常用序列**:希尔原始序列(N/2, N/4, ..., 1)、Hibbard 序列等。 * **子序列排序** 对每个增量间隔形成的子序列独立进行插入排序。 * **逐步细化** 随着增量减小,序列越来越有序,插入排序的效率显著提高。 ## 过程 排序对不相邻的记录进行比较和移动: 1. 将待排序序列分为若干子序列(每个子序列的元素在原始数组中间距相同); 2. 对这些子序列进行插入排序; 3. 减小每个子序列中元素之间的间距,重复上述过程直至间距减少为 $1$。 ## 时间复杂度 取决于增量序列: * 平均:$O(n log n)$ ~ $O(n²)$ * 最佳:$O(n log n)$ ## 空间复杂度 希尔排序的空间复杂度为 $O(1)$。 ## 稳定性 希尔排序是一种不稳定的排序算法。 ## 实现 ### 基础实现(使用希尔原始序列) ```ts function shellSort(arr: number[]): number[] { const n = arr.length // 初始增量 gap = n/2,逐步减半直至 1 for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) { // 从 gap 开始,对每个子序列执行插入排序 for (let i = gap; i < n; i++) { const temp = arr[i] // 当前待插入元素 let j = i // 在子序列中向前比较并移位 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap] // 较大元素后移 j -= gap } arr[j] = temp // 插入到正确位置 } } return arr } // 测试 const arr = [64, 34, 25, 12, 22, 11, 90] console.log('排序前:', arr) console.log('排序后:', shellSort(arr)) ``` ### 优化实现(使用 Knuth 增量序列) ```ts function shellSortOptimized(arr: number[]): number[] { const n = arr.length // 生成 Knuth 增量序列:1, 4, 13, 40, 121, ... let gap = 1 while (gap < Math.floor(n / 3)) { gap = gap * 3 + 1 // 计算最大有效增量 } while (gap > 0) { for (let i = gap; i < n; i++) { const temp = arr[i] let j = i while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap] j -= gap } arr[j] = temp } gap = Math.floor((gap - 1) / 3) // 缩小增量 } return arr } ``` ### 执行示例(`[8, 3, 5, 1, 4, 2]`) * **初始 Gap = 3** * 子序列 1:`[8, 1]` → 排序后 `[1, 8]` * 子序列 2:`[3, 4]` → 排序后 `[3, 4]` * 子序列 3:`[5, 2]` → 排序后 `[2, 5]` * 新数组:`[1, 3, 2, 8, 4, 5]` * **Gap = 1**(标准插入排序) * 逐步插入排序后得到 \[1, 2, 3, 4, 5, 8] ## 优点 比简单插入排序更快(减少元素移动次数),代码简洁,空间效率高。 ## 缺点 时间复杂度依赖增量序列,不稳定。 --- --- url: /article/0aqe7kd8/index.md --- # TypeScript5.4 值得关注的新特性 2024年2月22日,[TypeScript 发布了 5.4 版本的候选版本](https://devblogs.microsoft.com/typescript/announcing-typescript-5-4-rc/)。其中,有两个新特性,非常值得我们关注,它们有效的提高了开发体验。 ## 保留上次赋值后的类型收缩 在我们编写 typescript 代码时,通常需要检查变量,找出更具体的类型: ```ts function foo(x: string | number) { if (typeof x === 'string') { // typescript 可以推断出当前 `x` 的类型为 `string` return x.toUpperCase() } } ``` 但是,在这里通常会遇到的一个痛点是,`x` 缩窄后的类型并不总是保留函数的闭包中: ```ts function getUrls(url: string | URL, names: string[]) { if (typeof url === 'string') { url = new URL(url) } return names.map((name) => { url.searchParams.set('name', name) // ^^^^^^^^^^^^ // error: // Property 'searchParams' does not exist on type 'string | URL'. // Property 'searchParams' does not exist on type 'string'. return url.toString() }) } ``` 我们读这段代码时,可以明确知道 `url` 在进入 `names.map()` 回调函数中时是 `URL` 类型。 但是,在 `typescript@5.4` 之前,typescript 会假设 `url` 在进入 回调函数中后,其类型 `URL` 是不安全的,认为它可能 会在其他的地方发生变化。 而在这个例子中,回调函数始终在 `url` 完成赋值后创建,并且它也是最后一次赋值,所以 `url` 的类型总是 `URL`。 `typescript@5.4` 利用这一点,使类型收缩变得更加智能。 在 **非提升函数(non-hoisted functions)** 中使用 **参数** 和 **通过 `let` 声明的变量** 时,`typescript` 检查器会 查找最后一个赋值点,如果能够找到,`typescript` 就可以安全的对该变量做类型收缩。 因此,在 `typescript@5.4` 中,上面的例子将不再报错。 但是请注意,如果变量在嵌套函数中的任何位置赋值,则不会进行缩窄分析。这是因为没有办法确定以后是否会调用该函数。 ```ts function printValueLater(value: string | undefined) { if (value === undefined) { value = 'missing!' } setTimeout(() => { // 修改 `value`,即使是以不影响其类型的方式,也会使闭包中的类型收缩无效。 value = 'changed!' }, 500) setTimeout(() => { console.log(value.toUpperCase()) // ^^^^^ // error: 'value' is possibly 'undefined'. }, 1000) } ``` ## Utility Type: `NoInfer` 在 进行 泛型函数 调用时,typescript 可以根据传入的内容推断 参数类型: ```ts function foo(x: T) {} // 我们可以告诉typescript `x` 的类型是 `number` foo(1) // typescript 也可以推断 `x` 的类型是 `string` foo('bar') ``` 然而,typescript 并不总是很清楚要推断的 “最佳” 类型是什么。这可能导致 `typescript` 拒绝有效的调用、 接受有问题的调用,或者只是在捕获错误时报告更糟糕的错误消息。 例如,我们实现一个 `createStreetLight` 函数,它传入 颜色名称列表以及可选的默认颜色。 ```ts function createStreetLight(colors: C[], defaultColor?: C) { // ... } createStreetLight(['red', 'yellow', 'green'], 'red') ``` 当我们传入的 `defaultColor` 不在 `colors` 列表中时,会发生什么? ```ts twoslash function createStreetLight(colors: C[], defaultColor?: C) { // ... } // 这不符合预期,但还是通过了检查 createStreetLight(['red', 'yellow', 'green'], 'blue') // ^? // // // ``` 在这个调用中,类型推断会认为 `"blue"` 与 `"red"`、`"yellow"` 和 `"green"` 都是 有效的, 因此,不会拒绝调用,而是推断类型 `C` 为 `"red" | "yellow" | "green" | "blue"`。 但这显然不符合我们的预期! 目前我们通常是添加一个新的类型参数,该参数由现有的类型参数进行约束。 ```ts function createStreetLight(colors: C[], defaultColor?: D) {} createStreetLight(['red', 'yellow', 'green'], 'blue') // ^^^^^^ // error: // Argument of type '"blue"' is not assignable to parameter of // type '"red" | "yellow" | "green" | undefined'. ``` 这是可行的,但是有点尴尬。因为 签名 `createStreetLight` 可能不会在其他地方使用泛型参数 `D`。 虽然看起来还不错,但是在签名中只使用一次类型参数通常是一种 代码气味。 这就是 在 `TypeScript@5.4` 中引入 `NoInfer` 的原因。 将类型用 `NoInfer<...>` 包围起来,会向 `typescript` 发送信号, 使其不要深入挖掘并匹配内部类型以寻找类型推断的候选对象。 ```ts function createStreetLight(colors: C[], defaultColor?: NoInfer) { // ... } createStreetLight(['red', 'yellow', 'green'], 'blue') // ~~~~~~ // error: // Argument of type '"blue"' is not assignable to parameter // of type '"red" | "yellow" | "green" | undefined'. ``` 排除 `defaultColor` 类型进行推理意味着 `"blue"` 永远不会作为推理候选,并且类型检查器可以拒绝它。 --- --- url: /article/0ed6asz0/index.md --- `Docker` 是一个开源的应用容器引擎,它可以将应用打包到一个可移植的镜像中, 使得应用可以更轻便的部署在任意 Linux 或 Windows 的操作系统的机器上。 同时还提供了环境隔离,很大程度上避免了不同环境不一致带来的各种问题。 `Docker`可轻便移植的特性,也极大的促进了 `CI/CD` 的发展。 **`Docker`架构图** ![architecture](https://docs.docker.com/engine/images/architecture.svg) 从图中可以看出, `Docker` 的组成部分包括: * `docker client`: `docker` 命令行工具 * `docker host`: 宿主机,即 `docker daemon` 的运行环境服务器 * `docker daemon`: `docker` 的守护进程,`docker client` 通过命令行与 `docker daemon` 进行交互 * `container`: 最小型的一个操作系统环境,可以对各种服务和应用容器化 * `image`: 镜像,可以理解为一个容器的模板配置,通过一个镜像可以启动多个容器 * `registry`: 镜像仓库,存储各种镜像,可以从镜像仓库拉取或推送镜像。 ## 安装 > [官方安装文档](https://docs.docker.com/engine/install/) 以下仅说明在 `CentOS` 服务器上的安装过程 ### CentOS 安装 1. 安装依赖 ```sh yum install -y yum-utils device-mapper-persistent-data lvm2 ``` 2. 添加 docker 的yum镜像源,如果在国内,添加阿里云的镜像源 ```sh # 安装 docker 官方的镜像源 yum-config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo # 如果在国内,安装阿里云的镜像 yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo ``` 3. 安装 docker ```sh # 安装 docker sudo yum install docker-ce docker-ce-cli containerd.io docker-buildx-plugin docker-compose-plugin ``` 4. 启动服务 ```sh systemctl enable docker systemctl start docker ``` 当 `docker` 安装成功后,可以使用以下命令查看 `docker` 信息 ```sh # 查看版本信息 docker --version # 查看详细版本信息 docker version # 查看详细配置信息 docker info ``` ### 守护进程配置 `dockerd` 是 `docker` 的守护进程,`dockerd` 可以通过配置文件进行配置,在 `linux` 下的配置文件位置在 `/etc/docker/daemon.json`,更详细内容可以参考 [官方文档](https://docs.docker.com/engine/reference/commandline/dockerd/)。 日志引擎为 `json-file`,对日志结构化,结合合适的日志系统,方便定位日志。 存储引擎为 `overrlay2`。 ```sh mkdir /etc/docker # 设置 docker daemon cat > /etc/docker/daemon.json < [官方镜像仓库](https://hub.docker.com/explore/) 多数情况下,我们不需要自己构建镜像,可以直接从 官方镜像仓库拉取。 使用命令 `docker pull` 进行镜像拉取。 通过 `docker inspect` 查看镜像信息: ```sh # 加入拉取一个 node:alpine 的镜像 docker pull node:alpine # 查看镜像信息 docker inspect node:alpine ``` ### 构建镜像与发布 使用命令 `docker build` 构建镜像。`docker build` 会使用当前目录的 `dockerfile` 构建镜像。 使用 `-t` 指定标签 ```sh # -t node-base:10: 镜像以及版本号 # .: 指当前路径 docker build -t node-base:10 . ``` 当镜像构建成功,使用 `docker push` 推送镜像到仓库。 ## Dockerfile 在使用 `docker` 部署自己应用时,往往需要自己构建镜像。 `docker` 使用 `Dockerfile` 作为配置文件构建镜像: ```dockerfile FROM node:alpine ADD package.json package-lock.json /code/ WORKDIR /code RUN npm install --production ADD . /code CMD npm start ``` ### FROM 基于一个旧有的镜像,格式如下 ```dockerfile FROM [AS ] # 在多阶段构建时会用到 FROM [:] [AS ] ``` ### ADD 把目录,或者 url 地址文件加入到镜像的文件系统中 ```dockerfile ADD [--chown=:] ... ``` ### RUN 执行命令,由于 ufs 的文件系统,它会在当前镜像的顶层新增一层 ```dockerfile RUN ``` ### CMD 指定容器如何启动 一个 `Dockerfile` 中只允许有一个 `CMD` ```dockerfile # exec form, this is the preferred form CMD ["executable","param1","param2"] # as default parameters to ENTRYPOINT CMD ["param1","param2"] # shell form CMD command param1 param2 ``` ## 容器 镜像与容器的关系,类似于代码与进程的关系。 * `docker run` 创建容器 * `docker stop` 停止容器 * `docker rm` 删除容器 ### 创建容器 基于 `nginx` 镜像创建一个最简单的容器:启动一个最简单的 http 服务 使用 `docker run` 来启动容器,`docker ps` 查看容器启动状态 ```sh docker run -d --name nginx -p 8888:80 nginx:alpine docker ps -l CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES 404e88f0d90c nginx:alpine "nginx -g 'daemon of…" 4 minutes ago Up 4 minutes 0.0.0.0:8888->80/tcp nginx CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES ``` 其中: * `-d`: 启动一个 daemon 进程 * `--name`: 为容器指定名称 * `-p host-port:container-port`: 宿主机与容器端口映射,方便容器对外提供服务 * `nginx:alpine`: 基于该镜像创建容器 此时在宿主机使用 curl 测试容器提供的服务是否正常 ```sh curl localhost:8888 ``` 进入容器环境中,使用 `docker exec -it container-name` 命令 ```sh docker exec -it nginx sh / # / # / # ``` ### 容器管理 * `docker ps` 列出所有容器 ```sh docker ps CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES 404e88f0d90c nginx:alpine "nginx -g 'daemon of…" 4 minutes ago Up 4 minutes 0.0.0.0:8888->80/tcp nginx 498e7d74fb4f nginx:alpine "nginx -g 'daemon of…" 7 minutes ago Up 7 minutes 80/tcp lucid_mirzakhani 2ce10556dc8f redis:4.0.6-alpine "docker-entrypoint.s…" 2 months ago Up 2 months 0.0.0.0:6379->6379/tcp apolloserverstarter_redis_1 ``` * `docker port` 查看容器端口映射 ```sh docker port nginx 80/tcp -> 0.0.0.0:8888 ``` * `docker stats` 查看容器资源占用 ```sh docker stats nginx CONTAINER ID NAME CPU % MEM USAGE / LIMIT MEM % NET I/O BLOCK I/O PIDS 404e88f0d90c nginx 0.00% 1.395MiB / 1.796GiB 0.08% 632B / 1.27kB 0B / 0B 2 ``` --- --- url: /article/0m2gcz1j/index.md --- 在现代前端开发中,高效的调试能力是区分初级与高级开发者的关键指标。本文将从基础调试技巧到高级工具链,全面解析JavaScript调试的现代化解决方案。 ## 一、调试基础:从console.log到专业调试 ### 1.1 调试的重要性与演进 在JavaScript开发中,调试已从简单的`console.log`输出演变为完整的工具生态系统。掌握专业调试技能可以: * 快速定位和修复问题 * 深入理解代码执行流程 * 优化应用性能 * 提升开发效率 ### 1.2 调试核心概念 ```javascript // 传统调试方式 console.log('变量值:', variable) console.trace('调用栈追踪') // 现代调试方式 debugger // 断点调试 ``` ## 二、浏览器调试:Chrome DevTools深度解析 ### 2.1 Chrome DevTools核心功能 :::code-tabs @tab Sources面板 ```javascript function processUserData(user) { debugger // 在此设置断点 const processed = { name: user.name.toUpperCase(), age: user.age * 2, timestamp: Date.now() } return processed } ``` @tab Console交互 ```javascript // 在断点处执行 user.name = '测试用户' console.log('当前用户:', user) // 输出:当前用户: {name: "测试用户", age: 25} ``` @tab 监视表达式 ```javascript // 添加监视表达式 user.age > 18 ? '成年' : '未成年' processed.name.length Date.now() - startTime ``` ::: ### 2.2 高级断点技巧 #### 条件断点设置 ```javascript function validateForm(data) { // 右键设置条件断点:data.email.includes('@') if (!data.email.includes('@')) { throw new Error('邮箱格式错误') } // 日志断点:console.log(`验证用户: ${data.username}`) return data.username.length >= 3 } ``` #### XHR/Fetch断点 在Sources面板的**XHR/fetch Breakpoints**区域: * 添加URL包含字符串:`/api/users` * 当匹配请求发生时自动中断 ### 2.3 性能与内存分析 :::steps * **内存快照对比**:拍摄多个时间点的堆快照,识别内存泄漏 * **性能录制**:使用Performance面板录制操作,分析瓶颈 * **网络分析**:监控请求瀑布图,优化加载性能 ::: ## 三、VS Code调试:集成开发环境的力量 ### 3.1 基础调试配置 创建`.vscode/launch.json`配置文件: ```json title=".vscode/launch.json" { "version": "0.2.0", "configurations": [ { "type": "node", "request": "launch", "name": "启动调试", "program": "${workspaceFolder}/src/app.js", "skipFiles": [ "${workspaceFolder}/node_modules/**/*.js", "/**/*.js" ], "env": { "NODE_ENV": "development", "DEBUG": "app:*" } }, { "type": "chrome", "request": "launch", "name": "Chrome调试", "url": "http://localhost:3000", "webRoot": "${workspaceFolder}/src" } ] } ``` ### 3.2 智能调试功能 #### 条件断点与命中计数 ```javascript function processBatch(items) { for (let i = 0; i < items.length; i++) { // 设置命中次数断点:i > 10 const item = items[i] // 表达式条件断点:item.status === 'error' if (item.status === 'error') { console.error('处理错误项:', item) } } } ``` #### 热重载开发体验 ```json title="nodemon配置" { "type": "node", "request": "launch", "name": "Nodemon热重载", "runtimeExecutable": "nodemon", "program": "${workspaceFolder}/src/app.js", "restart": true, "console": "integratedTerminal" } ``` ## 四、Node.js调试:服务端调试全方案 ### 4.1 调试启动方式 ```bash # 基础调试模式 node --inspect app.js # 首行断点模式 node --inspect-brk app.js # 自定义端口 node --inspect=9229 app.js # 生产环境安全调试 node --inspect=127.0.0.1:9229 app.js ``` ### 4.2 异步代码调试 ```javascript title="异步调试示例" async function fetchUserWithPosts(userId) { try { const user = await fetchUser(userId) debugger // 用户数据获取后中断 const posts = await fetchUserPosts(userId) debugger // 帖子数据获取后中断 return { user, posts } } catch (error) { // 启用 "Break on uncaught exceptions" console.error('获取用户数据失败:', error) throw error } } // 启用异步调用栈追踪 // 在DevTools设置中勾选 Async Stack Traces ``` ### 4.3 内存泄漏检测 :::warning 内存泄漏是Node.js应用的常见问题,需要系统化检测和修复。 ::: ```javascript // 内存泄漏检测示例 const leakedReferences = new Set() function createLeakyReference(data) { const reference = { data, timestamp: Date.now() } leakedReferences.add(reference) // 潜在的泄漏点 return reference } // 在Memory面板拍摄堆快照,搜索leakedReferences ``` ## 五、高级调试工具链 ### 5.1 debug模块:智能日志控制 ```javascript title="分级日志系统" const debug = require('debug') // 定义不同级别的日志 const appLog = debug('app:info') const dbLog = debug('app:database') const errorLog = debug('app:error') const perfLog = debug('app:performance') function handleRequest(req, res) { appLog('处理请求: %s %s', req.method, req.url) const startTime = Date.now() // 业务逻辑处理 perfLog('请求处理耗时: %dms', Date.now() - startTime) } // 环境变量控制 // DEBUG=app:* node app.js # 启用所有日志 // DEBUG=app:database node app.js # 仅启用数据库日志 // DEBUG=app:*,-app:performance # 排除性能日志 ``` ### 5.2 Source Map:源码映射调试 :::info Source Map解决了压缩代码的调试难题,是现代前端构建流程的必备技术。 ::: ```javascript title="webpack.config.js" module.exports = { devtool: 'source-map', // 生成完整的Source Map // 其他配置选项: // - 'eval-source-map': 开发环境推荐 // - 'cheap-module-source-map': 生产环境调试 // - 'hidden-source-map': 仅生成但不引用 } ``` ### 5.3 性能分析工具 #### Clinic.js性能诊断 ```bash # 安装clinic.js npm install -g clinic # 性能分析 clinic doctor -- node app.js clinic flame -- node app.js clinic bubbleprof -- node app.js ``` #### 0x火焰图分析 ```bash # 生成火焰图 npx 0x app.js # 访问生成的HTML报告分析性能瓶颈 ``` ## 六、调试最佳实践与工作流 ### 6.1 系统化调试流程 :::steps * **问题复现**:创建最小可复现案例 * **假设验证**:基于现象提出可能原因 * **工具选择**:根据问题类型选择合适的调试工具 * **数据收集**:通过断点、日志、性能分析收集数据 * **根本原因分析**:分析收集的数据找到问题根源 * **解决方案验证**:实施修复并验证效果 ::: ### 6.2 调试效率技巧 ```javascript title="高效调试工具函数" class DebugHelper { static time(label) { console.time(label) return () => console.timeEnd(label) } static trace(message = '') { console.trace(message) } static async measureAsync(fn, label) { const end = DebugHelper.time(label) try { return await fn() } finally { end() } } } // 使用示例 const endTimer = DebugHelper.time('数据加载') // ... 执行代码 endTimer() await DebugHelper.measureAsync( () => fetch('/api/data'), 'API调用耗时' ) ``` ### 6.3 生产环境调试策略 :::caution 生产环境调试需要特别注意安全性和性能影响。 ::: ```javascript title="生产环境安全调试" // 条件调试代码 if (process.env.NODE_ENV === 'development' || process.env.ENABLE_DEBUG === 'true') { const inspector = require('node:inspector') inspector.open(9229, '127.0.0.1') } // 通过环境变量控制调试 const debugEnabled = process.env.DEBUG_LEVEL || 'error' ``` ## 七、现代化调试生态系统 ### 7.1 工具集成方案 :::file-tree * project/ * .vscode/ * launch.json * settings.json * src/ * app.js * utils/ * debug.js * tests/ * debug.test.js * package.json ::: ### 7.2 调试配置自动化 ```json title="package.json调试脚本" { "scripts": { "debug": "node --inspect src/app.js", "debug:brk": "node --inspect-brk src/app.js", "debug:test": "node --inspect test/*.js", "debug:chrome": "node --inspect=9229 src/app.js" } } ``` ## 总结 掌握现代化JavaScript调试工具链,让开发者从"猜测问题"转变为"精准定位",从"被动调试"升级为"主动防御"。通过合理运用Chrome DevTools、VS Code调试器、Node.js调试协议以及各种辅助工具,可以显著提升开发效率和代码质量。 ### 关键要点回顾 1. **==浏览器调试是基础=={.info}**:熟练掌握Chrome DevTools的断点、性能分析和内存调试 2. **==IDE集成提升效率=={.success}**:VS Code调试配置实现开发闭环体验 3. **==服务端调试不可忽视=={.warning}**:Node.js调试协议支持完整的服务端调试 4. **==工具链组合使用=={.important}**:根据场景选择合适的调试工具组合 5. **==生产环境安全第一=={.caution}**:生产调试需要平衡安全性和实用性 ## 参考 * [Chrome DevTools官方文档](https://developer.chrome.com/docs/devtools/) * [VS Code调试指南](https://code.visualstudio.com/docs/editor/debugging) * [Node.js调试指南](https://nodejs.org/en/docs/guides/debugging-getting-started/) --- --- url: /article/1w4onzn1/index.md --- # 为你的站点开启HSTS `HTTP-Strict-Transport-Security` 简称为 `HSTS`,是一个 HTTP 响应头。 用于通知浏览器应该只通过 HTTPS 访问该站点,并且以后使用 HTTP 访问该站点的所有尝试都应自动转换为 HTTPS。 ## 中间人劫持 当用户在未知风险的网络环境中访问 某个网站的时候,如访问 `http://example.com`,在这个未知风险的网络环境中, 可能会被其他人拦截到用户发出的网络请求,然后跳转到一个一模一样的钓鱼网站,或者在请求内容中,注入有危害的代码、广告等, 这种攻击行为,被称为 **中间人劫持**。 当 `example.com` 也支持 `https` 协议进行访问后,如果用户直接通过 `https` 协议访问,那么在一定程度上可以有效防止 `中间人劫持`。 如果用户依然通过 `http` 协议访问,虽然服务器可以重定向到 `https` 请求,然而在这个过程中,中间人依然可以 通过拦截 `http` 请求,然后向服务器发起 `https` 请求获取内容,再注入新的内容 返回给用户。 用户在浏览器地址栏中 输入 `example.com`, 浏览器默认发起的是 `http` 请求,这导致了我们很难要求用户在通过域名访问 网站时,一定要输入 `https://example.com`。 为了限制 `中间人劫持` 这种潜在的攻击手段,一种处理方式就是 强制浏览器使用 `https` 协议访问网站。 为此,我们需要给网站开启 `HSTS`。 ## HSTS `HSTS` 通过声明 `HTTP` 头部字段 `HTTP-Strict-Transport-Security` 来启用和配置策略: ```txt Strict-Transport-Security: max-age= Strict-Transport-Security: max-age=; includeSubDomains Strict-Transport-Security: max-age=; preload ``` ### 指令 #### `max-age=` 设置在浏览器收到这个请求后的``秒的时间内凡是访问这个域名下的请求都使用 HTTPS 请求。 #### `includeSubDomains` 可选 如果这个可选的参数被指定,那么说明此规则也适用于该网站的所有子域名。 #### `preload` 可选 查看 [预加载 HSTS](https://www.chromium.org/hsts/) 获得详情。不是标准的一部分。 ### 浏览器处理 > 当网站已开启 `HSTS` 用户在第一次通过 `https` 协议访问网站时,服务器响应`Strict-Transport-Security` 头,浏览器记录下信息, 在以后重新访问访问网站时,会把访问这个网站的 `http` 请求自动替换为 `https`。 当 `HSTS` 头设置的过期时间到了,后面通过 `HTTP` 的访问恢复到正常模式,不会再自动跳转到 `HTTPS。` 每次浏览器接收到 `Strict-Transport-Security` 头,它都会更新这个网站的过期时间,所以网站可以刷新这些信息,防止过期发生。 Chrome、Firefox 等浏览器里,当尝试访问该域名下的内容时,会产生一个 307 Internal Redirect(内部跳转),自动跳转到 HTTPS 请求。 ## 预加载 如果用户首次访问网站时,依然使用的是 `http` 协议,浏览器会忽略`Strict-Transport-Security`,而且中间人依然可以劫持请求内容,删除 `Strict-Transport-Security`。 为了进一步处理这个问题, `Google`、`Firefox` 等浏览器厂商,维护了一个 `HSTS` 预加载服务。 你可以将你已开启了 `HSTS` 的 站点域名,提交到 预加载服务中,浏览器将会永不使用非安全的方式连接到你的域名。 但是,这不是 HSTS 标准的一部分,也不该被当作正式的内容。 [`HSTS`预加载服务](https://hstspreload.org/) ## 示例 当前域名,以及所有子域名,开启 `HSTS`, 过期时间为 一年。 ```txt Strict-Transport-Security: max-age=31536000; includeSubDomains ``` --- --- url: /article/284xp17b/index.md --- # tsconfig.json 完全使用指南 `TSConfig` 文件是用于表明其所在的目录是一个 `typescript` 或 `javascript` 项目的根目录。 `TSConfig` 文件可以是 `tsconfig.json` 或 `jsconfig.json`,它们的配置和行为相同。 > [官方文档](https://www.typescriptlang.org/tsconfig) ## 基础 使用 `TSConfig` 是一个很容易的事情,只需要在目录下创建一个 `tsconfig.json` 或 `jsconfig.json` 文件即可: ::: code-tabs @tab tsconfig.json ```json {} ``` @tab jsconfig.json ```json {} ``` ::: `TSConfig` 包含了默认配置。 `TSConfig` 主要包含了以下 `top level` 的配置字段: ```json { "extends": "", "compilerOptions": {}, "files": [], "include": [], "exclude": [], "references": [], "watchOptions": {}, "typeAcquisition": {} } ``` ## `extends` **Type**: `string` `extends` 属性用于从另一个 `TSConfig` 文件继承配置。它的值是一个路径, 或者是一个 `Node.js` 风格的路径。 如果是一个相对路径,则相对于配置文件对路径进行解析,如果是一个 `Node.js` 风格的路径,则从 `node_modules`解析获取路径。 `extends` 不会继承 配置文件中的 `files`, `include`, `exclude` 字段,同时,不允许配置文件之间循环引用。 ### example `tsconfig.base.json` ```json { "compilerOptions": { "noImplicitAny": true, "strictNullChecks": true } } ``` `tsconfig.json` ```json { "extends": "./tsconfig.base", "files": ["main.ts"] } ``` `tsconfig.noStrictNullChecks.json` ```json { "extends": "./tsconfig", "compilerOptions": { "strictNullChecks": false } } ``` ## `compilerOptions` 指定 `typescript` 的编译配置。 `compilerOptions` 主要包含以下配置内容: **Type checking:** [`allowUnreachableCode`](#allowunreachablecode), [`allowUnusedLabels`](#allowunusedlabels), [`alwaysStrict`](#alwaysstrict), [`exactOptionalPropertyTypes`](#exactoptionalpropertytypes), [`noFallthroughCasesInSwitch`](#nofallthroughcasesinswitch), [`noImplicitAny`](#noimplicitany), [`noImplicitOverride`](#noimplicitoverride), [`noImplicitReturns`](#noimplicitreturns), [`noImplicitThis`](#noimplicitthis), [`noPropertyAccessFromIndexSignature`](#nopropertyaccessfromindexsignature), [`noUncheckedIndexedAccess`](#nouncheckedindexedaccess),[`noUnusedLocals`](#nounusedlocals), [`noUnusedParameters`](#nounusedparameters), [`strict`](#strict), [`strictBindCallApply`](#strictbindcallapply), [`strictFunctionTypes`](#strictfunctiontypes), [`strictNullChecks`](#strictfunctiontypes), [`strictPropertyInitialization`](#strictpropertyinitialization), [`useUnknownInCatchVariables`](#useunknownincatchvariables) **Modules:** [`allowUmdGlobalAccess`](#allowumdglobalaccess), [`baseUrl`](#baseurl), [`module`](#module), [`moduleResolution`](#moduleresolution), [`moduleSuffixes`](#modulesuffixes), [`noResolve`](#noresolve), [`paths`](#paths), [`resolveJsonModule`](#resolvejsonmodule), [`rootDir`](#rootdir), [`rootDirs`](#rootdirs), [`typeRoots`](#typeroots), [`types`](#types) **Emit:** [`declaration`](#declaration), [`declarationDir`](#declarationdir), [`declarationMap`](#declarationmap), [`downlevelIteration`](#downleveliteration), [`emitBOM`](#emitbom), [`emitDeclarationOnly`](#emitdeclarationonly), [`importHelpers`](#importhelpers), [`importsNotUsedAsValues`](#importsnotusedasvalues), [`inlineSourceMap`](#inlinesourcemap), [`inlineSources`](#inlinesources), [`mapRoot`](#maproot), [`newLine`](#newline), [`noEmit`](#noemit), [`noEmitHelpers`](#noemithelpers), [`noEmitOnError`](#noemitonerror), [`outDir`](#outdir), [`outFile`](#outfile), [`preserveConstEnums`](#preserveconstenums), [`preserveValueImports`](#preservevalueimports), [`removeComments`](#removecomments), [`sourceMap`](#sourcemap), [`sourceRoot`](#sourceroot), [`stripInternal`](#stripinternal) **JavaScript Support:** [`allowJs`](#allowjs), [`checkJs`](#checkjs), [`maxNodeModuleJsDepth`](#maxnodemodulejsdepth) **Editor Support:** [`disableSizeLimit`](#disablesizelimit), [`plugins`](#plugins) **Interop Constraints:** [`allowSyntheticDefaultImports`](#allowsyntheticdefaultimports), [`esModuleInterop`](#esmoduleinterop), [`forceConsistentCasingInFileNames`](#forceconsistentcasinginfilenames), [`isolatedModules`](#isolatedmodules), [`preserveSymlinks`](#preservesymlinks) **Backwards Compatibility:** [`charset`](#charset), [`keyofStringsOnly`](#keyofstringsonly), [`noImplicitUseStrict`](#noimplicitusestrict), [`noStrictGenericChecks`](#nostrictgenericchecks), [`out`](#out), [`suppressExcessPropertyErrors`](#suppressexcesspropertyerrors), [`suppressImplicitAnyIndexErrors`](#suppressimplicitanyindexerrors) **Language and Environment:** [`emitDecoratorMetadata`](#emitdecoratormetadata), [`experimentalDecorators`](#experimentaldecorators), [`jsx`](#jsx), [`jsxFactory`](#jsxfactory), [`jsxFragmentFactory`](#jsxfragmentfactory), [`jsxImportSource`](#jsximportsource), [`lib`](#lib), [`moduleDetection`](#moduledetection), [`noLib`](#nolib),[`reactNamespace`](#reactnamespace),[`target`](#target), [`useDefineForClassFields`](#usedefineforclassfields) **Compiler Diagnostics:** [`diagnostics`](#diagnostics), [`explainFiles`](#explainfiles), [`extendedDiagnostics`](#extendeddiagnostics), [`generateCpuProfile`](#generatecpuprofile), [`generateCpuProfile`](#generatecpuprofile), [`listFiles`](#listfiles), [`traceResolution`](#traceresolution) **Projects:** [`composite`](#composite), [`disableReferencedProjectLoad`](#disablereferencedprojectload), [`disableSolutionSearching`](#disablesolutionsearching), [`disableSourceOfProjectReferenceRedirect`](#disablesourceofprojectreferenceredirect), [`incremental`](#incremental), [`tsBuildInfoFile`](#tsbuildinfofile) **Output Formatting:** [`noErrorTruncation`](#noerrortruncation), [`preserveWatchOutput`](#preservewatchoutput), [`pretty`](#pretty) **Completeness:** [`skipDefaultLibCheck`](#skipdefaultlibcheck),[`skipLibCheck`](#skiplibcheck) **watch options:** [`assumeChangesOnlyAffectDirectDependencies`](#assumechangesonlyaffectdirectdependencies) ### allowUnreachableCode 是否允许代码中包含不会被执行的代码 * `undefined` default 向编辑器提供建议作为警告 * `true` 允许包含 * `false` 不允许,并给出错误警告 **example** `"allowUnreachableCode": false` ```ts function fn(n: number) { if (n > 5) { return true } else { return false } return true // error: Unreachable code detected. } ``` ### allowUnusedLabels 是否允许 未被使用的 `labels`。 * `undefined` default 向编辑器提供建议作为警告 * `true` 允许包含 * `false` 不允许,并给出错误警告 **example:** ```ts function verifyAge(age: number) { // Forgot 'return' statement if (age > 18) { verified: true // error: Unused label. } } ``` ### alwaysStrict 确保文件在ECMAScript严格模式下解析,并对每个源文件添加 `use strict`。 ### exactOptionalPropertyTypes 如果启用 `exactOptionalPropertyTypes`,`typescript` 将会用更加严格的模式,对 通过 `type` 或者 `interface` 声明的包含 `?` 的可选属性的检查 **example:** ```ts interface Theme { colorThemeOverride?: 'dark' | 'light' } ``` 如果没有启用这个配置,那么 `colorThemeOverride` 的值可以是 `'dark'`, `'light'`, `undefined`。 如果启用了这个配置,则值不能被显式的赋值为 `undefined`。 `"exactOptionalPropertyTypes": true` ```ts const theme: Theme = {} theme.colorThemeOverride = 'dark' theme.colorThemeOverride = 'light' theme.colorThemeOverride = undefined // error ``` ### noFallthroughCasesInSwitch 如果配置为 `true`, 则表示 `switch` 语句中的 任何一个非空的 `case` 分支,都必须包含 `break` 或 `return` 。 ### noImplicitAny 在没有类型注释的情况下,`typescript` 在无法推断类型时,会将类型回退到 `any`。这可能会导致一些错误被遗漏。 启用此配置,`typescript` 会在类型回退到 `any` 时报告一个错误。 ```ts function fn(s) { // Parameter 's' implicitly has an 'any' type. console.log(s.subtr(3)) } ``` ### noImplicitOverride ### noImplicitReturns ### noImplicitThis ### noPropertyAccessFromIndexSignature ### noUncheckedIndexedAccess ### noUnusedLocals ### noUnusedParameters ### strict 是否启用 严格模式的类型检查,当开启这个选项时,也会启用所有 `strict` 系列的配置。 ### strictBindCallApply 当开启时,`TypeScript` 会检查 `call`、`bind`和`apply`是否使用正确的参数调用底层函数。 ### strictFunctionTypes 当开启时,`TypeScript` 会对 函数的参数类型使用更严格的检查。 需要注意的是,该配置只适用于 `function` 语法,而不适用于 `method` 语法。 ```ts function fn(x: string) { return x } type Fn = (ns: string | number) => string | number const fn1: Fn = fn // error: Types of parameters 'x' and 'ns' are incompatible. ``` ### strictNullChecks 当开启时,`typescript` 会把 `undefined` 和 `null` 作为不同的类型。 ### strictPropertyInitialization 当启用时,`typescript` 会检查 在 `class` 中已声明的属性,是否有在 `constructor` 中进行初始化。 ### useUnknownInCatchVariables ### allowUmdGlobalAccess 允许 Umd 全局访问。 当 `allowUmdGlobalAccess` 设置为 `true` 时,将允许你在模块文件中以全局变量的形式访问 UMD 的导出。 模块文件是具有或同时导入、导出的文件。当未设置这个选项时,使用 UMD 模块的导出需要首先导入声明。 比如,在一个 Web 项目中, 知道特定的库(如 jQuery 或 Lodash )在运行时总是可用的,但无法通过导入来使用他们。 ### baseUrl 设置解析非绝对路径模块名时的基准目录。 ### module 设置程序的模块系统。 可选值包括: `CommonJS`, `UMD`,`AMD`, `System`,`ESNext`, `ES2020`, `ES6/ES2015`,`ES2022`, `Node16`, `NodeNext`, `None` ### moduleResolution 指定模块解析策略。 可选值包括: `node` ,`classic`。 如果未指定值,当 `module` 为 `CommonJS`时,为 `node`,当 `module` 为 `UMD`,`AMD`, `System`,`ESNext`,`ES2015`时,为 `classic` 。 ### moduleSuffixes 声明在模块解析时,默认搜索的文件名后缀列表 ```json { "compilerOptions": { "moduleSuffixes": [".ios", ".native", ""] } } ``` `import * as foo from "./foo";`, `typescript` 将会检索 `./foo.ios.ts`, `./foo.native.ts`, `./foo.ts`。 ### noResolve ### paths 路径设置。将模块导入重新映射到相对于 baseUrl 路径的配置。 paths 可以允许你声明 TypeScript 应该如何解析你的 require/import。 ```json { "compilerOptions": { "baseUrl": ".", // this must be specified if "paths" is specified. "paths": { "jquery": ["node_modules/jquery/dist/jquery"] } } } ``` 告诉 TypeScript 文件解析器支持一些自定义的前缀来寻找代码。 这种模式可以避免在你的代码中出现过长的相对路径: ```json { "compilerOptions": { "baseUrl": "src", "paths": { "app/*": ["app/*"], "config/*": ["app/_config/*"], "environment/*": ["environments/*"], "shared/*": ["app/_shared/*"], "helpers/*": ["helpers/*"], "tests/*": ["tests/*"] } } } ``` ### resolveJsonModule 允许直接导入 `.json` 模块。并基于json生成静态类型。 ### rootDir 根目录。 **默认**: 所有输入的非声明文件中的最长公共路径。若 composite 被指定,则是包含 tsconfig.json 文件的目录。 ### rootDirs 根目录。 通过 `rootDirs`,你可以告诉编译器有许多“虚拟”的目录作为一个根目录。 这将会允许编译器在这些“虚拟”目录中解析相对应的模块导入,就像它们被合并到同一目录中一样。 ### typeRoots 默认情况下,所有 可见 的 `@types` 包都将包含在你的编译过程中。 在 `node_modules/@types` 中的任何包都被认为是 可见 的。 例如,这意味着包含 `./node_modules/@types/`,`../node_modules/@types/`,`../../node_modules/@types/` 中所有的包。 当 `typeRoots` 被指定,仅有 在 `typeRoots` 下的包会被包含。例如: ```json { "compilerOptions": { "typeRoots": ["./typings", "./vendor/types"] } } ``` 这个配置文件将包含 `./typings` 和 `./vendor/types` 下的所有包,而不包括 `./node_modules/@types` 下的。其中所有的路径都是相对于 `tsconfig.json`。 ### types 默认情况下,所有 可见 的 `@types` 包都将包含在你的编译过程中。 在 `node_modules/@types` 中的任何包都被认为是 可见 的。 例如,这意味着包含 `./node_modules/@types/`,`../node_modules/@types/`,`../../node_modules/@types/` 中所有的包。。 当 types 被指定,则只有列出的包才会被包含在全局范围内。例如: ```json { "compilerOptions": { "types": ["node", "jest", "express"] } } ``` 这个 `tsconfig.json` 文件将 只会 包含 `./node_modules/@types/node`,`./node_modules/@types/jest` 和 `./node_modules/@types/express`。 其他在 `node_modules/@types/*` 下的包将不会被包含。 此选项不会影响 `@types/*` 如何被包含在你的代码中。 当你设置了这个选项,通过不在 types 数组中包含,它将: * 不会再你的项目中添加全局声明(例如 node 中的 process 或 Jest 中的 expect) * 导出不会出现再自动导入的建议中 ### declaration 为你工程中的每个 `TypeScript` 或 `JavaScript` 文件生成 `.d.ts`文件。 这些 `.d.ts` 文件是描述模块外部 API 的类型定义文件。 可以通过 `.d.ts` 文件为非类型化的代码提供 `intellisense` 和精确的类型。 ### declarationDir 配置 声明文件生成的输出目录。 ### declarationMap ### downlevelIteration `downlevel (降级)` 是 `TypeScript` 的术语,指用于转换到旧版本的 `JavaScript。` 这个选项是为了在旧版 `Javascript` 运行时上更准确的实现现代 `JavaScript` 迭代器的概念。 `ECMAScript 6` 增加了几个新的迭代器原语:`for / of` 循环(`for (el of arr)`),数组展开(`[a, ...b]`),参数展开(`fn(...args)`)和 `Symbol.iterator`。 如果 `Symbol.iterator` 存在的话,`--downlevelIteration` 将允许在 ES5 环境更准确的使用这些迭代原语。 ### emitBOM ### emitDeclarationOnly 只生成 `.d.ts` 文件,但不生成 `.js` 文件 ### importHelpers ### importsNotUsedAsValues ### inlineSourceMap 是否 内联 `sourceMap` ### inlineSources ### mapRoot ### newLine 指定输出文件时使用的行尾序列: `CRLF` (dos)或 `LF` (unix)。 ### noEmit 禁止编译器生成文件,例如 `JavaScript` 代码,`source-map` 或声明。 这为另一个工具提供了空间,例如用 `Babel` 或 `swc` 来处理将 `TypeScript` 转换为可以在 `JavaScript` 环境中运行的文件的过程。 然后你可以使用 `TypeScript` 作为提供编辑器集成的工具,或用来对源码进行类型检查。 ### noEmitHelpers ### noEmitOnError 如果报告了任何错误,不允许编译器输出文件,如JavaScript源代码、源映射或声明。 默认为false,这使得在类似监听的环境中使用TypeScript更容易, 在这种环境中,您可能希望在确保所有错误都得到解决之前,再在另一个环境中查看代码更改的结果。 ### outDir 如果被指定,`.js` (以及 .d.ts, .js.map 等)将会被生成到这个目录下。 原始源文件的目录将会被保留,如果计算出的根目录不是你想要的,可以查看 [`rootDir`](#rootdir)。 如果没有指定,`.js` 将被生成至于生成它们的 `.ts` 文件相同的目录中。 ### outFile 如果被指定,所有 全局 (非模块) 文件将被合并到指定的单个输出文件中。 如果 `module` 为 `system` 或 `amd`,所有模块文件也将在所有全局内容之后被合并到这个文件中。 注:除非 `module` 是 `None``,System` 或 `AMD`, 否则不能使用 `outFile`。 这个选项 不能 用来打包 `CommonJS` 或 `ES6` 模块。 ### preserveConstEnums ### preserveValueImports ### removeComments 当转换为 `JavaScript` 时,忽略所有 TypeScript 文件中的注释。默认为 `false`。 ### sourceMap 启用生成 `sourcemap files`。 这些文件允许调试器和其他工具在使用实际生成的 `JavaScript` 文件时, 显示原始的 `TypeScript` 代码。 Source map 文件以 `.js.map` (或 `.jsx.map`)文件的形式被生成到相应的 `.js` 文件输出旁。 `.js` 文件将会包含一个 `sourcemap` 注释,以向外部工具表明文件在哪里。 ### sourceRoot ### stripInternal ### allowJs 允许 `JavaScript` 文件在你的工程中被引入,而不是仅仅允许 `.ts` 和 `.tsx` 文件。 这个选项是一种可以允许 `.ts` 和 `.tsx` 与现有的 `JavaScript` 文件共存的方式。可以用于逐步将 `TypeScript` 文件逐步添加到 JS 工程中。 ### checkJs 与 `allowJs` 配合使用,当 `checkJs` 被启用时,`JavaScript` 文件中会报告错误。也就是相当于在项目中所有 `JavaScript` 文件顶部包含 `// @ts-check`。 ### maxNodeModuleJsDepth ### disableSizeLimit 在处理非常大的`JavaScript`项目时,为了避免可能出现的内存膨胀问题,`TypeScript`分配的内存数量有一个上限。 打开此标志将取消限制。 ### plugins 可在编辑器内运行的语言服务插件列表。 语言服务插件是一种基于现有 `TypeScript` 文件向用户提供额外信息的方法。它们可以改进 `TypeScript` 和编辑器之间的现有信息,或提供自己的错误信息。 ### allowSyntheticDefaultImports 当设置为 true, 并且模块没有显式指定默认导出时,allowSyntheticDefaultImports 可以让你这样写导入: ```ts import React from 'react' ``` 而不是: ```ts import * as React from 'react' ``` 本选项不会影响 `TypeScript` 生成的 `JavaScript`,它仅对类型检查起作用。当你使用 `Babel` 生成额外的默认导出,从而使模块的默认导出更易用时,本选项可以让 `TypeScript` 的行为与 `Babel` 一致。 ### esModuleInterop 默认情况下(未设置 `esModuleInterop` 或值为 `false``),TypeScript` 像 ES6 模块一样对待 `CommonJS/AMD/UMD`。这样的行为有两个被证实的缺陷: * 形如 `import * as moment from "moment"` 这样的命名空间导入等价于 `const moment = require("moment")` * 形如 `import moment from "moment"` 这样的默认导入等价于 `const moment = require("moment").default` 这种错误的行为导致了这两个问题: * ES6 模块规范规定,命名空间导入(`import * as x`)只能是一个对象。TypeScript 把它处理成 `= require("x")` 的行为允许把导入当作一个可调用的函数,这样不符合规范。 * 虽然 `TypeScript` 准确实现了 `ES6` 模块规范,但是大多数使用 `CommonJS/AMD/UMD` 模块的库并没有像 `TypeScript` 那样严格遵守。 开启 `esModuleInterop` 选项将会修复 `TypeScript` 转译中的这两个问题。 ### forceConsistentCasingInFileNames ### isolatedModules 虽然你可以使用 `TypeScript` 来从 `TypeScript` 中生成 `JavaScript` 代码, 但是使用其他转译器例如 `Babel` 也很常见。 但其他转译器一次只能在一个文件上操作, 这意味着它们不能进行基于完全理解类型系统后的代码转译。 这个限制也同样适用于被一些构建工具使用的 `TypeScript` 的 `ts.transpileModule` 接口。 这些限制可能会导致一些 `TypeScript` 特性的运行时问题,例如 `const enum` 和 `namespace`。 设置 `isolatedModules` `选项后,TypeScript` 将会在当你写的某些代码不能被单文件转译的过程正确处理时警告你。 它不会改变你代码的行为,也不会影响 `TypeScript` 的检查和代码生成过程。 如果设置了 `isolatedModules`,则所有的实现文件必须是 模块 (也就是它有某种形式的 `import/export`)。 ### preserveSymlinks ### charset 配置从磁盘读取文本文件时使用的编码。 ### keyofStringsOnly ### noImplicitUseStrict ### noStrictGenericChecks ### out 已弃用。 ### suppressExcessPropertyErrors ### suppressImplicitAnyIndexErrors ### emitDecoratorMetadata 启用对使用`reflect-metadata`模块的装饰器发射类型元数据的实验性支持。 ### experimentalDecorators ### jsx 控制 JSX 在 JavaScript 文件中的输出方式。 这只影响 .tsx 文件的 JS 文件输出。 * `react`: 将 JSX 改为等价的对 `React.createElement` 的调用并生成 .js 文件。 * `react-jsx`: 改为 `__jsx` 调用并生成 .js 文件。 * `react-jsxdev`: 改为 `__jsx` 调用并生成 .js 文件。 * `preserve`: 不对 JSX 进行改变并生成 .jsx 文件。 * `react-native`: 不对 JSX 进行改变并生成 .js 文件。 ### jsxFactory 更改使用经典JSX运行时编译JSX Elements时在.js文件中调用的函数。 最常见的变化是使用`h`或`preact.h`而不是默认的`React`。 ### jsxFragmentFactory ### jsxImportSource ### lib `TypeScript` 包括一组默认的内建 JS 接口(例如 Math)的类型定义,以及在浏览器环境中存在的对象的类型定义 (例如 `document`)。 `TypeScript` 还包括与你指定的 `target` 选项相匹配的较新的 JS 特性的 API。 例如如果`target` 为 `ES6` 或更新的环境,那么 Map 的类型定义是可用的。 你可能出于某些原因改变这些: * 你的程序不运行在浏览器中,因此你不想要 "dom" 类型定义。 * 你的运行时平台提供了某些 JavaScript API 对象(也许通过 polyfill),但还不支持某个 ECMAScript 版本的完整语法。 * 你有一些 (但不是全部)对于更高级别的 ECMAScript 版本的 polyfill 或本地实现。 **高阶库:** | 名称 | 内容 | | ---------- | --------------------------------------------------------------------------------------------------------------------------- | | ES5 | ES3 和 ES5 的核心功能定义 | | ES2015 | ES2015 中额外提供的 API (又被称为 ES6) —— array.find, Promise,Proxy,Symbol,Map,Set,Reflect 等。 | | ES6 | ES2015 的别名。 | | ES2016 | ES2016 中额外提供的 API —— array.include 等。 | | ES7 | ES2016 的别名。 | | ES2017 | ES2017 中额外提供的 API —— Object.entries,Object.values,Atomics,SharedArrayBuffer,date.formatToParts,typed arrays 等。 | | ES2018 | ES2018 中额外提供的 API —— async iterables,promise.finally,Intl.PluralRules,rexexp.groups 等。 | | ES2019 | ES2019 中额外提供的 API —— array.flat,array.flatMap,Object.fromEntries,string.trimStart,string.trimEnd 等。 | | ES2020 | ES2020 中额外提供的 API —— string.matchAll 等。 | | ESNext | ESNext 中额外提供的 API —— 随着 JavaScript 的发展,这些会发生变化。 | | DOM | DOM 定义 —— window,document 等。 | | WebWorker | WebWorker 上下文中存在的 API。 | | ScriptHost | Windows Script Hosting System 的 API。 | **库的各个组件:** `DOM.Iterable`, `ES2015.Core`, `ES2015.Collection`, `ES2015.Generator`, `ES2015.Iterable`, `ES2015.Promise`, `ES2015.Proxy`, `ES2015.Reflect`, `ES2015.Symbol`, `ES2015.Symbol.WellKnown`, `ES2016.Array.Include`, `ES2017.object`, `ES2017.Intl`, `ES2017.SharedMemory`, `ES2017.String`, `ES2017.TypedArrays`, `ES2018.Intl`, `ES2018.Promise`, `ES2018.RegExp`, `ES2019.Array`, `ES2019.Full`, `ES2019.Object`, `ES2019.String`, `ES2019.Symbol`, `ES2020.Full`, `ES2020.String`, `ES2020.Symbol.wellknown`, `ESNext.AsyncIterable`, `ESNext.Array`, `ESNext.Intl`, `ESNext.Symbol` ### moduleDetection 模块检查。 * `auto` (default): `typescript` 会不仅检查 `import` 或 `export` 语句, 还会检查 `package.json` 是否有 `type` 字段,且当 配置文件中 `module` 值是否为 `nodenext` 或 `node16`时,`type` 字段值为 `module`。以及检查。 当使用 `jsx: react-jsx` 配置时,当前文件是否是 `jsx` 文件。 * `legacy`: 检查文件是否包含 检查 `import` 或 `export` 语句。 * `force` : 确保每个非声明文件都被视为是一个模块。 ### noLib 禁用自动包含任何库文件。如果设置了该选项,lib将被忽略。 ### reactNamespace 已弃用,改用 [\`jsxFactory](#jsxfactory) ### target 编译目标 现代浏览器支持全部 `ES6` 的功能,所以 `ES6` 是一个不错的选择。 如果你的代码部署在旧的环境中,你可以选择设置一个更低的目标;如果你的代码保证会运行在新的环境中,你可以选择一个更高的目标。 `target` 的配置将会改变哪些 JS 特性会被降级,而哪些会被完整保留 例如,如果 `target` 是 `ES5` 或更低版本,箭头函数 `() => this` 会被转换为等价的 函数 表达式。 改变 `target` 也会改变 `lib` 选项的默认值。 你可以根据需要混搭 `target` 和 `lib` 的配置,你也可以为了方便只设置 `target`。 特殊的 `ESNext` 值代表你的 `TypeScript` 所支持的最高版本。这个配置应当被谨慎使用,因为它在不同的 `TypeScript` 版本之间的含义不同,并且会导致升级更难预测。 可选值: `es3` (default), `es5`, `es6/es2015`, `es2016`, `es2017`, `es2018`, `es2019`, `es2020`, `es2021`, `es2022`, `esnext` ### useDefineForClassFields ### diagnostics ### explainFiles ### extendedDiagnostics ### generateCpuProfile ### listEmittedFiles ### listFiles ### traceResolution ### composite `composite` 选项会强制执行某些约束,使得构建工具(包括 在 `--build` 模式下的 `TypeScript` 本身)可以快速确定一个工程是否已经建立。 当此设置开启时: * 如果没有明确指定 `rootDir`,则默认为包含 `tsconfig.json` 文件的目录。 * 所有实现的文件必须由 `include` 来匹配,或在 `files` 数组中指定。如果违反了这一约束,`tsc` 将告诉你哪些文件没有被指定。 * `declaration` 默认为 `true`。 ### disableReferencedProjectLoad ### disableSolutionSearching ### disableSourceOfProjectReferenceRedirect ### incremental 使 TypeScript 将上次编译的工程图信息保存到磁盘上的文件中。这将会在您编译输出的同一文件夹中创建一系列 `.tsbuildinfo` 文件。 它们不会再运行时被您的 `JavaScript` 使用,并且可以被安全的删除。 ### tsBuildInfoFile 这个选项可以让您指定一个文件来存储增量编译信息,以作为复合工程的一部分,从而可以更快的构建更大的 `TypeScript` 代码库。 这个选项提供了一种方法,可以配置 `TypeScript` 追踪它存储在磁盘上的文件的位置,用来指示项目的构建状态。—— 默认情况下,它们与你生成的 `JavaScript` 在同一个文件夹中。 ### noErrorTruncation 启用时,错误信息不会被截断。 ### preserveWatchOutput 是否在控制台保留历史监听信息,而不是清空它们。 ### pretty 是否使用 颜色和样式 格式化 输出信息。 ### skipDefaultLibCheck 使用 `skipLibCheck` 此配置。 ### skipLibCheck 跳过声明文件的类型检查。 这可以在编译期间节省时间,但代价是类型系统的准确性。例如,两个库可以以不一致的方式定义同一类型的两个副本。TypeScript不会对所有`d.ts`文件进行全面检查,而是会对你在应用源代码中特别引用的代码进行类型检查。 ### assumeChangesOnlyAffectDirectDependencies 当这个选项被启用时,TypeScript将避免重新检查/重建所有可能真正受影响的文件,只检查/重建已经更改的文件以及直接导入这些文件的文件。 这可以被认为是监视算法的“快速和松散”实现,它可以大幅减少增量重建时间,代价是不得不偶尔运行完整的构建以获得所有编译器错误消息。 ## `files` **Types**: `string[]` 显式的指定需要编译的文件列表。 如果列表中的文件不存在,则会发生错误。 ### example ```json { "files": ["main.ts", "core.ts", "shared.ts", "utils.ts"] } ``` ## `include` **Type**: `string[]` 指定需要编译的文件列表,可以是目录,文件,也可以是模式匹配。 这些文件路径是相对于包含`tsconfig.json`的目录进行解析。 ### example ```json { "include": ["src/**/*.ts", "test/**/*.ts"] } ``` 它将会匹配: ```sh . ├── scripts ⨯ │ ├── lint.ts ⨯ │ ├── update_deps.ts ⨯ │ └── utils.ts ⨯ ├── src ✓ │ ├── client ✓ │ │ ├── index.ts ✓ │ │ └── utils.ts ✓ │ ├── server ✓ │ │ └── index.ts ✓ ├── tests ✓ │ ├── app.test.ts ✓ │ ├── utils.ts ✓ │ └── tests.d.ts ✓ ├── package.json ├── tsconfig.json └── yarn.lock ``` ### patterns `include` 和 `exclude` 支持使用 通配符 模式匹配: * `*` 匹配零个到多个字符(不包含目录分隔符) * `?` 匹配任意一个字符(不包含目录分隔符) * `**/` 匹配任意嵌套深度的目录 ## `exclude` **Type**: `string[]` 指定在解析 `include` 包含的文件时,应该跳过的文件列表,可以是目录,文件,也可以是模式匹配。 ### example ```json { "exclude": ["src/**/*.spec.ts"] } ``` **提示**: `exclude` 仅排除已包含在 `include` 设置中的文件。 但有时候即使`exclude` 已配置了排除某个文件,但在代码中仍然使用`import` 语句引入该文件,或在 `types` 中包含该文件, 或通过 `/// { console.log('Timer running, data length:', largeData.length) }, 1000) // 返回清理函数 return function stopTimer() { clearInterval(timerId) largeData = null // 明确解除引用 } } // 使用示例 const cleanup = startTimerWithCleanup() // 不再需要时调用 cleanup(); ``` ### 3.3 闭包导致的泄漏 ```javascript title="闭包优化示例" function avoidLeak() { let largeData = Array.from({ length: 10000000 }).fill('data') // 只提取需要的数据 let firstItem = largeData[0] // 返回仅捕获所需数据的闭包 return function optimizedFunction() { console.log('First item:', firstItem) } // largeData在此函数执行完毕后可以被垃圾回收 } ``` ### 3.4 DOM引用问题 ```javascript title="DOM引用管理" class DOMReferenceManager { constructor() { this.elements = new Map() } registerElement(id, element) { this.elements.set(id, element) } removeElement(id) { const element = this.elements.get(id) if (element && element.parentNode) { element.parentNode.removeChild(element) } this.elements.delete(id) // 清除引用 } } ``` ## 四、内存优化高级技术 ### 4.1 使用WeakMap和WeakSet ```javascript title="WeakMap应用示例" const privateData = new WeakMap() class User { constructor(name, age) { // 存储私有数据 privateData.set(this, { name, age, loginHistory: [] }) } getName() { return privateData.get(this).name } } // 当user对象被回收时,WeakMap中的私有数据自动清理 ``` ### 4.2 对象池模式 ```javascript title="对象池实现" class ParticlePool { constructor(size) { this.pool = Array.from({ length: size }).fill().map(() => ({ x: 0, y: 0, vx: 0, vy: 0, active: false })) } get() { for (let i = 0; i < this.pool.length; i++) { if (!this.pool[i].active) { this.pool[i].active = true return this.pool[i] } } return null } release(particle) { particle.active = false // 重置属性 particle.x = particle.y = particle.vx = particle.vy = 0 } } ``` ### 4.3 数据虚拟化 ```javascript title="虚拟列表实现" class VirtualList { constructor(container, itemHeight, totalItems, renderItem) { this.container = container this.itemHeight = itemHeight this.totalItems = totalItems this.renderItem = renderItem this.init() } render() { const scrollTop = this.container.scrollTop const startIndex = Math.floor(scrollTop / this.itemHeight) const visibleItems = Math.ceil(this.container.clientHeight / this.itemHeight) + 2 const endIndex = Math.min(startIndex + visibleItems, this.totalItems) // 只渲染可见项 this.renderVisibleItems(startIndex, endIndex) } } ``` ## 五、内存检测与分析工具 ### 5.1 Chrome DevTools内存分析 :::steps * 打开Performance面板,勾选Memory选项记录内存使用趋势 * 使用Memory面板的堆快照功能比较不同时间点的内存状态 * 通过Allocation Timeline分析内存分配模式 ::: ### 5.2 编程式内存监控 ```javascript title="内存监控工具" class MemoryMonitor { constructor(interval = 5000) { this.interval = interval this.history = [] } start() { this.timer = setInterval(() => { if (window.performance?.memory) { const memory = performance.memory const data = { used: memory.usedJSHeapSize, total: memory.totalJSHeapSize, limit: memory.jsHeapSizeLimit, timestamp: Date.now() } this.history.push(data) this.analyzeTrend() } }, this.interval) } analyzeTrend() { if (this.history.length > 5) { const growthRate = this.calculateGrowthRate() if (growthRate > 1048576) { // 1MB/s console.warn('Possible memory leak detected!') } } } } ``` ## 六、框架特定的内存管理 ### 6.1 React内存优化 ```javascript title="React优化示例" import React, { useCallback, useMemo, useState } from 'react' function SearchComponent({ onSearch }) { const [query, setQuery] = useState('') // 使用useCallback防止不必要的函数重新创建 const handleSearch = useCallback(() => { onSearch(query) }, [query, onSearch]) // 使用useMemo缓存计算结果 const processedData = useMemo(() => { return processLargeDataSet(data) }, [data]) return (
setQuery(e.target.value)} />
) } ``` ### 6.2 Vue内存优化 ```vue title="Vue优化示例" ``` ## 七、未来趋势与新技术 ### 7.1 WebAssembly内存控制 ```javascript title="WebAssembly内存管理" async function initWasmProcessor() { const result = await WebAssembly.instantiateStreaming( fetch('/processor.wasm') ) const wasmModule = result.instance const memory = wasmModule.exports.memory return { process: (data) => { // 使用WASM内存进行高效处理 const bufferPtr = wasmModule.exports.allocateBuffer(data.length) const wasmBuffer = new Uint8Array(memory.buffer, bufferPtr, data.length) wasmBuffer.set(data) wasmModule.exports.processData(bufferPtr, data.length) // 手动释放内存 wasmModule.exports.freeBuffer(bufferPtr) } } } ``` ## 总结 :::important 关键要点 1. **理解内存模型**:掌握栈内存和堆内存的区别是内存管理的基础 2. **识别泄漏模式**:熟悉常见的泄漏场景并采用相应的预防措施 3. **善用工具**:熟练使用浏览器开发者工具进行内存分析 4. **采用优化模式**:对象池、数据虚拟化等模式可显著提升性能 5. **框架最佳实践**:遵循React、Vue等框架的内存管理指南 ::: :::tip 黄金法则 * 闭包引用记心上,用后即焚保平安 * 定时任务守纪律,临走要留请假条 * DOM元素易缠身,解绑删除要彻底 * 大对象操作如履冰,池化管理效率高 * 弱引用工具随身带,适时使用解烦恼 ::: 通过深入理解JavaScript的内存管理机制,我们能够编写出更加高效、稳定的应用程序。内存管理不是一劳永逸的工作,而是需要持续关注的领域,只有不断学习和实践,才能在复杂的前端应用中游刃有余。 ## 参考 * [MDN Web Docs: JavaScript 内存管理](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Guide/Memory_management) * [V8 开发者博客: 垃圾回收](https://v8.dev/blog/trash-talk) * [Chrome DevTools 内存分析指南](https://developers.google.com/web/tools/chrome-devtools/memory-problems) --- --- url: /article/2f45bq9x/index.md --- # 跨域资源共享(CORS) **跨域资源共享(CORS)** 是一种基于 **HTTP Header** 的机制。 该机制通过允许服务器标示除了它自己的 origin(域,协议和端口),使这些 origin 有权限访问加载服务器上的资源。 跨域资源共享 通过 **预检请求** 的机制,检查服务器是否允许要发送的真实请求。 浏览器向服务器发送一个到服务器托管的跨域资源 **预检请求**, 在预检请求中,浏览器发送的头部中标示有HTTP方法和真实请求会用到的头。 ## 前言 浏览器出于安全性的原因,会限制脚本内发起的跨域资源请求, 比如 **XMLHttpRequest** 和 **Fetch API** 遵循 **同源策略**,默认情况下不允许发起非同源的资源请求。 使用这些API的Web应用,只能加载从应用程序的同一个域的请求HTTP资源, **除非响应报文中包含了正确的CORS响应头** ## 概述 跨域资源共享 新增了一组 HTTP首部字段,允许服务器声明哪些源站通过浏览器有权限访问哪些资源。 同时,对于可能对服务器数据产生副作用的 HTTP 请求方法,浏览器必须首先使用 `OPTIONS` 方法发起一个预检请求, 从而获取服务器是否允许跨域请求,服务器确认允许之后,才发起实际的HTTP请求。 CORS 请求失败会产生错误,但是为了安全,在 JavaScript 代码中,是无法获取具体是哪里出了问题。 我们只能通过查看浏览器的控制台来获取具体出现的错误。 若要开启 CORS ,我们需要配置 CORS 相关的 HTTP首部字段。 ## HTTP 响应首部字段 在 CORS 中,HTTP 响应首部字段主要有以下几个: * **Access-Control-Allow-Origin** * **Access-Control-Allow-Methods** * **Access-Control-Allow-Headers** * **Access-Control-Max-Age** * **Access-Control-Expose-Headers** * **Access-Control-Allow-Credentials** ### Access-Control-Allow-Origin **Access-Control-Allow-Origin** 响应首部字段,用于 **指定允许访问该资源的外域URI**。 对于不需要携带身份凭证的请求,服务器可以指定改字段的值为通配符(`*`),表示允许来自所有域的请求。 语法: ```txt Access-Control-Allow-Origin: Access-Control-Allow-Origin: * ``` 如果服务器 指定了具体的域名而非 `*`,那么响应首部中的 **Vary** 字段的值必须包含 `Origin`。 用于告诉客户端:服务器对不同的源站返回不同的内容。 ::: info 注意 当响应的是附带身份凭证的请求时,服务端 必须 明确 **Access-Control-Allow-Origin** 的值,而不能使用通配符`“*”`。 ::: **示例1:** 允许所有域访问 ```txt Access-Control-Allow-Origin: * ``` **示例2:** 允许来自 的请求 ```txt Access-Control-Allow-Origin: https://pengzhanbo.cn Vary: Origin ``` ### Access-Control-Allow-Methods **Access-Control-Allow-Methods** 响应首部字段用于 预检请求的响应。 **指明了实际请求所允许使用的HTTP方法或方法列表**。 语法: ```txt Access-Control-Allow-Methods: [, ]* ``` 示例: ```txt Access-Control-Allow-Methods: POST, GET, OPTIONS ``` ### Access-Control-Allow-Headers **Access-Control-Allow-Headers** 响应首部字段用于 预检请求的响应。 **指明了实际请求中允许携带的首部字段**。 语法: ```txt Access-Control-Allow-Headers: [, header-name]* Access-Control-Allow-Headers: * ``` 以下特定的首部是一直允许的,无需特意声明他们: * Accept * Accept-Language * Content-Language * Content-Type,但只在其值属于MIME类型 `application/x-www-form-urlencoded`,`multipart/form-data`,`text/pain` 中的一种。 **示例1:** 自定义请求头。 除了 CORS 安全清单列出的请求头外,支持 自定义请求头 X-Custom-Header ```txt Access-Control-Allow-Headers: X-Custom-Header ``` **示例2:** 多个自定义请求头。 ```txt Access-Control-Allow-Headers: X-Custom-Header, X-My-Header ``` ### Access-Control-Max-Age **Access-Control-Max-Age** 响应首部字段表示 **预检请求的返回结果可以被缓存多久**。 返回结果是指: **Access-Control-Allow-Methods** 和 **Access-Control-Allow-Headers** 提供的信息。 语法: ```txt Access-Control-Max-Age: ``` **delta-seconds** 表示返回结果可以被缓存的最长时间(秒)。 在 Firefox 中, 上限是 **24小时(86400秒)**。 在 Chromium 中,上限是 **2小时(7200秒)**,同时 Chromium 还规定了默认值是 **5秒**。 如果值为 **-1** , 表示禁用缓存,则每次请求前都需要使用 OPTIONS 预检请求。 **示例:** 将预检请求缓存 10分钟: ```txt Access-Control-Max-Age: 600 ``` ### Access-Control-Expose-Headers **Access-Control-Expose-Headers** 响应首部字段,列出了 哪些首部可以作为响应的一部分暴露给外部。 在 跨源访问时,XMLHttpRequest 对象的 `getResponseHeader()` 方法默认只能拿到一些最基本的响应头。 默认情况下,只有七种 简单响应首部 可以暴露给外部: * Cache-Control * Content-Language * Content-Length * Content-Type * Expires * Last-Modified * Pragma 如果期望让客户端可以访问到其他的首部信息,可以将它们 该字段受列出来。 语法: ```txt Access-Control-Expose-Headers: [, ]* ``` **示例:** 暴露一个非简单响应首部: ```txt Access-Control-Expose-Headers: X-My-Header ``` 暴露多个非简单响应首部: ```txt Access-Control-Expose-Headers: X-My-Header, X-Custom-Header ``` ### Access-Control-Allow-Credentials **Access-Control-Allow-Credentials** 响应首部字段 用于在 请求包含 Credentials 时, 告知浏览器是否可以将对请求的响应暴露给前端 JavaScript 代码。 当请求的 Credentials 模式 (Request.credentials)为 `include` 时,浏览器尽在相应头 **Access-Control-Allow-Credentials** 的值为 `true` 时将响应暴露给前端的 JavaScript 代码。 Credentials 可以是 `cookies`、 `authorization headers` 或 `TLS client certificates`。 语法: ```txt Access-Control-Allow-Credentials: true ``` **Access-Control-Allow-Credentials** 需要与 `XMLHttpRequest.withCredentials` 或 **Fetch API** 的 `Request()` 构造函数中的 `credentials` 选项结合使用。 Credentials 必须在前后端都被配置,才能使带 credentials 的 CORS 请求成功。 **示例:** 允许 credentials ```txt Access-Control-Allow-Credentials: true ``` 使用带 credentials 的 XHR: ```js const xhr = new XMLHttpRequest() xhr.open('GET', 'https://pengzhanbo.cn', true) xhr.withCredentials = true xhr.send(null) ``` 使用带 credentials 的 Fetch: ```js fetch('https://pengzhanbo.cn', { credentials: 'include', }) ``` ## HTTP 请求首部字段 在 CORS 中,可用于发起跨域请求的首部字段,如下: * Origin * Access-Control-Request-Method * Access-Control-Request-Headers 这些首部字段无需手动设置。 当开发者使用 XMLHttpRequest 发起跨域请求时,它们已经被设置就绪。 ### Origin **Origin** 请求首部字段表明预检请求或实际请求的源站。 语法: ```txt Origin: ``` origin 参数的值为源站的URI。不包含任何路径信息,仅表示服务器名称。 ### Access-Control-Request-Method **Access-Control-Request-Method** 请求首部字段用于预检请求。作用是 将实际情况所使用的HTTP方法告诉服务器。 语法: ```txt Access-Control-Request-Method: ``` ### Access-Control-Request-Headers **Access-Control-Request-Headers** 请求首部字段用于预检请求。作用是 将实际请求所携带的首部字段告诉服务器。 语法: ```txt Access-Control-Request-Headers: [, ]* ``` ## 预检请求 一个 CORS 预检请求时用于 检查服务器使用支持 CORS, 即 跨域资源共享。 预检请求 通过 发送一个 OPTIONS 请求,请求头部包含了以下字段: * Access-Control-Request-Method * Access-Control-Request-Headers * Origin 浏览器会在有必要的时候,自动发出一个预检请求。 所以在正常情况下,前端开发者不需要自己去发送这样的请求。 ### 预检请求与凭据 CORS 预检请求不能包含凭据。预检请求的响应必须指定 Access-Control-Allow-Credentials: true 来表明可以携带凭据进行实际的请求。 ## 简单请求 某些情况下,不会触发 CORS预检请求,这样的请求,可表述为 *简单请求*。 若请求满足以下所有条件,则可视为 简单请求: * 使用 GET, HEAD POST 请求方法 * 除了被用户代理自动设置的首部字段(Connection,User-Agent等), 以及在 Fetch 规范中定义为 [禁用首部名称](https://fetch.spec.whatwg.org/#forbidden-header-name) 的其他首部, 允许人为设置的字段为 Fetch 规范定义的 对 [CORS 安全的首部字段集合](https://fetch.spec.whatwg.org/#cors-safelisted-request-header) * 请求中任意的 XMLHttpRequest 对象均没有注册任何监听事件, XMLHttpRequest 对象可以使用 XMLHttpRequest.upload 属性访问。 * 请求中没有使用 ReadableStream 对象。 ## 附带身份的请求与通配符 在响应附带身份凭证的请求时: * 服务器不能将 **Access-Control-Allow-Origin** 的值设为通配符 `*`,而应将其设置为特定的域,如:Access-Control-Allow-Origin: * 服务器不能将 **Access-Control-Allow-Headers** 的值设为通配符 `*`,而应将其设置为首部名称的列表,如:Access-Control-Allow-Headers: X-Custom-Header, Content-Type * 服务器不能将 **Access-Control-Allow-Methods** 的值设为通配符 `*`,而应将其设置为特定请求方法名称的列表,如:Access-Control-Allow-Methods: POST, GET ## 需要CORS的场景 1. 使用 **XMLHttpRequest** 发起的 HTTP请求 2. 使用 **Fetch API** 发起的 HTTP 请求 3. Web字体,CSS通过 `@font-face` 使用的跨域字体资源 4. WebGL 贴图 5. 使用 drawImage 将 Images/video 画面绘制到 canvas 6. 来自图像的 CSS 图形 ## 安全 在实际的使用场景中,尽可能的少使用 通配符 `*`,来允许所有域访问,或允许所有自定义首部字段, 这可能在 web 安全上来带风险。 --- --- url: /article/4ef5e74b/index.md --- # 一文读懂 CSS 自定义滚动条 有时候,为了保持我们的应用程序 UI 交互体验在不同系统的一致性,需要覆盖默认的滚动条, 通过自定义滚动条的方式,获得更好的用户体验。 :::window ![scrollbar intro](/images/scrollbar/scrollbar-intro.jpg) ::: ## 滚动条的组成 首先,需要了解 滚动条由哪些部分组成的。 滚动条主要包含两个部分: **滚动轨道 Track** 和 **滑块 Thumb**。 :::window ![scrollbar parts](/images/scrollbar/scrollbar-parts.jpg) ::: **Track** 是滚动条的底部, **Thumb** 是提供用户交互的, 当用户拖动它控制页面或容器的滚动内容。 滚动条可以出现在 **水平** 或者 **垂直** 方向,而且在 多语言环境下,也会随着 从左到右 `LTR` 和 从右到左 `RTL` 而变化。 :::window ![scrollbar places dir](/images/scrollbar/scrollbar-places-dir.jpg) ::: ## 自定义滚动条 在过去,能够进行 自定义滚动条的, 只有 基于 `webkit` 内核的浏览器 得到了支持,而像 `Firefox` 和 `IE` 浏览器则不具备 自定义滚动条 的能力。但是,对于 `Firebox`, CSS 有了新的语法帮助我们完成滚动条的自定义。 我将分别介绍 `webkit` 下的旧的语法,然后是 新的语法。 ### 旧的语法 #### 滚动条宽度 首先,我们需要定义滚动条的大小,它可以是垂直滚动条的宽度,也可以是水平滚动条的高度。 ```css .container::-webkit-scrollbar { width: 10px; } ``` 然后,我们就可以开始自定义滚动条的样式了。 #### 滚动条 Track Track 表示滚动条的底部,我们可以通过添加 `background-color`、`box-shadow`、 `border-radius` 和 `border` 来控制 Track 的样式。 ```css .container::-webkit-scrollbar-track { background-color: darkgrey; } ``` #### 滚动条 Thumb 准备好 滚动条的底部后,我们还需要设置滚动条 `Thumb` 的样式。用户可以拖动 `Thumb` 来与滚动条进行交互。 ```css .container::-webkit-scrollbar-thumb { box-shadow: inset 0 0 6px rgba(0, 0, 0, 0.3); } ``` #### 旧语法浏览器兼容 @[caniuse](mdn-css_selectors_-webkit-scrollbar) 至此,我们已经介绍了 CSS 中设置 自定义滚动条的旧语法以及兼容性。 接下来,我们将介绍 CSS 中设置 自定义滚动条的新语法。 ### 新语法 #### 滚动条宽度 这定义了滚动条宽度,我们需要关注的值是 `auto` 和 `thin` 。 需要注意的是,我们无法像 `webkit` 语法那样定义一个特定的数字。 ```css .section { scrollbar-width: thin; } ``` #### 滚动条颜色 使用此属性,我们可以将滚动条 `Track` 和 `Thumb` 的颜色定义为成对的值。 ```css .section { scrollbar-color: #6969dd #e0e0e0; } ``` 尽管这种语法很简单,但是我们只能使用 纯色,无法添加 阴影、渐变、圆角边框 等其他相关的样式。 #### 滚动条装订线 Gutter 你有没有想过,当内容在滚动容器中增加时,我们如何避免布局变化?让我们以以下案例为例。 :::window ![scrollbar gutter](/images/scrollbar/scrollbar-gutter-1.jpg) ::: ```css .box { padding: 1rem; max-height: 220px; overflow-y: auto; } ``` 我们有一个四周都有 1rem 的内边距的容器。到目前为止,内容很短,滚动条不会显示,因为使用了 `overflow-y: auto`。 > \[!note] > 当我们使用 `overflow-y: auto` ,当内容很短时不会显示滚动条,直到内容超过了容器的高度,滚动条才显示。 当内容增长时,将显示滚动条,从而减少内容的可用空间。 :::window ![scrollbar gutter](/images/scrollbar/scrollbar-gutter-2.jpg) ::: 可以看到,当内容过长出现滚动条时,内容会发生偏移。 这是由于浏览器为滚动条保留了一个空间,导致内容空间收到挤压变小。 但幸运的是,现在可以通过 [`scrollbar-gutter`](https://developer.mozilla.org/en-US/docs/Web/CSS/scrollbar-gutter) 属性来解决这个问题。它帮助为滚动条提前预留足够的空间。 它的默认值为 `auto`,可选值有 `stable` 和 `both-edges` 。 ```css .box { padding: 1rem; max-height: 220px; overflow-y: auto; scrollbar-gutter: stable; } ``` :::window ![scrollbar gutter](/images/scrollbar/scrollbar-gutter-3.jpg) ::: 当内容增加时,就不会影响布局的空间变化,因为浏览器已经为 滚动条预留了空间。 :::window ![scrollbar gutter](/images/scrollbar/scrollbar-gutter-4.jpg) ::: 好消息是,`scrollbar-gutter` 的兼容性,从 `Chrome@94` 就开始得到了支持。 #### 新语法浏览器兼容 @[caniuse](mdn-css_properties_scrollbar-width) ## 自定义滚动条的使用范围 有一点需要考虑的,我们的 自定义滚动条,它应该在哪里生效。 是希望所有的 可滚动的元素都应用 自定义滚动条,还是只有特定的元素应用自定义滚动条呢。 ### 所有可滚动元素 对于 旧的语法, 想要使所有 可滚动元素都 生效,我们可以直接编写 选择器,而无需将它们附加到元素。 ```css ::-webkit-scrollbar { width: 10px; } ::-webkit-scrollbar-track { background-color: darkgrey; } ::-webkit-scrollbar-thumb { box-shadow: inset 0 0 6px rgba(0, 0, 0, 0.3); } ``` 而对于新语法,只需要将它们 应用于 `` 元素即可 ```css html { scrollbar-color: #6969dd #e0e0e0; scrollbar-width: thin; } ``` ### 特定可滚动元素 对于 旧的语法,想要使特定的 可滚动元素生效,我们在特定元素之后编写 选择器。 ```css .container::-webkit-scrollbar { width: 10px; } .container::-webkit-scrollbar-track { background-color: darkgrey; } .container::-webkit-scrollbar-thumb { box-shadow: inset 0 0 6px rgba(0, 0, 0, 0.3); } ``` 对于新语法,也是是相同的。 ```css .container { scrollbar-color: #6969dd #e0e0e0; scrollbar-width: thin; } ``` ## 设计自定义滚动条 在深入研究 自定义滚动条之前,首先需要了解 默认的滚动条的样式。 默认的滚动条在 不同的操作系统之中是不同的。 在 MacOS Safari 中, Track 两侧都有边框, 背景色为纯色,Thumb 是圆形的,左右两侧都有空间。 :::window ![scrollbar use case](/images/scrollbar/use-case-1.jpg) ::: 而在 MacOS Chrome 中,Track 是透明的,`Thumb` 是原型的,而且整个滚动条只在滚动时才显示,且不占据空间。 在 Windows 中,Track 是 灰色背景,Thumb 是 矩形的。 ::: window ![scrollbar use case](/images/scrollbar/use-case-1-2.jpg) ::: ### 示例1 以下是根据上面的模型,自定义的滚动条 ```css .container::-webkit-scrollbar { width: 16px; } .container::-webkit-scrollbar-track { background-color: #e4e4e4; border-radius: 100px; } .container::-webkit-scrollbar-thumb { background-color: #d4aa70; border-radius: 100px; } ``` 为 `Track` 和 `Thumb` 添加 `border-radius` 是必要的,因为 `border-radius` 无法在 `::-webkit-scrollbar` 上生效。 :::window gap=0 如果是使用的 新的语法,我们不能调整 滚动条的宽度,能做的事情只有设置 `Track` 和 `Thumb` 的颜色: ```css .container { scrollbar-color: #d4aa70 #e4e4e4; } ``` *** > \[!warning] > 以下示例仅适用于 `webkit` 内核的浏览器。对于实际项目,你还可以同时添加新的语法支持 `Firefox`。 ### 示例2:阴影+渐变 在这个示例中,我们给滚动条添加了 阴影 和 渐变。来看看效果如何: ```css .container::-webkit-scrollbar-thumb { background-image: linear-gradient(180deg, #d0368a 0%, #708ad4 99%); box-shadow: inset 2px 2px 5px 0 rgba(#fff, 0.5); border-radius: 100px; } ``` :::window gap=0 title="渐变" ### 示例3: 带边框 我们还可以为 `Track` 和 `Thumb` 添加 边框,这可以帮助我们解决一些棘手的设计。 ```css .container::-webkit-scrollbar-thumb { border-radius: 100px; background: #8070d4; border: 6px solid rgba(0, 0, 0, 0.2); } ``` :::window gap=0 基于相同的示例,我们还可以调整 `Thumb` 的 边框,获得一些有趣的效果。 ```css .container::-webkit-scrollbar-thumb { border-radius: 100px; background: #8070d4; border: 6px solid rgba(0, 0, 0, 0.2); border-left: none; border-right: none; } ``` :::window gap=0 ### 示例4:Thumb 带间隔 在此示例中,我们希望 `Thumb` 的四周与 `Track` 都带有一定的间隔。 由于它无法与 滚动条一起使用 `padding`。 因此我们需要使用 `border` 和 `background-clip` 实现效果。 ```css .container::-webkit-scrollbar-thumb { border: 5px solid transparent; border-radius: 100px; background-color: #8070d4; background-clip: content-box; } ``` :::window gap=0 title="Thumb 带间隔" ## 增加 hover 效果 我们可以为 滚动条添加 `hover` 效果吗? 是的, 可以。我们可以为 新旧的语法添加 `hover` 效果。 ```css /* 旧语法 */ .section::-webkit-scrollbar-thumb:hover { background-color: #5749d2; } /* 新语法 */ .section { scrollbar-color: #d4aa70 #e4e4e4; transition: scrollbar-color 0.3s ease-out; } .section:hover { scrollbar-color: #5749d2; } ``` 同时,在使用新语法上,我们还可以添加 过渡效果,但是在 旧语法 上则不支持。 :::window gap=0 title="hover 效果" ## 在需要时显示滚动条 通过向 `overflow` 属性添加值以外的 `visible` 值,可以创建可滚动元素。 建议使用关键字, `auto` 因为它只会在内容超出其容器时显示滚动条。 ```css .container { overflow: auto; } ``` --- --- url: /article/4nop90ge/index.md --- # 浏览器指纹 在当今互联网环境中,用户隐私保护日益受到关注,而**浏览器指纹**技术作为网站识别用户的重要手段,既带来了便利也引发了隐私担忧。本文将深入探讨浏览器指纹的工作原理、技术实现以及防护策略。 ## 什么是浏览器指纹? 浏览器指纹是通过收集用户浏览器和设备的各类信息,组合成一个**唯一标识符**的技术。就像人类的指纹一样,这个数字指纹能够以极高的准确率识别和追踪特定用户。 :::info 核心概念 浏览器指纹不是传统意义上的Cookie,它无需在用户设备上存储任何数据,而是通过分析浏览器特征来创建用户画像。 ::: ## 浏览器指纹的构成要素 ### 1. 基础信息组件 ```javascript // 获取基础浏览器指纹信息 function getBasicFingerprint() { return { userAgent: navigator.userAgent, language: navigator.language, platform: navigator.platform, screenResolution: `${screen.width}x${screen.height}`, colorDepth: screen.colorDepth, timezone: new Intl.DateTimeFormat().resolvedOptions().timeZone, hardwareConcurrency: navigator.hardwareConcurrency, deviceMemory: navigator.deviceMemory || 'unknown' } } ``` ### 2. 高级指纹技术 #### Canvas 指纹 ```javascript function generateCanvasFingerprint() { const canvas = document.createElement('canvas') const ctx = canvas.getContext('2d') // 绘制文本和图形 ctx.textBaseline = 'top' ctx.font = '14px Arial' ctx.fillText('Browser fingerprint test', 2, 2) // 返回Canvas数据哈希 return hashCanvasData(canvas.toDataURL()) } ``` #### WebGL 指纹 ```javascript async function getWebGLFingerprint() { const canvas = document.createElement('canvas') const gl = canvas.getContext('webgl') || canvas.getContext('experimental-webgl') if (!gl) return null const debugInfo = gl.getExtension('WEBGL_debug_renderer_info') return { vendor: gl.getParameter(debugInfo.UNMASKED_VENDOR_WEBGL), renderer: gl.getParameter(debugInfo.UNMASKED_RENDERER_WEBGL), // 其他WebGL参数... } } ``` #### 音频指纹 ```javascript function getAudioFingerprint() { const audioContext = new (window.AudioContext || window.webkitAudioContext)() const oscillator = audioContext.createOscillator() const analyser = audioContext.createAnalyser() oscillator.connect(analyser) oscillator.start() // 分析音频信号特征 const data = new Float32Array(analyser.frequencyBinCount) analyser.getFloatFrequencyData(data) return hashAudioData(data) } ``` ## 浏览器指纹的独特性分析 :::code-tabs @tab 指纹组合示例 ```javascript const fingerprint = { // 用户代理信息 userAgent: 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36', // 屏幕特性 screen: '1920x1080@24bit', // 插件列表 plugins: ['Chrome PDF Viewer', 'Chrome PDF Plugin'], // 字体列表 fonts: ['Arial', 'Times New Roman', 'Verdana'], // 时区和语言 timezone: 'Asia/Shanghai', language: 'zh-CN' } ``` @tab 唯一性计算 ```javascript function calculateUniqueness(fingerprint) { // 基于信息熵计算指纹唯一性 const entropyBits = Object.values(fingerprint) .map(value => calculateEntropy(value)) .reduce((sum, entropy) => sum + entropy, 0) return 2 ** entropyBits // 可能的组合数量 } ``` ::: ## 实际应用场景 ### 1. 反欺诈系统 ```javascript class FraudDetection { constructor() { this.fingerprint = this.collectFingerprint() } detectSuspiciousActivity() { const currentFp = this.collectFingerprint() const previousFp = this.getStoredFingerprint() // 检测指纹变化模式 if (this.hasRapidFingerprintChanges(currentFp, previousFp)) { this.flagForReview() } } } ``` ### 2. 个性化体验 ```javascript function enhanceUserExperience() { const fingerprint = getDeviceFingerprint() // 根据设备能力优化体验 if (fingerprint.hardwareConcurrency > 4) { enableAdvancedFeatures() } // 根据屏幕尺寸调整布局 adjustLayoutForScreen(fingerprint.screenResolution) } ``` ## 隐私保护与应对策略 ### 1. 浏览器内置防护 现代浏览器提供了多种防护机制: :::steps * **Firefox**:通过 `privacy.resistFingerprinting` 配置项提供指纹防护 * **Chrome**:正在开发 Privacy Sandbox 技术限制指纹追踪 * **Safari**:智能防跟踪预防(ITP)技术 * **Tor Browser**:标准化用户代理和屏幕尺寸 ::: ### 2. 用户防护措施 ```javascript // 使用浏览器扩展防护示例 class FingerprintProtection { static methods = { canvasNoise: () => this.injectCanvasNoise(), fontSpoofing: () => this.spoofFontList(), webglMasking: () => this.maskWebGLInfo() } static injectCanvasNoise() { // 为Canvas添加随机噪声 const originalMethod = HTMLCanvasElement.prototype.toDataURL HTMLCanvasElement.prototype.toDataURL = function () { const ctx = this.getContext('2d') // 添加微小随机像素 this.addRandomNoise(ctx) return originalMethod.call(this) } } } ``` ### 3. 开发者伦理指南 :::warning 重要提醒 开发者在实现指纹技术时应: * 明确告知用户数据收集目的 * 提供选择退出机制 * 遵循数据最小化原则 * 遵守GDPR、CCPA等隐私法规 ::: ## 技术发展趋势 ### 1. 联邦学习与差分隐私 ```javascript // 使用差分隐私的指纹处理 class DifferentialPrivacyFingerprint { addLaplaceNoise(sensitivity, epsilon) { // 添加拉普拉斯噪声保护隐私 const noise = this.generateLaplaceNoise(sensitivity / epsilon) return this.fingerprintData + noise } generateAnonymousFingerprint() { // 生成匿名化指纹标识 return this.hashFingerprint( this.addLaplaceNoise(this.fingerprintData) ) } } ``` ### 2. 隐私增强技术(PETs) ```javascript // 零知识证明应用示例 class ZeroKnowledgeFingerprint { async generateProof(fingerprint) { // 生成证明而不泄露具体指纹信息 const proof = await zkSnark.generateProof( fingerprint, this.verificationKey ) return proof } verifyWithoutRevealing(proof) { // 验证用户身份而不获取具体指纹 return zkSnark.verify(proof, this.verificationKey) } } ``` ## 总结 浏览器指纹技术是一把双刃剑: **积极方面**: * \==增强安全性=={.success},防止账户盗用和欺诈 * \==改善用户体验=={.success},提供个性化服务 * \==业务分析=={.success},理解用户行为模式 **挑战方面**: * \==隐私风险=={.warning},用户可能被无感知追踪 * \==法规合规=={.warning},需要遵守日益严格的隐私法规 * \==技术滥用=={.caution},可能被用于不正当目的 ### 最佳实践建议 1. **对用户**:使用隐私保护浏览器和扩展,定期清理浏览器数据 2. **对开发者**:实施隐私设计原则,最小化数据收集 3. **对企业**:建立透明的数据使用政策,尊重用户选择 随着技术发展和法规完善,浏览器指纹技术将在**隐私保护**和**功能需求**之间寻找更好的平衡点。 *** **参考**: * [W3C Privacy Interest Group](https://www.w3.org/Privacy/) * [Electronic Frontier Foundation - Panopticlick](https://panopticlick.eff.org/) * [Mozilla Developer Network - Fingerprinting](https://developer.mozilla.org/en-US/docs/Glossary/Fingerprinting) ::: important 保护用户隐私,共建可信网络环境 🔒 ::: --- --- url: /article/4sfcfmws/index.md --- ## 理解 Git Rebase Git rebase(变基)是 Git 版本控制系统中一个功能强大但需要谨慎使用的工具,它允许开发者重新整理提交历史。简而言之,rebase 能够将一系列提交从一个分支“移植”到另一个分支,并在此过程中重新组织提交记录。 ### 核心概念解析 假设你正在开发一个新功能,从主分支(main)创建了一个特性分支(feature)。在开发过程中,主分支上产生了新的提交。此时,你面临两个选择: * **Merge(合并)**:保留两个分支的完整历史,创建一个合并提交 * **Rebase(变基)**:将特性分支的提交“重放”到主分支的最新提交之上 ## Git Rebase 的核心应用场景 ### 1. 维护清晰的提交历史 ```bash # 在特性分支上执行 git rebase main ``` 此命令将特性分支的所有提交重新应用到主分支的最新提交上,形成一条线性的提交历史。 ### 2. 交互式提交管理 ```bash # 交互式 rebase,编辑最近3个提交 git rebase -i HEAD~3 ``` 交互式 rebase 支持以下操作: * 重新排列提交顺序 * 合并多个提交 * 编辑提交信息 * 拆分提交内容 * 删除指定提交 ### 3. 解决分支分叉问题 当多个开发者协作于同一分支时,rebase 有助于维护线性的提交历史。 ## Git Rebase 实战指南 ### 基础操作 #### 1. 特性分支变基到主分支 ```bash # 切换到特性分支 git checkout feature-branch # 获取远程最新变更 git fetch origin # 变基到主分支 git rebase origin/main ``` #### 2. 交互式变基操作 ```bash # 编辑最近5个提交 git rebase -i HEAD~5 ``` 编辑器将显示类似内容: ```txt pick a1b2c3d 添加用户登录功能 pick e4f5g6h 修复登录bug pick h7i8j9k 添加用户注册 pick k0l1m2n 优化表单验证 pick n3o4p5q 添加密码重置功能 ``` 可用的操作命令: * `pick`:保留提交 * `reword`:修改提交信息 * `edit`:修改提交内容 * `squash`:合并到前一个提交 * `fixup`:合并并丢弃提交信息 * `drop`:删除提交 ### 3. 冲突处理策略 rebase 过程中遇到冲突时: ```bash # 1. 解决冲突文件 # 2. 添加已解决的文件 git add <冲突文件> # 3. 继续 rebase 过程 git rebase --continue # 如需取消 rebase 操作 git rebase --abort ``` ## Git Rebase 使用注意事项 ### ⚠️ 核心原则:避免对已推送提交进行变基 **绝对不要**对已经推送到远程仓库的提交执行 rebase,除非你确认没有其他协作者在此分支上工作。 ```bash # ❌ 危险操作:对已推送提交执行 rebase git push origin feature-branch git rebase main # 这会重写历史,引发协作问题 # ✅ 安全操作:在推送前执行 rebase git rebase main git push origin feature-branch ``` ### 其他关键注意事项 1. **分支备份**:执行复杂 rebase 前创建备份分支 2. **小步提交**:保持提交的原子性,每次只完成一个小改动 3. **功能验证**:rebase 完成后务必验证代码功能 4. **团队协调**:在团队项目中建立统一的 rebase 使用规范 ## Git Rebase 与 Git Merge 深度对比 ### 工作机制分析 #### Merge(合并) ```bash # 创建合并提交,保留完整历史 git checkout main git merge feature-branch ``` 特点: * 生成新的合并提交 * 完整保留两个分支历史 * 历史呈现树状结构 #### Rebase(变基) ```bash # 重写历史,创建线性记录 git checkout feature-branch git rebase main git checkout main git merge feature-branch ``` 特点: * 重写提交历史 * 创建线性提交记录 * 不产生额外合并提交 ### 历史记录可视化对比 **Merge 后的历史结构:** ```txt * Merge branch 'feature' |\ | * Feature commit 3 | * Feature commit 2 | * Feature commit 1 * | Main commit 2 * | Main commit 1 |/ * Base commit ``` **Rebase 后的历史结构:** ```txt * Feature commit 3 * Feature commit 2 * Feature commit 1 * Main commit 2 * Main commit 1 * Base commit ``` ## Git Rebase 的优势与局限 ### 核心优势 #### 1. 清晰的历史记录 * 线性历史更易阅读和理解 * 避免复杂的合并提交 * 便于使用 `git bisect` 进行问题追踪 #### 2. 提升代码审查效率 * 每个提交都是独立完整的单元 * 便于按功能模块审查代码 * 减少合并冲突干扰 #### 3. 灵活的历史管理 * 自由调整提交顺序 * 合并相关小提交 * 修正提交信息错误 ### 潜在风险 #### 1. 历史重写风险 * 可能丢失重要历史信息 * 对已推送提交变基会破坏团队协作 #### 2. 学习成本较高 * 初学者容易误用 * 需要深入理解 Git 内部机制 #### 3. 冲突处理复杂 * 可能在每个提交点遇到冲突 * 需要重复解决冲突 ## 最佳实践指南 ### 1. 个人分支管理策略 ```bash # 推送前整理本地提交 git rebase -i HEAD~3 # 整理最近3个提交 git push origin feature-branch ``` ### 2. 团队协作规范 * 仅在个人特性分支使用 rebase * 主分支和开发分支采用 merge 策略 * 建立团队统一的 rebase 使用规范 ### 3. 实用工作流示例 ```bash # 完整工作流演示 git checkout -b feature/login # 进行功能开发,完成多次提交... # 准备推送代码 git fetch origin git rebase origin/main # 处理可能出现的冲突 git rebase --continue # 推送到远程仓库 git push origin feature/login ``` ## 总结与展望 Git rebase 是一个功能强大的工具,但需要谨慎使用。掌握 rebase 的关键要点: 1. **理解机制**:深入理解 rebase 如何重写提交历史 2. **遵守规范**:严格避免对已推送提交执行变基 3. **持续实践**:在个人项目中积累使用经验 4. **团队协作**:建立统一的工作流标准 正确使用 rebase 能够帮助我们维护清晰、整洁的提交历史,提升代码审查效率,是现代 Git 工作流中的重要工具。 谨记:**能力越大,责任越大**。在享受 rebase 带来的便利时,必须时刻警惕其潜在风险。 *** *推荐学习资源:* * [Pro Git 书籍 - Rebasing 章节](https://git-scm.com/book/en/v2/Git-Branching-Rebasing) * [Git 官方文档 - git-rebase](https://git-scm.com/docs/git-rebase) * [GitHub 学习实验室 - Git 工作流](https://lab.github.com/) --- --- url: /article/4v4g4vmb/index.md --- 在 Node.js 开发中,经常需要在不同项目间切换不同版本的 Node.js。多版本管理器应运而生,让我们能够轻松安装、切换和管理多个 Node.js 版本。本文将详细介绍目前主流的四种工具:n、nvm、fnm 和 volta。 ## 1. n ### 安装 ```bash # 使用 npm 安装 npm install -g n # 或者使用官方脚本 curl -L https://bit.ly/n-install | bash ``` ### 基本使用 ```bash # 安装最新的稳定版 n latest # 安装最新的 LTS 版本 n lts # 安装特定版本 n 18.12.1 # 查看已安装版本 n # 删除版本 n rm 14.17.0 # 查看所有远程版本 n ls-remote ``` ### 功能特点 * **简单易用**:命令直观,学习成本低 * **直接覆盖**:通过替换二进制文件实现版本切换 * **快速安装**:下载预编译的二进制包 ### 优缺点 **优点:** * 安装和使用极其简单 * 不需要修改环境变量 * 切换速度快 **缺点:** * 官方不支持 Windows * 全局包在不同版本间不隔离 * 版本切换可能不够灵活 ## 2. nvm (Node Version Manager) ### 安装 ```bash # Linux/macOS 安装 curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.4/install.sh | bash # 或者使用 wget wget -qO- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.4/install.sh | bash # Windows 用户使用 nvm-windows # 下载地址:https://github.com/coreybutler/nvm-windows/releases ``` ### 基本使用 ```bash # 安装指定版本 nvm install 18.12.1 # 安装最新 LTS nvm install --lts # 使用特定版本 nvm use 16.18.0 # 设置默认版本 nvm alias default 18.12.1 # 查看已安装版本 nvm ls # 查看远程可用版本 nvm ls-remote # 在当前目录创建 .nvmrc 文件 echo "18.12.1" > .nvmrc # 然后运行 nvm use ``` ### 功能特点 * **完全隔离**:每个版本有独立的全局包 * **项目级配置**:支持 .nvmrc 文件 * **跨平台**:有专门的 Windows 版本 ### 优缺点 **优点:** * 成熟的生态系统 * 完整的版本隔离 * 良好的项目集成 * 社区支持强大 **缺点:** * 启动速度相对较慢 * 不同 shell 需要重新加载 * Windows 版本功能有限 ## 3. fnm (Fast Node Manager) ### 安装 ```bash # 使用安装脚本 curl -fsSL https://fnm.vercel.app/install | bash # 使用 Homebrew (macOS) brew install fnm # 使用 Scoop (Windows) scoop install fnm # 使用 Cargo cargo install fnm ``` ### 基本使用 ```bash # 安装 Node.js fnm install 18.12.1 # 使用版本 fnm use 18.12.1 # 设置默认版本 fnm default 18.12.1 # 列出所有版本 fnm list # 配置自动版本切换 # 在 shell 配置文件中添加 eval "$(fnm env --use-on-cd)" ``` ### 功能特点 * **极速性能**:Rust 编写,启动速度快 * **自动检测**:支持 .node-version 和 .nvmrc 文件 * **跨平台支持**:完整的 Windows 支持 ### 优缺点 **优点:** * 极快的启动速度 * 现代化的架构 * 良好的跨平台支持 * 自动版本检测 **缺点:** * 相对较新,生态系统不如 nvm 成熟 * 某些高级功能可能缺失 ## 4. volta ### 安装 ```bash # 一键安装 (Linux/macOS) curl https://get.volta.sh | bash # Windows # 下载安装器:https://volta.sh/ # 使用 Homebrew brew install volta ``` ### 基本使用 ```bash # 安装 Node.js volta install node@18.12.1 # 查看当前工具链 volta list # 固定项目 Node.js 版本 volta pin node@18 # 安装全局包 volta install prettier # 查看当前工具版本 volta which node ``` ### 功能特点 * **项目级锁定**:自动管理项目特定版本 * **工具链管理**:同时管理 Node.js、npm、Yarn * **无感知切换**:进入项目目录自动切换版本 * **跨平台一致**:统一的跨平台体验 ### 优缺点 **优点:** * 优秀的项目版本管理 * 工具链完整管理 * 自动版本切换 * 优秀的性能 **缺点:** * 学习曲线相对陡峭 * 对现有工作流改变较大 ## 5. 详细对比分析 ### 性能对比 | 工具 | 启动速度 | 内存占用 | 安装速度 | | ----- | -------- | -------- | -------- | | n | 快 | 低 | 快 | | nvm | 慢 | 中 | 中 | | fnm | 很快 | 低 | 快 | | volta | 快 | 中 | 中 | ### 功能对比 | 功能 | n | nvm | fnm | volta | | ------------ | ---- | --- | --- | ------ | | Windows 支持 | ❌ | ✅ | ✅ | ✅ | | 自动版本切换 | ❌ | ✅ | ✅ | ✅ | | 全局包隔离 | ❌ | ✅ | ✅ | ✅ | | 多工具管理 | ❌ | ❌ | ❌ | ✅ | | 项目配置文件 | ❌ | ✅ | ✅ | ✅ | | 二进制管理 | ❌ | ❌ | ❌ | ✅ | ### 生态系统成熟度 * **nvm**: ⭐⭐⭐⭐⭐ (最成熟,社区支持最好) * **n**: ⭐⭐⭐⭐ (简单可靠,历史悠久) * **volta**: ⭐⭐⭐⭐ (功能丰富,官方推荐) * **fnm**: ⭐⭐⭐ (新兴工具,快速发展) ## 6. 选择建议 ### 根据使用场景选择 **个人开发者/初学者:** * 推荐:**n** 或 **fnm** * 理由:简单易用,学习成本低 **团队项目/企业环境:** * 推荐:**volta** 或 **nvm** * 理由:版本锁定严格,协作友好 **Windows 用户:** * 推荐:**fnm** 或 **volta** * 理由:完整的 Windows 支持 **性能敏感用户:** * 推荐:**fnm** * 理由:极快的启动速度 **全栈工具链管理:** * 推荐:**volta** * 理由:完整的工具链管理 ### 迁移建议 ```bash # 从 nvm 迁移到 fnm nvm ls > versions.txt # 然后使用 fnm 逐个安装列出的版本 # 从 n 迁移到 volta # volta 会自动检测现有安装,无需特殊迁移 ``` ## 7. 最佳实践 ### 项目版本配置 ```bash # .nvmrc (nvm/fnm) 18.12.1 # package.json (volta) { "volta": { "node": "18.12.1", "npm": "9.1.0" } } ``` ### CI/CD 集成 ```yaml # GitHub Actions 示例 - name: Setup Node.js uses: actions/setup-node@v3 with: node-version-file: .nvmrc # 或者使用 fnm - name: Install fnm run: curl -fsSL https://fnm.vercel.app/install | bash - name: Install Node.js run: fnm use ``` ## 总结 选择合适的 Node.js 版本管理器取决于你的具体需求: * **追求简单**:选择 **n** * **需要稳定性**:选择 **nvm** * **追求性能**:选择 **fnm** * **需要完整工具链**:选择 **volta** 无论选择哪个工具,重要的是保持团队一致性,并在项目中正确配置版本约束文件,这样才能确保开发环境的一致性。 ## 延伸资源 * [n 官方文档](https://github.com/tj/n) * [nvm 官方文档](https://github.com/nvm-sh/nvm) * [fnm 官方文档](https://github.com/Schniz/fnm) * [volta 官方文档](https://volta.sh/) 希望本文能帮助你选择最适合的 Node.js 版本管理工具! --- --- url: /article/5fmy4kla/index.md --- # WebComponent——template 在web开发领域中,模板并不少见。从服务器端的模板语言,如`Django`、`jsp`等,应用十分广泛,存在了很长时间。又如前端,早期例如`art(artTemplate)`,以及近年来,大多数的MV\*框架涌现,绝大多数在展现层使用了同样的渲染机制:模板。 > **定义** > 模板,一个拥有预制格式的文档或者文件,可作为特定应用的出发点,这样就避免在每次使用格式的时候都重复创建。 从模板的定义中,我们可以发现,“避免在每次使用格式的时候重复创建”,从这句话来看,模板可以让我们避免重复的工作。那么,web平台有没有提供原生支持呢? 答案是,有,在 [WhatWG HTML 模板规范](https://html.spec.whatwg.org/multipage/scripting.html#the-template-element)中,它定义了一个新的`