生物信息学学习笔记：第 1 章 绪论

0. PDF 内容检查

1. 书名 / 章 / 节 / 小节结构

• 书名：生物信息学（第二版）（中文教材，配套有《生物信息学实验指导》）
• 章标题：第 1 章 绪论
• 节与小节结构（严格按 PDF 顺序）：
  • 第一节 生物信息与生物信息学
    • 一、迅速增长的生物信息
    • 二、生物信息学概念
  • 第二节 生物信息学历史与展望
    • 一、发展简史
    • 二、应用领域
    • 三、学科展望
  • 习题（5 题）
  • 历史与人物：“bioinformatics”之名的由来（Paulien Hogeweg / 林华安 Hwa A. Lim）

2. PDF 页与印刷页对应

• PDF 共 15 页，对应教材印刷页码 第 1～15 页（页脚可见“第 1 章 绪论 1/2/3…”与“生物信息学 2/4/6…”交替，为奇偶页页眉页脚）。对应关系基本 1:1。

3. 缺页 / 重复 / 乱码 / OCR 错误

• 无明显缺页，章节从开头到习题、历史人物完整。
• 存在少量 OCR/排版小瑕疵：
  • 图 1.1 的坐标轴数字（14/12/10…）与图注被打散夹在正文里，图本身无法从文本还原，只能读文字说明。
  • 个别外文拼写按原文保留（如 “Fleischman” 应为 Fleischmann、“Ensemble” 应为 Ensembl、“Neighbour-Joining”），这些是教材/OCR 层面的小笔误，我在术语表会给出正确写法。
  • “kisac.ki.se，现为 www.bea.ki.se” 一句被排到图 1.2 描述前面（排版跨页所致），不影响理解。

4. 图表公式可识别性

• 图 1.1～1.7 只能读到文字标题和说明，图像内容（曲线、漫画、网页截图）无法从文本判读。
• 表 1.1（学科发展主要事件）、表 1.2（高被引论文）文本完整可读，是本章最有价值的可提取信息。
• 本章无任何数学公式。

5. 是否完整章节：是，绪论完整。

6. 缺失上下文：本章多次以“详见第 2/3/4 章”“附录 2”指向后续内容（数据类型、数据库、序列联配、系统发生等），这些属于后续章节，不在本 PDF 中。

1. 本节定位与知识地图

1. 本章解决什么问题
回答三个入门问题：①什么是生物信息（biological information）以及它为何爆炸式增长；②什么是生物信息学（bioinformatics）这门学科；③它从哪来、往哪去（历史、应用、展望、就业、我国发展）。

2. 在全书与整个学科体系中的位置
它是全书的“地图与导言”：先建立“数据海洋”的世界观和学科边界，再由后续章节逐一展开数据类型（第 2 章）、数据库（第 3 章）、序列联配（第 4 章）等。

3. 属于哪个子领域：学科概论 / 学科史，不属于任何具体计算子领域。

4. 在真实研究 pipeline 中的位置：不对应任何 pipeline 步骤。它是“为什么要有 pipeline”的动机层。

5. 上游输入 / 6. 下游分析：不适用（无数据流）。可类比理解为：上游是“测序技术产生海量数据”，下游是“本书后续所有分析方法”。

7. 与其他章节 / 实验指导的对应

• 与主教材：第 2 章（数据类型）、第 3 章（数据库、Dayhoff）、第 4 章（序列联配、Waterman）、进化分析章（Sankoff、NJ、自举法）均在本章被点名预告。
• 与《实验指导》：本章本身无配套实验，但它列出的工具（BLAST、ClustalW、ORF finder、HMMER、FGENESH、NCBI/EBI 在线服务）正是后续实验的主角。

前置知识

• 生物学：中心法则（DNA→RNA→蛋白质）、碱基与氨基酸、基因/基因组的基本概念。
• 数学统计：本章几乎不需要；仅需理解“数据量指数增长/翻番”这类直觉。
• 算法/数据结构：无硬性要求；了解“动态规划、图论”是名词即可（后续章节才展开）。
• 编程工具：无；但本章明确建议未来要会 命令行 + Python/Perl + C/C++，会用 Unix/Linux。

知识结构树

1
2
3
4
5
6
7
8
9
10
11
12

绪论（生物信息学是什么）
├── 生物学问题：如何管理/解读/使用爆炸增长的生物数据
├── 核心对象：生物信息（核酸/蛋白序列、结构、表达、通路…）
│   ├── 初级数据库 primary（原始序列/结构）
│   └── 二级数据库 secondary（domain、二级结构、疏水位点…）
├── 学科定义：分子生物学 + 遗传学 + 计算机科学
│   ├── 三大内容：新算法/统计；数据分析解释；数据管理工具
│   └── 研究范式：假设—实验（数据库搜索=一次“实验”）
├── 历史四阶段：萌芽/形成/基因组与互联网/高通量测序
├── 应用领域：序列分析、基因预测、拼接、结构预测、进化、精准医疗…
├── 平民化桥梁：Windows 软件 + 在线 Web 服务（SSS/MSA/BSA）
└── 展望：从"积累数据"转向"解读数据"；大数据/AI/合成生物学/就业

2. 按教材顺序精读

第一节 · 一、迅速增长的生物信息 【应该理解】

1. 要回答的问题：生物信息指什么？增长有多快？
2. 主要内容：生物信息包含分子序列（核酸/蛋白）、蛋白二级/三维结构等；原始数据构成初级数据库，分析衍生数据构成二级数据库；核酸库数据约每 14 个月翻一番。
3. 核心结论：数据爆炸 → 催生“如何有效管理、准确解读、充分使用”的新需求。
4. 重要术语：初级数据库(primary database)、二级数据库(secondary database)、功能区/结构域(domain)、WGS。
5. 数据（作为素材）：DNA 字母表 {A,T,G,C}；蛋白 20 个氨基酸字母；GenBank 2000 年底 >100 亿 bp，2020 年 4 月 4158 亿 bp（+WGS 7.8 万亿 → 合计约 8.2 万亿 bp / 14.8 亿条）。
6. 方法：无（描述性）。
7. 易错点：“每 14 个月翻一番”是核酸库的历史经验值，不同来源/年份数字不同（人类基因组测序另有“每 5–7 个月翻番”）——不要当作精确定律。
8. 前后关系：为下一小节“为何需要一门新学科”做铺垫。
9. 页码/图：印刷 p.1–2，图 1.1（GenBank/WGS 增长曲线）。

第一节 · 二、生物信息学概念 【必须掌握】

1. 要回答的问题：生物信息学是什么？
2. 主要内容：一般定义=研究生物信息的采集、处理、存储、传播、分析、解释；三大组成部分=①新算法与统计方法；②数据分析与解释；③数据管理利用工具。引用 Claverie(2000)、Wikipedia 定义。研究范式=假设—实验（如“该序列在库中无同源序列”是无效假设，数据库搜索就是一次验证实验）。
3. 核心结论：生物信息学不是“移植信息学技术到生物学”的纯应用技术，而是有丰富科学内涵、有大量未解科学问题（生物学的+计算的）的独立学科。
4. 重要术语：bioinformatics、假设—实验模式、无效假设。
5. 方法/数据：无。
6. 易错点：两个常见误解——“人人可做/不花钱/软件都免费”与“只是敲键盘写论文”。教材明确反驳：需算力投入、需实验验证、需想象力。
7. 前后关系：给出全书立场（学科定位），承上（数据爆炸）启下（历史）。
8. 页码/图：p.2–4，图 1.2（早期“路线图”）、图 1.3（NCBI 在线工具网页）。

第二节 · 一、发展简史 【应该理解 + 部分必须掌握】

1. 要回答的问题：这门学科怎么来的？关键里程碑有哪些？
2. 主要内容：起源可追溯到 1960s；术语最早由 Paulien Hogeweg (1978) 提出（“the study of informatic processes in biotic systems”），另一说 1990 年由 林华安 (Hwa A. Lim) 提出并办首届会议。学科奠基人：Margaret Dayhoff、Michael Waterman、David Sankoff。四阶段划分（必须掌握）：①萌芽期(1960s–70s，Dayhoff 替换矩阵、Needleman-Wunsch)；②形成期(1980s，分子数据库+BLAST/FASTA)；③基因组与互联网期(1990s–2005，基因组测序、Phred-Phrap-Consed、在线数据库)；④高通量测序期(2005 至今，NGS/三代)。
3. 核心结论：最核心的算法在 1960–70s 就已奠基（序列联配是最基本内容），之后是不断改进。
4. 重要术语：替换矩阵、Needleman-Wunsch、Smith-Waterman、BLAST/FASTA、Phred-Phrap-Consed、NGS。
5. 数据：表 1.1（发展大事记）——本章最值得记的干货。
6. 易错点：术语“谁最早提出”有两种说法（Hogeweg 1978 vs Lim 1990），教材两者并存；别只记一个。
7. 前后关系：承接“学科定位”，为“应用/展望”提供时间脉络。
8. 页码/表：p.4–7，表 1.1。

第二节 · 二、应用领域 【应该理解】

1. 问题：生物信息学有什么用？入门者能做什么？
2. 主要内容：Nature 高被引 100 篇中生物信息学（含系统发生）占 10 篇（表 1.2，含 ClustalW、BLAST、NJ、自举法、MEGA4、ModelTest、MrBayes 等）；“平民化”两条路——Windows 桌面软件 与 在线 Web 服务；EBI 把在线平台分三类 SSS（序列搜索）/MSA（多序列联配）/BSA（序列分析）；NAR 每年 Database Issue（1993 起） 和 Web Server Issue（2004 起） 两大专刊是“两座桥梁”。给出“何时该找专业人员帮忙”的判据（>100 条序列、需 Linux、NGS、大规模芯片数据、复杂统计等）。
3. 核心结论：绝大多数生物学家日常工作集中在数据库搜索 + BLAST + ClustalW。
4. 术语：SSS、MSA、BSA、workflow management system、Database Issue、Web Server Issue。
5. 易错点：“在线服务方便”≠“适合所有场景”；超过一定规模/复杂度必须转向命令行与专业分析（本章已明说）。
6. 前后关系：把历史落到“今天能干嘛”，并引出展望。
7. 页码/表：p.8–9，表 1.2。

第二节 · 三、学科展望 【了解即可 + 少量必须掌握】

1. 问题：学科往哪走？我国现状？关键待解难题？就业？
2. 主要内容：研究重心从数据积累转向数据解读（图 1.4）；人类基因组测序数据每 5–7 个月翻番（图 1.5）；从“读懂基因组”走向“书写基因组/基因组社会化”（图 1.6）；我国机构与人物（北大 CBI、清华、NGDC/CNCB/CNGB、终身成就奖名单）；五大急需攻关技术（必须掌握其类别）：①大基因组从头组装；②基因组注释；③比较基因组与进化；④群体重测序变异检测(SNP/Indel/SV/CNV)；⑤RNA 分析。
3. 核心结论：大数据时代“产生 > 处理能力”，生物信息学是瓶颈也是马达；就业前景好但要求“生物学理解 + 编程 + 统计 + Linux + 沟通”。
4. 术语：de novo assembly、注释 annotation、SNP/Indel/SV/CNV、精准医疗、合成生物学、后基因组时代。
5. 易错点：图 1.5/1.6 的“预测曲线”是预测，教材已注明“实际增长超过预测”——别把预测当事实。
6. 前后关系：收束全章，指向后续章节的技术内容。
7. 页码/图：p.9–14，图 1.4–1.7。

习题 & 历史与人物 【了解即可】

• 习题 5 道（见第 14 节 G 我已整理并给参考答案思路）。
• 人物：Hogeweg（1978，理论生物学，迭代多序列联配、RNA 折叠预测）；林华安（1988 提 bio-informatique→bioinformatics，1990 办首会）。属背景故事。

3. 生物学问题到计算问题的映射

本章是导论，没有一个具体的计算任务可映射。但它反复给出了整个学科的“总链路直觉”，我据此给出学科级映射（而非某算法的映射）。

• 生物学对象：核酸/蛋白质序列、结构、表达、通路、群体变异。
• 不可直接观测的状态：基因功能、进化关系、调控机制、分子结构。
• 原始生物学问题：如何管理、解读、使用爆炸增长的生物数据。
• 实验技术测量：（测序等）——本章不展开，属后续章节。
• 计算任务归类（本章点名的学科任务，非本章实现）：序列搜索（BLAST）、序列比对/联配（NW/SW/ClustalW）、基因组拼装（assembly）、基因预测/分类（HMM、GENSCAN）、系统发生推断（NJ、MrBayes）、变异检测（SNP/SV）。
• 转换中丢失/推断的东西：本章的核心洞见是——生物信息学结论大多是“预测/估计”，是指示实验方向的“路灯”，最终仍需湿实验验证（“你最终还是需要具体的实验”）。

学科级链路（本章的世界观）：

1
2
3
4
5
6
7

生物学问题(功能/进化/机制)
→ 高通量实验(测序等)
→ 海量原始数据(primary database)
→ 计算方法(联配/搜索/拼接/预测/推断)
→ 衍生信息(secondary database: domain/结构…)
→ 生物学解释(预测=假设)
→ 湿实验验证

4. 数据对象、文件格式和 shape

本章不定义任何文件格式，也没有可给出 shape 的数据矩阵。为忠实原文，我只把本章**提到的“数据概念”**列出，并标注“具体格式见后续章节”。请不要把下表当作可直接编程的对象。

唯一可明确写出的“数据表示”直觉（本章反复强调）：

• 一批 DNA 序列：sequences ∈ {A,T,G,C,N}^(n × 变长)
• 一批蛋白序列：sequences ∈ {20 种氨基酸,X}^(n × 变长)

坐标系统、0/1-based、链方向、FASTA/FASTQ 结构等——本章均未涉及，属第 2–3 章。

5. 端到端数据处理流程

本章不适用（无 pipeline）。

它只给出了“学科级的宏观流程直觉”（见第 3 节链路图），以及一个重要的实践决策规则（值得记）：

何时从“在线服务/桌面软件”升级到“找专业人员 / Linux / 脚本 / workflow”：

• 序列数 > ~100
• 需要 Linux-only 软件
• 使用高通量测序数据
• 大规模数据（如芯片/表达矩阵）
• 数据结构/完整性有问题
• 需要复杂统计（多假设/前提/检验）

这条规则本身就是你未来搭建真实 pipeline 的“分流开关”。

6. 算法、统计模型和公式

本章不适用——无任何算法细节或公式。

但本章点名了后续要学的核心算法，先建立“待学清单”（都不在本章展开）：

7. 软件、数据库与工具

本章是“工具全景图”，非常适合建立总览。以下区分教材角色与现状。

教材实验偏向在线服务 + Windows；真实科研需补充：

• Linux 命令行版（如 blastn/blastp、mafft、hmmsearch、bwa mem、samtools、gatk）；
• 批量/脚本化（Bash + Python/R）；
• workflow（Nextflow / Snakemake / Galaxy）；
• 环境管理（conda/mamba、容器 Docker/Singularity）；
• HPC（SLURM 作业调度）。
• 本章给出的官方入口（部分可能变动，需要查证）：www.bea.ki.se（早期路线图）、bigd.big.ac.cn（NGDC）、www.bioinformatics.org。

8. 实验设计、QC、偏差与结果解释

本章无具体数据分析，故传统 QC 项目不适用。但它明确了一条方法论红线，值得抽成检查清单：

分析前检查清单（本章精神）

• 我是否清楚自己的无效假设是什么？（如“该序列无同源序列”）
• 数据规模/复杂度是否超过在线工具能力（>100 序列、NGS、需 Linux）？
• 我是否具备该问题的生物学背景知识（避免误解合作方需求）？

结果解释检查清单（本章反复强调）

• 我的结果是预测/估计还是观测事实？（生物信息学多为预测=“路灯”）
• 是否需要湿实验验证？（“你最终还是需要具体的实验”）
• 相关性是否被误当因果？

能/不能由本章支持的结论

• 能支持：学科定义、历史脉络、工具全景、方法论立场。
• 不能支持：任何具体数据的分析结论（本章无数据分析）。

9. 易混淆概念

10. Toy example

本章不适用（无可计算的方法）。

作为替代，给一个能手工完成的“字母表核对”小练习（源于本章唯一具体的“数据”——字母表）：

• 生物学背景：本章说 DNA=4 字符、蛋白=20 字符。
• 练习：教材列出的 20 个氨基酸单字母为
  A R N D C Q E G H I L K M F P S T W Y V
  → 数一数是否恰好 20 个？（答案：是，20 个）
• 反向核对：标准 20 种氨基酸单字母中未在 DNA 字母表出现的、也未被用作特殊符号的字母有哪些？（如 B、J、O、U、X、Z 不在标准 20 内；X 常表示未知氨基酸，N 常表示未知核苷酸）
• 意义：理解“alphabet”是后续所有序列算法的基础（打分矩阵、联配、搜索都建立在字母表上）。

最小项目目录（供你未来做真实实验时预先建立的规范，本章不产出文件）：

1
2
3
4
5
6
7

project/
├── raw_data/        # 原始序列（FASTA/FASTQ，后续章节）
├── reference/       # 参考基因组/注释
├── metadata/        # 样本信息
├── results/{qc,intermediate,final}/
├── scripts/         # Python/R/Bash
└── environment/     # conda env / Dockerfile

11. 从教学实验到真实科研

本章无配套实验，但它本身就在讨论“教学式在线工具 vs 真实科研”的差别，我据此整理：

本章要训练的能力：建立学科世界观 + 知道有哪些工具 + 明白“何时该升级到专业流程”。
真实项目必须补充：命令行技能、脚本化、版本与参数记录、统计设计、验证。

12. 与现代机器学习的联系

本章只在“展望/就业”中点到 AI、机器学习、数据挖掘、模式识别、文本挖掘、Hadoop/MySQL，作为“未来趋势与就业技能”，没有任何可建模的数据或标签。

• 是否适合把本章内容做成 ML 任务：不适用。
• 唯一可记的联系（学科层面）：教材把“模式识别、数据挖掘、机器学习、可视化”列为生物信息学实现目标的手段，并把 HMM 作为早期概率序列模型的代表（1994/1997）——这是经典方法通向现代序列建模（乃至今天的深度学习/大模型）的历史脉络起点。

13. 研究复现视角

本章不涉及可复现的分析，故传统复现清单不适用。

但本章提出了一个与复现直接相关的重要主张（值得作为科研伦理/复现意识记住）：

• 数据共享与尽早释放：HGP 采用“正式发表前即上网释放”的政策，许多基因组计划沿用。
• 复现的前提是原始数据（primary data）可获取——本章反问：“测序仪每天产生的初级数据归谁所有？何时公开？能否设限？”这些正是今天数据可获得性 / 复现性的核心议题。

给你的实操提醒：从现在起养成记录 软件版本、数据库版本（如 GenBank Release 号）、访问日期、参数 的习惯——本章多处引用“GenBank Release 120/236”“数据截至 2020 年 2 月”，正示范了“引用数据库要写版本和日期”。

14. 最终汇总

A. 一页式总结

• 核心生物学问题：生物数据爆炸（核酸库约每 14 个月翻番），如何管理、解读、使用。
• 核心实验：无（本章为导论）；学科动机来自高通量测序。
• 核心数据：核酸序列 {A,T,G,C}、蛋白序列（20 氨基酸）；初级 vs 二级数据库。
• 核心 shape：seq ∈ {A,T,G,C}^L（概念性）。
• 核心算法：无本章算法；预告 NW/SW/BLAST/HMM/NJ 等。
• 核心工具：BLAST、ClustalW、NCBI/EBI 在线服务（SSS/MSA/BSA）。
• 核心 pipeline：无；给出“何时升级到 Linux/专业流程”的分流规则。
• 核心假设/范式：假设—实验模式（数据库搜索=一次实验）。
• 核心 QC：区分“预测”与“事实”。
• 核心解释边界：生物信息学结论多为预测，是“路灯”，最终需湿实验验证。

B. 必须记住的知识点（12 条）

1. 生物信息学=研究生物信息的采集/处理/存储/传播/分析/解释的学科（分子生物学+遗传学+计算机科学）。
2. 三大组成：新算法与统计、数据分析与解释、数据管理工具。
3. 初级数据库(原始) vs 二级数据库(衍生 domain/结构等)。
4. DNA 字母表 4 个；蛋白字母表 20 个（会背单字母更好）。
5. 术语提出者两说：Hogeweg(1978) / 林华安(1990)。
6. 三位奠基人：Dayhoff、Waterman、Sankoff。
7. 历史四阶段：萌芽/形成/基因组与互联网/高通量测序。
8. 里程碑算法年份：NW 1970、SW 1981、NJ 1987、BLAST 1990、HMM 应用 1994。
9. 三大数据库联盟：GenBank + EMBL(ENA) + DDBJ。
10. EBI 在线平台三类：SSS / MSA / BSA；NAR 两大专刊：Database Issue(1993)、Web Server Issue(2004)。
11. 研究范式=假设—实验；结论多为预测，需实验验证（“最终还是需要具体的实验”）。
12. 五大待攻关技术：从头组装、注释、比较基因组/进化、群体变异检测(SNP/Indel/SV/CNV)、RNA 分析。

C. 术语表

正名：EMBL Data Library → 现 ENA；表 1.1 中 “Ensemble”应为 Ensembl，“Fleischman”应为 Fleischmann。

D. 数据 shape 汇总表

本章仅此两项为概念性；无真实矩阵/坐标/文件结构。

E. 工具汇总表

参数细节本章未给，均属后续章节/官方文档，需要查证。

F. 掌握程度清单

• 应能口头解释：生物信息学定义、三大组成、初级/二级数据库、假设—实验范式、历史四阶段、“预测=路灯，需实验验证”。
• 应能手工计算：本章无（仅字母表计数练习）。
• 应能从头编程实现：本章无算法（NW/SW 留待第 4 章）。
• 应能调用工具完成：能在 NCBI/EBI 上做一次在线 BLAST（作为体验，细节后续学）。
• 应能设计的 pipeline：本章无；但应记住“何时升级到 Linux/脚本/专业流程”的判据。
• 只需知道其存在：具体人物生平、我国机构名单、期刊史、就业调查细节、表 1.1 全部年份（记大事件即可）。

G. 自测题

概念题

1. 用一句话给出生物信息学的定义，并列出其三大组成部分。
2. 初级数据库与二级数据库有何区别？各举一例。
3. 为什么说生物信息学结论常是“预测”而非“事实”？举例说明假设—实验范式。
4. 谁被认为是“bioinformatics”一词的提出者？为何有两种说法？
5. EBI 把在线分析平台分为哪三类？各对应什么任务？

数据格式与 shape 题
6. DNA 与蛋白质序列的字母表各有多少字符？分别写出。
7. 用集合记号写出“一条 DNA 序列”的概念表示，并说明 L 代表什么。
8. GenBank 为什么把 WGS 数据单列一类？这提示序列数据具有什么特征？

算法/公式题（本章仅涉及“提名”，考查历史定位）
9. Needleman-Wunsch 与 Smith-Waterman 分别属于哪种联配、分属哪个历史阶段？
10. HMM 在生物信息学中最早被用于哪两类任务（举本章提到的例子）？
11. 按提出年份排序：BLAST、Neighbor-Joining、Needleman-Wunsch、Smith-Waterman。

pipeline 设计题
12. 你拿到 500 条蛋白序列要做进化分析，为什么不建议全程用在线网页工具？给出本章依据。
13. 请据本章“何时求助专业人员”的判据，列出至少 4 种应转向专业/Linux 流程的情形。
14. 若要让一次 BLAST 分析可复现，你至少应记录哪些信息？（结合第 13 节）

批判性思考题
15. 教材说数据每若干月翻一番、并给出“预测曲线”，你如何看待“预测被实际超过”这一事实对“数据处理能力滞后”论断的支持或削弱？
16. “人人都能做生物信息学”这一说法错在哪里？请从经费、软件、验证三方面反驳。

参考答案

1. 研究生物信息的采集、处理、存储、传播、分析与解释的交叉学科（分子生物学+遗传学+计算机科学）；三大组成=新算法与统计方法、数据分析与解释、数据管理与利用工具。
2. 初级库存原始数据（如 GenBank 的序列、PDB 的结构）；二级库存由原始数据分析衍生的信息（如结构域 domain、二级结构、疏水位点）。
3. 因为多数结果是从数据中推断/估计出来的（如同源、基因位置、结构），不是直接观测；它像“路灯”指示实验方向。范式：先立无效假设（如“该序列无同源序列”），用数据库搜索作为“实验”去验证，拒绝或接受假设，最终仍需湿实验确证。
4. 两说：Paulien Hogeweg（1978，最早文献）与林华安 Hwa A. Lim（1990 年被普遍认为提出并办首会）；因不同来源追溯口径不同，教材两者并存。
5. SSS（序列搜索）、MSA（多序列联配）、BSA（序列分析）。
6. DNA 4 个：A、T、G、C；蛋白 20 个：A R N D C Q E G H I L K M F P S T W Y V。
7. seq ∈ {A,T,G,C}^L，L=序列长度（碱基数），不同序列 L 可变。
8. 因为 WGS（全基因组鸟枪法）数据体量极大（万亿 bp 级），单列便于管理；提示序列数据规模巨大、增长极快、异质。
9. NW=全局联配，属萌芽期(1970)；SW=局部联配，属形成期(1981)。
10. 功能域(domain)分析 与 基因预测（GENSCAN）。
11. NW(1970) → SW(1981) → NJ(1987) → BLAST(1990)。
12. 序列数已接近/超过在线工具适用上限（本章以 >100 条为经验阈值），且进化分析常需模型选择、自举、复杂统计与批处理，网页工具难以胜任、不可批量、难复现——本章明确建议此类情形求助专业/Linux 流程。
13. ①>100 条序列；②需 Linux-only 软件；③使用高通量测序数据；④处理大规模数据（如芯片/表达矩阵）；⑤数据结构或完整性有问题；⑥需复杂统计（多假设/前提/检验）。（任列 4 项）
14. 查询序列与数据库、数据库版本与访问日期、程序与版本、参数（矩阵、E-value 阈值、gap 罚分等）、运行环境。
15. 开放题要点：实际增长超过预测，说明数据产生速度被低估，反而强化“数据产生 > 处理能力”的论断；同时提醒“预测曲线”不可当精确定律，应关注趋势方向而非具体数值。
16. ①经费误解：算力/大型机与商业软件昂贵，并非零成本；②软件误解：先进商业软件多需付费，非全免费；③验证误解：计算结果是预测，“最终还是需要具体实验”，仅有电脑和教科书不足以产出可靠科学结论。

H. 下一步学习建议

• 下一节/章：进入第 2 章（生物数据/数据类型），把本章“核酸/蛋白/结构/初级二级库”的概念落到具体文件格式与 shape；随后第 3 章（数据库、Dayhoff）、第 4 章（序列联配 NW/SW，Waterman）。
• 需补的前置：中心法则、碱基/氨基酸生化基础；命令行入门（bash）、Python 基础——本章已明确点名为必备技能。
• 值得亲手实现的算法：读到第 4 章时，自己用 Python 实现 Needleman-Wunsch（本章埋下的最经典起点）。
• 值得实际运行的工具：去 NCBI 做一次在线 BLAST，体验 SSS 流程；再用 EBI 做一次 ClustalW/MSA。
• 值得手工查看的文件格式：下一章的 FASTA（本章尚未出现，但是所有后续分析的入口）。
• 配套实验：本章无专属实验；从第 2/3 章起对接《实验指导》中数据库检索与 BLAST/ClustalW 实验。
• 需查最新官方资料：GenBank/ENA/DDBJ 现状与最新 Release、NGDC(bigd.big.ac.cn)、BLAST/ClustalW 现行版本与替代工具（MAFFT/MUSCLE、DIAMOND）——本章数字截至 2020 年，需要查证更新。

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记为class49的内容。滑动窗口是处理子数组（子串）问题的重要技巧，通过维持左右边界都不回退的一段范围，可以高效求解各类连续区间问题。

前置知识

学习滑动窗口之前，需要掌握以下基础知识：

• 双指针的基本概念
• 数组和字符串的基本操作
• 哈希表或数组的计数技巧
• 贪心思想的理解

049【必备】滑动窗口技巧与相关题目

基本思想

滑动窗口是通过维护一个动态区间来求解子数组或子串问题的技巧：

• 核心特征：左右边界都不回退（单调移动）
• 关键要素：找到范围和答案指标之间的单调性关系
• 维护信息：使用简单变量或额外结构（如数组、哈希表）来维护窗口信息
• 求解方式：通常固定一个边界（左或右），移动另一个边界来找答案

单调性关系

滑动窗口能够应用的前提是找到单调性：

1
2
3
4
5
6
7

# 示例1：累加和的单调性
# 范围变大 → 累加和一定变大（或不变）
# 范围变小 → 累加和一定变小（或不变）

# 示例2：字符种类的单调性
# 范围变大 → 字符种类一定增加（或不变）
# 范围变小 → 字符种类一定减少（或不变）

窗口维护策略

1
2
3
4
5
6
7
8
9
10
11
12
13

# 标准滑动窗口模板
l = 0  # 左边界
for r in range(n):  # 右边界遍历
    # 1. 扩展右边界，加入新元素
    add_element(r)
    
    # 2. 收缩左边界，维持窗口性质
    while not_valid():
        remove_element(l)
        l += 1
    
    # 3. 更新答案
    update_answer(l, r)

题目一：长度最小的子数组

问题描述

给定一个含有n个正整数的数组和一个正整数target，找到累加和≥target的长度最小的子数组并返回其长度。如果不存在符合条件的子数组返回0。

测试链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

核心思想

利用累加和的单调性质：范围变大累加和一定增加

1. 右边界扩展：不断加入新元素增加累加和
2. 左边界收缩：当满足条件时，尝试缩小窗口
3. 贪心策略：在满足条件的前提下找最小长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14

示例：target = 7, nums = [2,3,1,2,4,3]

初始：l=0, r=0, sum=0
r=0: sum=2, [2]
r=1: sum=5, [2,3]
r=2: sum=6, [2,3,1]
r=3: sum=8, [2,3,1,2] ✓ 满足，尝试收缩
     → 移除2，sum=6 < 7，不满足，停止收缩
     答案=4
r=4: sum=10, [3,1,2,4] ✓ 满足，收缩
     → 移除3，sum=7 ✓ 仍满足，继续
     → 移除1，sum=6 < 7，停止
     答案=min(4,3)=3
...

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        """
        滑动窗口求最短达标子数组
        
        时间复杂度：O(n)
        - 虽然是for+while双层循环，但每个元素最多被访问两次
        - 右指针遍历n次，左指针最多移动n次
        
        空间复杂度：O(1)
        """
        ans = float('inf')  # 初始化答案为无穷大
        l = 0  # 左指针
        sum_val = 0  # 当前窗口的累加和
        
        # 右指针遍历数组
        for r in range(len(nums)):
            sum_val += nums[r]  # 右边界扩展，加入新元素
            
            # 尝试收缩左边界，保持累加和刚好 >= target
            # 贪心思想：如果去掉l位置的数还能达标，那就去掉
            while sum_val - nums[l] >= target:
                sum_val -= nums[l]  # l位置的数从窗口出去
                l += 1  # 左指针右移
            
            # 如果当前窗口满足条件，更新答案
            if sum_val >= target:
                ans = min(ans, r - l + 1)
        
        # 如果没有找到满足条件的子数组，返回0
        return 0 if ans == float('inf') else ans

算法分析

• 时间复杂度：O(n)（每个元素最多访问两次）
• 空间复杂度：O(1)
• 关键技巧：贪心收缩窗口

题目二：无重复字符的最长子串

问题描述

给定一个字符串s，请找出其中不含有重复字符的最长子串的长度。

测试链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

核心思想

使用数组记录每个字符最后出现的位置，动态调整左边界：

1. 位置记录：last[c]记录字符c上次出现的位置
2. 左边界更新：遇到重复字符时，左边界跳到重复位置的下一位
3. 答案更新：每次右边界扩展时更新最长长度

1
2
3
4
5
6
7
8
9
10

示例：s = "abcabcbb"

r=0: 'a', last['a']=-1→0, l=0, len=1
r=1: 'b', last['b']=-1→1, l=0, len=2
r=2: 'c', last['c']=-1→2, l=0, len=3
r=3: 'a', last['a']=0→3, l=max(0,0+1)=1, len=3
                          ↑重复了，左边界跳到1
r=4: 'b', last['b']=1→4, l=max(1,1+1)=2, len=3
r=5: 'c', last['c']=2→5, l=max(2,2+1)=3, len=3
...

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        滑动窗口 + 位置记录
        
        核心思想：
        1. 固定窗口右边界，动态调整左边界
        2. 使用last数组记录每个字符上次出现的位置
        3. 遇到重复字符时，左边界跳到重复字符的下一个位置
        
        时间复杂度：O(n)
        空间复杂度：O(1)（last数组固定256大小）
        """
        n = len(s)
        # 记录每个字符上次出现的位置，初始化为-1表示未出现过
        last = [-1] * 256  # ASCII码范围
        ans = 0  # 记录最长子串的长度
        l = 0  # 左指针
        
        # 右指针遍历字符串
        for r in range(n):
            char_code = ord(s[r])  # 获取字符的ASCII码
            
            # 更新左指针：要么保持原位，要么跳到重复字符的下一个位置
            # 这个逻辑可以理解为：如果当前字符已经出现过，那么左边界需要跳到重复字符的下一个位置，因为不能包含重复字符
            # 如果当前字符没有出现过，那么左边界保持原位，因为可以包含重复字符
            l = max(l, last[char_code] + 1)
            
            # 更新答案
            ans = max(ans, r - l + 1)
            
            # 更新当前字符最后出现的位置
            last[char_code] = r
        
        return ans

关键点说明

1
2
3
4
5
6
7
8

# 为什么使用max(l, last[char_code] + 1)？

示例："abba"
r=0: 'a', last['a']=-1, l=max(0,-1+1)=0 ✓
r=1: 'b', last['b']=-1, l=max(0,-1+1)=0 ✓
r=2: 'b', last['b']=1,  l=max(0,1+1)=2  ✓ 左边界跳过第一个'b'
r=3: 'a', last['a']=0,  l=max(2,0+1)=2  ✓ 左边界不回退
                                          如果不用max，会错误地回到1

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)（256大小的数组）
• 优化技巧：通过位置数组避免重复扫描

题目三：最小覆盖子串

问题描述

给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串””。

测试链接：https://leetcode.cn/problems/minimum-window-substring/

核心思想

使用”欠债表”维护字符需求，先负债后还债：

1. 欠债表：cnts[c] < 0表示还需要字符c，> 0表示字符c多余
2. 债务管理：debt记录总债务（还需要多少个字符）
3. 两阶段处理：先扩展找到覆盖，再收缩找到最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

示例：s = "ADOBECODEBANC", t = "ABC"

初始化欠债表：
cnts['A'] = -1 (欠1个A)
cnts['B'] = -1 (欠1个B)
cnts['C'] = -1 (欠1个C)
debt = 3

扩展阶段：
r=0: 'A', cnts['A']=-1→0, debt=3→2
r=1: 'D', cnts['D']=0→1,  debt=2
r=2: 'O', cnts['O']=0→1,  debt=2
r=3: 'B', cnts['B']=-1→0, debt=2→1
r=4: 'E', cnts['E']=0→1,  debt=1
r=5: 'C', cnts['C']=-1→0, debt=1→0 ✓ 债务还清！

收缩阶段：
去掉'A'：cnts['A']=0→-1, 不行（会欠债）
窗口："ADOBEC"，长度=6

继续扩展...

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        滑动窗口 + 欠债表
        
        核心思想：
        1. cnts数组维护欠债情况：
           - cnts[i] < 0：字符i有负债（还需要）
           - cnts[i] > 0：字符i有盈余（多了）
        2. debt记录总债务（还需要多少个字符）
        3. 先扩展窗口还债，债务清零后再收缩窗口
        
        时间复杂度：O(n + m)，n是s长度，m是t长度
        空间复杂度：O(1)（cnts数组固定256大小）
        """
        # 记录每种字符的欠债情况
        cnts = [0] * 256
        
        # 统计t中每个字符的需求，初始为负数（欠债）
        for char in t:
            cnts[ord(char)] -= 1
        
        length = float('inf')  # 最小覆盖子串的长度
        start = 0  # 最小覆盖子串的起始位置
        debt = len(t)  # 总债务（还需要多少个字符）
        l = 0  # 左指针
        
        # 右指针遍历字符串s
        for r in range(len(s)):
            char_code = ord(s[r])
            
            # 如果当前字符是需要的（cnts < 0），则减少债务
            if cnts[char_code] < 0:
                debt -= 1
            cnts[char_code] += 1  # 字符进入窗口
            
            # 如果债务已还清（找到了包含t所有字符的窗口）
            if debt == 0:
                # 收缩左边界，去掉多余的字符
                while cnts[ord(s[l])] > 0:
                    cnts[ord(s[l])] -= 1
                    l += 1
                
                # 更新最小窗口
                if r - l + 1 < length:
                    length = r - l + 1
                    start = l
        
        # 如果没有找到满足条件的子串，返回空字符串
        return "" if length == float('inf') else s[start:start + length]

欠债表机制详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 欠债表的工作原理

初始状态（t = "ABC"）:
cnts['A'] = -1  # 欠1个A
cnts['B'] = -1  # 欠1个B  
cnts['C'] = -1  # 欠1个C
其他字符 = 0     # 不欠不多

加入字符'A':
cnts['A'] = -1 + 1 = 0  # 刚好够，debt减1
加入字符'A':
cnts['A'] = 0 + 1 = 1   # 多了1个，debt不变

去掉字符'A':
cnts['A'] = 1 - 1 = 0   # 还是刚好，可以去掉
去掉字符'A':
cnts['A'] = 0 - 1 = -1  # 又欠了，不能再去掉

算法分析

• 时间复杂度：O(n + m)
• 空间复杂度：O(1)
• 核心技巧：欠债表 + 两阶段处理

题目四：加油站

问题描述

在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。

测试链接：https://leetcode.cn/problems/gas-station/

核心思想

通过结余数组和滑动窗口找到合适的起点：

1. 结余计算：每个位置的结余 = gas[i] - cost[i]
2. 环路扩展：将数组扩展为两倍处理环路
3. 窗口验证：从每个位置出发，看能否走完一圈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
结余数组 = [-2,-2,-2,3,3]

扩展数组：
索引：0   1   2   3   4   5   6   7   8   9
结余：-2  -2  -2  3   3   -2  -2  -2  3   3
                          ↑原数组重复

从l=0开始：
r=0: sum=-2 < 0，失败，跳到r+1=1
从l=1开始：
r=1: sum=-2 < 0，失败，跳到r+1=2
...
从l=3开始：
r=3: sum=3 ✓
r=4: sum=6 ✓
r=5: sum=4 ✓
r=6: sum=2 ✓
r=7: sum=0 ✓
走完一圈！答案=3

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        """
        滑动窗口处理环路问题
        
        核心思想：
        1. 将环路扩展为两倍：[a,b,c,d,e] → [a,b,c,d,e,a,b,c,d,e]
        2. 窗口范围[l,r)，左闭右开，r是到不了的位置
        3. 从每个位置l出发，看能否走完n个站点
        4. 如果失败，直接跳到r+1位置（剪枝）
        
        时间复杂度：O(n)
        - 外层循环l最多到n-1
        - 内层循环r最多移动到2n
        - 总移动次数不超过2n
        
        空间复杂度：O(1)
        """
        n = len(gas)
        l = 0
        
        while l < n:
            r = l  # 右指针从左指针开始
            sum_val = 0  # 当前油量余额
            
            # 尝试从l位置出发
            while sum_val + gas[r % n] - cost[r % n] >= 0:
                # 检查是否已经绕了一圈
                if r - l + 1 == n:
                    return l  # 找到答案
                
                # r位置进入窗口，累加油量余额
                sum_val += gas[r % n] - cost[r % n]
                r += 1
            
            # 从l出发无法完成，直接跳到r+1开始尝试（剪枝）
            # 原理：如果从l到r失败，那么从l+1到r也必然失败
            l = r + 1
        
        return -1  # 没有找到可行的起点

剪枝原理说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 为什么可以直接跳到r+1？

假设从位置i到位置j失败（油量不足）：
  i → i+1 → i+2 → ... → j (失败)
  
如果从i能到j-1，说明：
  sum(i到j-1) >= 0
  
但在j失败，说明：
  sum(i到j) < 0
  即 sum(i到j-1) + rest[j] < 0
  
现在考虑从i+1出发：
  sum(i+1到j) = sum(i到j) - rest[i]
  
因为sum(i到j) < 0，且rest[i] <= sum(i到j-1)（否则到不了i+1）
所以 sum(i+1到j) <= sum(i到j) < 0

结论：从i+1、i+2...j出发都无法到达j，可以直接跳过

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 核心技巧：环路扩展 + 剪枝优化

题目五：替换子串得到平衡字符串

问题描述

有一个只含有’Q’,’W’,’E’,’R’四种字符，且长度为n的字符串。假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。请通过「替换一个子串」的方式，使原字符串变成一个「平衡字符串」，返回待替换子串的最小可能长度。

测试链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

核心思想

反向思考：找到包含所有多余字符的最小窗口

1. 字符整数化：将QWER映射为0123
2. 计算过剩：统计每种字符超过n/4的数量
3. 窗口覆盖：找到包含所有过剩字符的最小窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例：s = "QWER", n = 4
期望：每种字符1个

示例：s = "QQWE", n = 4
Q出现2次，多1个
W出现1次，正好
E出现1次，正好
R出现0次，少1个

初始欠债表：
cnts[Q] = 1-2 = -1 (多1个Q要放进窗口)
cnts[W] = 1-1 = 0
cnts[E] = 1-1 = 0
cnts[R] = 1-0 = 1 (缺1个R，不用管)
debt = 1

找到包含这1个多余Q的最小窗口即可

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class Solution:
    def balancedString(self, s: str) -> int:
        """
        滑动窗口 + 字符整数化
        
        核心思想：
        1. 将字符映射为数字：Q→0, W→1, E→2, R→3
        2. 计算每种字符的过剩数量（超过n/4的部分）
        3. 找到包含所有过剩字符的最小窗口
        4. 这个窗口就是需要替换的最小子串
        
        时间复杂度：O(n)
        空间复杂度：O(1)（cnts数组固定4大小）
        """
        n = len(s)
        # 将字符映射为数字
        char_to_num = []
        cnts = [0] * 4  # 统计四种字符的出现次数
        
        for char in s:
            if char == 'W':
                num = 1
            elif char == 'E':
                num = 2
            elif char == 'R':
                num = 3
            else:  # 'Q'
                num = 0
            char_to_num.append(num)
            cnts[num] += 1
        
        # 计算每种字符的欠债情况
        debt = 0
        for i in range(4):
            if cnts[i] < n // 4:
                # 该字符不足，不需要减少
                cnts[i] = 0
            else:
                # 该字符过多，需要减少到n/4
                cnts[i] = n // 4 - cnts[i]  # 负数表示需要减少的数量
                debt -= cnts[i]
        
        # 如果已经平衡，直接返回0
        if debt == 0:
            return 0
        
        ans = float('inf')
        l = 0
        
        # 滑动窗口
        for r in range(n):
            # 窗口右边界向右，给出字符
            if cnts[char_to_num[r]] < 0:
                debt -= 1
            cnts[char_to_num[r]] += 1
            
            # 如果债务已还清
            if debt == 0:
                # 窗口左边界向右，拿回字符
                while cnts[char_to_num[l]] > 0:
                    cnts[char_to_num[l]] -= 1
                    l += 1
                # 更新答案
                ans = min(ans, r - l + 1)
        
        return ans

字符整数化技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 为什么要字符整数化？

方法1：直接用字符作为索引（不推荐）
cnts = {}
cnts['Q'] = ...  # 字典操作，较慢

方法2：字符整数化（推荐）
cnts = [0] * 4  # 数组操作，更快
Q → 0
W → 1
E → 2
R → 3

优势：
1. 数组访问比字典快
2. 空间固定，不需要哈希表
3. 代码更清晰

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 核心技巧：字符整数化 + 反向思考

题目六：K个不同整数的子数组

问题描述

给定一个正整数数组nums和一个整数k，返回nums中「好子数组」的数目。如果nums的某个子数组中不同整数的个数恰好为k，则称这个连续子数组为「好子数组」。

测试链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/

核心思想

将”恰好k种”转化为”最多k种”的差值：

核心公式：恰好k种 = 最多k种 - 最多k-1种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

示例：nums = [1,2,1,2,3], k = 2

最多2种的子数组：
[1]         1种 ✓
[1,2]       2种 ✓
[2]         1种 ✓
[1]         1种 ✓
[1,2]       2种 ✓
[2]         1种 ✓
[2,1]       2种 ✓
[1]         1种 ✓
[2]         1种 ✓
[2,3]       2种 ✓
[3]         1种 ✓
...
总计：最多2种的数量 = X

最多1种的子数组：
[1]         1种 ✓
[2]         1种 ✓
[1]         1种 ✓
[2]         1种 ✓
[3]         1种 ✓
总计：最多1种的数量 = Y

恰好2种的数量 = X - Y

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution:
    def subarraysWithKDistinct(self, nums: list[int], k: int) -> int:
        """
        恰好k种 = 最多k种 - 最多k-1种
        
        核心思想：
        1. "恰好k种"不好直接计算
        2. "最多k种"可以用滑动窗口
        3. 利用差值关系转化问题
        """
        return self.numsOfMostKinds(nums, k) - self.numsOfMostKinds(nums, k - 1)
    
    def numsOfMostKinds(self, arr: list[int], k: int) -> int:
        """
        计算数组中有多少子数组，数字种类不超过k
        
        核心思想：
        1. 固定右边界r，计算以r结尾的满足条件的子数组数量
        2. 对于固定的r，所有从[l,r]区间的子数组都满足条件
        3. 数量 = r - l + 1
        
        时间复杂度：O(n)
        空间复杂度：O(n)（cnts数组大小）
        """
        cnts = [0] * 20001  # 统计每个数字出现的次数
        ans = 0
        collect = 0  # 当前窗口中不同数字的种类数
        l = 0
        
        for r in range(len(arr)):
            # 右边界扩展
            cnts[arr[r]] += 1
            if cnts[arr[r]] == 1:
                collect += 1
            
            # 如果种类数超过k，收缩左边界
            while collect > k:
                cnts[arr[l]] -= 1
                if cnts[arr[l]] == 0:
                    collect -= 1
                l += 1
            
            # 以r结尾的，种类数不超过k的子数组个数
            # 例如：l=0, r=3，则子数组有[0,3],[1,3],[2,3],[3,3]
            ans += r - l + 1
        
        return ans

计数原理详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 为什么ans += r - l + 1？

固定右边界r，所有从[l,r]区间开始的子数组都满足条件

示例：l=1, r=4，数组=[a,b,c,d,e]
窗口内：[b,c,d,e]，种类数≤k

以r=4结尾的满足条件的子数组：
[b,c,d,e]  从1到4
[c,d,e]    从2到4
[d,e]      从3到4
[e]        从4到4

共4个，即 r - l + 1 = 4 - 1 + 1 = 4

累加过程：
r=0: ans += 1        (1个子数组)
r=1: ans += ...      (若干个子数组)
r=2: ans += ...
...
最终ans = 所有满足条件的子数组总数

转化技巧总结

1
2
3
4
5
6
7
8
9
10
11

# 恰好 vs 最多 转化技巧

问题类型                     转化方式
========================================================
恰好k个                   = 最多k个 - 最多k-1个
至少k个                   = 全部 - 最多k-1个
恰好在[a,b]区间内         = 最多b - 最多a-1
========================================================

这种转化技巧可以将复杂的"恰好"问题转化为
更容易处理的"最多"问题

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 核心技巧：”恰好”转化为”最多”的差值

题目七：至少有K个重复字符的最长子串

问题描述

给你一个字符串s和一个整数k，请你找出s中的最长子串，要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。

测试链接：https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

核心思想

固定字符种类 + 滑动窗口

为什么要固定字符种类？因为直接求解没有单调性：

• 窗口变大：字符种类可能增加，但某些字符可能不达标
• 窗口变小：字符种类可能减少，但剩余字符可能达标

解决方案：枚举字符种类数（1到26），对每种情况求最长子串

1
2
3
4
5
6
7
8
9
10
11
12

示例：s = "aaabb", k = 3

要求：每种字符必须出现≥3次

情况1：恰好1种字符
窗口[aaa]：'a'出现3次 ✓，长度=3

情况2：恰好2种字符
窗口[aaabb]：'a'出现3次 ✓，'b'出现2次 ✗
无满足条件的窗口

答案 = 3

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        """
        固定字符种类 + 滑动窗口
        
        核心思想：
        1. 直接求解没有单调性，需要固定字符种类
        2. 枚举字符种类数require（1到26）
        3. 对每种情况，用滑动窗口求最长子串
        4. 维护两个指标：
           - collect: 窗口中字符种类数
           - satisfy: 达标的字符种类数（次数≥k）
        
        时间复杂度：O(26n) = O(n)
        空间复杂度：O(1)（cnts数组固定256大小）
        """
        n = len(s)
        ans = 0
        
        # 枚举字符种类数：1到26种
        for require in range(1, 27):
            cnts = [0] * 256  # 统计每个字符出现的次数
            collect = 0  # 窗口中字符种类数
            satisfy = 0  # 达标的字符种类数(次数≥k)
            l = 0
            
            # 滑动窗口
            for r in range(n):
                char_code = ord(s[r])
                cnts[char_code] += 1
                
                # 新增一种字符
                if cnts[char_code] == 1:
                    collect += 1
                # 该字符达标
                if cnts[char_code] == k:
                    satisfy += 1
                
                # 种类数超过require，收缩左边界
                while collect > require:
                    left_char_code = ord(s[l])
                    if cnts[left_char_code] == 1:
                        collect -= 1
                    if cnts[left_char_code] == k:
                        satisfy -= 1
                    cnts[left_char_code] -= 1
                    l += 1
                
                # 所有字符都达标，更新答案
                if satisfy == require:
                    ans = max(ans, r - l + 1)
        
        return ans

为什么要固定字符种类？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 反例：不固定字符种类的问题

s = "aaabbc", k = 3

窗口扩展过程：
[a]       'a':1 ✗
[aa]      'a':2 ✗
[aaa]     'a':3 ✓  达标！
[aaab]    'a':3 ✓, 'b':1 ✗  不达标
[aaabb]   'a':3 ✓, 'b':2 ✗  不达标
[aaabbc]  'a':3 ✓, 'b':2 ✗, 'c':1 ✗  更不达标

问题：窗口变大后，新字符可能不达标
      没有明确的单调性

解决：固定字符种类后
require=1: [aaa] ✓
require=2: 无满足条件的窗口
require=3: 无满足条件的窗口

双指标维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# collect 和 satisfy 的关系

collect: 窗口中有多少种字符
satisfy: 其中有多少种达标（出现次数≥k）

示例：s = "aabbc", k = 2, require = 2

r=0: 'a'  cnts['a']=1, collect=1, satisfy=0
r=1: 'a'  cnts['a']=2, collect=1, satisfy=1 (a达标)
r=2: 'b'  cnts['b']=1, collect=2, satisfy=1
r=3: 'b'  cnts['b']=2, collect=2, satisfy=2 (a,b都达标)
     ✓ satisfy == require，更新答案

关键判断：
if satisfy == require:  # 所有种类都达标
    ans = max(ans, r - l + 1)

算法分析

• 时间复杂度：O(26n) = O(n)
• 空间复杂度：O(1)
• 核心技巧：固定变量制造单调性

滑动窗口技巧总结

1. 核心模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 标准滑动窗口框架

def sliding_window(arr, constraint):
    """
    arr: 输入数组/字符串
    constraint: 约束条件
    """
    n = len(arr)
    l = 0  # 左指针
    ans = 初始值  # 根据题目初始化
    
    # 维护信息的数据结构（根据题目选择）
    info = {}  # 或 [], 或 变量
    
    for r in range(n):  # 右指针遍历
        # 1. 扩展右边界，更新信息
        update_info_add(arr[r])
        
        # 2. 收缩左边界，维持约束
        while not satisfy_constraint():
            update_info_remove(arr[l])
            l += 1
        
        # 3. 更新答案
        update_answer(l, r)
    
    return ans

2. 常见维护信息的方式

3. 滑动窗口 vs 其他技巧

1
2
3
4
5
6
7
8
9
10
11
12
13

# 何时使用滑动窗口？

适用情况：
✓ 连续子数组/子串问题
✓ 存在单调性关系
✓ 需要维护区间信息
✓ 左右边界都单向移动

不适用情况：
✗ 非连续子序列
✗ 需要回溯的问题
✗ 边界需要回退
✗ 需要排序的问题

4. 时间复杂度分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 为什么是O(n)？

虽然代码是双层循环：
for r in range(n):      # O(n)
    while ...:          # 看起来O(n)
        l += 1

但实际上：
- 右指针r：从0移动到n-1，移动n次
- 左指针l：从0移动到n-1，最多移动n次
- 总移动次数：2n次
- 时间复杂度：O(n)

关键：每个元素最多被访问常数次（进入窗口1次，离开窗口1次）

5. 常见技巧汇总

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 技巧1：位置数组避免重复扫描
last = [-1] * 256
l = max(l, last[char] + 1)  # 左边界不回退

# 技巧2：欠债表维护需求
cnts[char] = -need  # 负数表示欠债
debt = total_need   # 总债务

# 技巧3：字符整数化
char_to_num = {'Q': 0, 'W': 1, 'E': 2, 'R': 3}

# 技巧4：恰好转化为最多
exactly_k = at_most_k - at_most_(k-1)

# 技巧5：固定变量制造单调性
for require in range(1, 27):  # 固定字符种类
    # 滑动窗口求解

6. 调试技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 调试检查点

1. 左右边界是否正确移动？
   - 打印l和r的值
   - 检查边界条件

2. 维护信息是否正确？
   - 打印info的内容
   - 验证更新逻辑

3. 答案更新时机是否正确？
   - 检查更新条件
   - 验证窗口状态

4. 边界情况是否处理？
   - 空数组
   - 单元素
   - 全相同元素

学习建议

1. 理解单调性

滑动窗口的核心是单调性关系：

• 明确范围和答案的关系
• 识别哪些变量具有单调性
• 理解如何固定变量制造单调性

2. 掌握维护技巧

熟练使用各种数据结构维护窗口信息：

• 数组计数（字符频次）
• 位置记录（避免重复扫描）
• 多变量跟踪（种类数、达标数等）

3. 练习转化思维

学会将复杂问题转化为简单问题：

• “恰好”转化为”最多”的差值
• 固定变量降低问题维度
• 反向思考问题本质

4. 注意边界处理

重点关注边界条件：

• 左右边界的移动时机
• 答案更新的条件判断
• 特殊情况的处理

5. 复杂度分析

理解滑动窗口为什么是O(n)：

• 每个元素最多访问两次
• 左右指针都单向移动
• 总移动次数是线性的

通过掌握滑动窗口技巧，可以高效解决各类子数组和子串问题。关键在于识别单调性关系，选择合适的维护方式，以及灵活运用转化技巧。

引言

本笔记总结了Linux操作系统的基础知识和实用技巧，涵盖远程连接工具、常用命令、系统设置、定时任务、用户管理、文件权限等内容。

前置知识

在学习本笔记内容之前，建议具备以下基础：

• 基本的计算机操作知识
• 了解操作系统的基本概念
• 熟悉命令行界面的使用方式
• 建议购买云服务器进行实践操作

Linux使用总结

1. Linux介绍

历史背景

Linux，全称GNU/Linux，是一套免费使用和自由传播的类UNIX操作系统。其内核由林纳斯·本纳第克特·托瓦兹（Linus Torvalds）于1991年第一次释出。它主要受到Minix和Unix思想的启发，是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。

核心特点：

• Linux内核kernel最初由芬兰人李纳斯·托瓦兹在赫尔辛基大学上学时出于个人爱好编写
• 1991年10月5日第一次正式向外公布
• Linux借鉴了Unix的思想，但没有一行Unix的代码
• Linux英文解释：Linux is not Unix，业界称为”类Unix”系统

Linux构成

Linux系统由以下部分组成：

• Linux Kernel（内核）：系统的核心部分
• 软件包：各种应用程序和工具

主流发行版本

目前市面上比较知名的Linux发行版有：

• RedHat：企业级商业发行版
• CentOS：社区企业操作系统（常用于Web服务器）
• Ubuntu：用户友好的桌面和服务器版本
• Fedora：RedHat的社区版本
• Debian：稳定性强的发行版
• Aliyun Linux：阿里云定制版本
• SUSE Linux：企业级发行版
• Open SUSE：SUSE的社区版本
• CoreOS：容器化操作系统
• FreeBSD：类Unix系统

应用场景选择：

• Web应用（Java、PHP等）→ 选择CentOS
• 微软技术栈（ASP、.NET、SQL Server）→ 选择Windows Server

2. Linux常用远程连接工具

建议：购买云服务器（阿里云、华为云等）进行实践，多练习才能熟练掌握Linux。

推荐工具组合

最佳组合：Xshell + WinSCP

主流远程连接工具

1. SecureCRT

• 功能：可直接连接并上传文件
• 下载地址：https://www.vandyke.com
• 特点：集成度高，功能全面

2. XShell

• 功能：终端连接工具
• 下载地址：https://www.netsarang.com/zh/xshell/
• 特点：界面友好，功能强大

3. Putty

• 功能：轻量级SSH客户端
• 下载地址：https://www.chiark.greenend.org.uk/~sgtatham/putty/latest.html
• 特点：小巧免费，适合快速连接

4. XFTP

• 功能：文件传输工具
• 下载地址：https://www.netsarang.com/zh/xftp/
• 特点：上传速度快，界面直观

5. WinSCP

• 功能：SFTP和FTP客户端
• 下载地址：https://winscp.net/eng/download.php
• 特点：支持多种协议，操作便捷

3. Linux常用命令总结

3.1 Linux特色目录符号

1
2
3
4

.      # 当前目录
..     # 上一级目录
-      # 上一个工作目录（配合cd使用）
~      # 用户根目录（/root）

使用示例：

1
2
3

cd -   # 返回上一个工作目录
cd ~   # 返回用户根目录
cd ..  # 返回上一级目录

3.2 磁盘管理

目录切换与查看

1
2
3
4
5
6
7
8
9
10
11
12

# 进入目录
cd 目录名              # 进入某个目录
cd /info/a           # 进入多级目录
cd ..               # 返回上一级目录
cd /                # 返回根目录
cd -                # 返回上一个工作目录

# 显示当前目录
pwd                 # 显示当前完整路径

# 查看分区
fdisk -l            # 查看新的分区

列出文件和目录

1
2
3
4
5
6
7
8
9
10
11

# 基本列出命令
ll                  # 纵向列出（含详细信息）
ll -a              # 额外展示隐藏文件
ll -h              # 人性化显示大小（KB、MB、GB）
ls                  # 横向列出
ls -a              # 额外展示隐藏文件
dir                 # 列出当前目录内容

# ll vs ls 区别
# ll：纵向展示，显示权限、所有者、组、大小等详细信息
# ls：横向简洁展示

磁盘空间查看

1
2
3
4

# df 命令 - 查看文件系统级别的磁盘使用
df                  # 查看磁盘空间使用情况
df -h              # 人性化显示（GB、MB格式）
df -T              # 显示文件系统类型

df 输出字段说明：

• Filesystem：文件系统
• Size：总容量
• Used：已使用
• Avail：可用空间
• Use%：使用百分比
• Mounted on：挂载点

1
2
3

# du 命令 - 查看文件/目录级别的磁盘使用
du                  # 查看文件和目录大小
du -h              # 人性化显示大小

使用场景：

• df：查看磁盘分区整体使用情况
• du：查看具体文件和文件夹占用空间

3.3 文件管理

创建目录

1
2
3
4
5
6
7
8
9

# 基本创建
mkdir 目录名                          # 创建单个目录
mkdir -p file1/file2                # 递归创建多级目录
mkdir -v file4                      # 显示创建信息
mkdir -vp {hello/,maven/}          # 一次创建多个目录结构

# 参数说明
# -p, --parents  : 自动创建父目录
# -v, --verbose  : 显示详细信息

文件操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 创建文件
touch 文件名                         # 创建空文件或更新修改时间

# 删除操作
rm -f 文件                          # 强制删除文件
rm -rf 目录                         # 递归删除目录及内容

# 移动/重命名
mv 源文件 目标文件                   # 移动或重命名

# mv 常用参数
# -b : 覆盖前先备份
# -f : 强制覆盖
# -i : 覆盖前询问
# -u : 仅当源文件较新时才更新
# -t : 指定目标目录
# -v : 显示过程

查看文件内容

1
2
3
4
5

cat 文件名                          # 一次性输出全部内容
more 文件名                         # 逐屏输出（空格翻页）
less 文件名                         # 逐屏输出（PgUp/PgDn翻页，q退出）
head 文件名                         # 显示前10行
tail 文件名                         # 显示后10行

复制与查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 复制
cp 源文件 目标文件                   # 复制文件
cp -rf 源目录 目标目录               # 递归复制目录

# 查找文件
find ./ -name 文件名                # 按名称查找
find ./ -mtime +5                  # 查找5天前修改的文件

# 查找命令
which 命令                          # 查找命令位置（PATH中）
whereis 程序名                      # 查找程序相关文件
# whereis 参数：
# -b : 只搜索二进制文件
# -m : 只搜索man说明文件
# -s : 只搜索源代码文件

3.4 系统设置

进程管理

1
2
3
4
5
6
7

# 查看进程
ps -aux                            # 查看所有进程（BSD风格）
ps -ef                             # 查看所有进程（标准风格）

# 终止进程
kill PID                           # 正常终止进程
kill -9 PID                        # 强制终止进程

系统信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 日期时间
date                               # 显示/设置系统日期时间

# 语言环境
echo $LANG                         # 显示当前语言环境
locale                             # 查看语言包

# 系统信息
uname                              # 查看系统信息
cat /etc/centos-release           # 查看CentOS版本

# 用户信息
who                                # 显示已登录用户
whoami                             # 显示当前用户
su 用户名                          # 切换用户

系统操作

1
2
3

shutdown -h now                    # 立即关机
reboot                            # 重启系统
clear                             # 清屏（内容上移）

实用技巧：

• 按 Tab 键自动补全命令或文件名

系统负载监控

1
2

# top 命令 - 实时监控系统
top                               # 动态显示系统资源使用情况

top 可查看信息：

• CPU使用率
• 内存使用情况
• 系统运行时间
• 进程线程信息
• 交换分区使用情况

1
2

# uptime 命令 - 系统负载概览
uptime                            # 显示系统运行时长和负载

系统负载解读：

• 系统平均负载：特定时间间隔内运行队列中的平均进程数
• 每个CPU核心活动进程数 ≤ 3：系统运行良好
• 四核CPU：负载 < 12 为正常
• 负载达到20：系统负载严重

进程进入运行队列的条件：

• 没有在等待I/O操作
• 没有主动进入等待状态
• 没有被停止

内存管理

1
2
3

free                              # 显示内存使用（KB）
free -m                          # 显示内存使用（MB）
free -h                          # 显示内存使用（GB，人性化）

3.5 Linux定时任务

详细教程：可参考博文《Linux crontab 命令详细使用》

Crontab 基本命令

1
2
3

crontab -e                        # 创建或编辑定时任务
crontab -l                        # 查看当前定时任务
crontab -r                        # 删除所有定时任务（慎用）

Crontab 语法格式

1
2
3
4
5
6
7

* * * * * command
│ │ │ │ │
│ │ │ │ └─── 星期 (0-7, 0和7都表示周日)
│ │ │ └───── 月份 (1-12)
│ │ └─────── 日期 (1-31)
│ └───────── 小时 (0-23)
└─────────── 分钟 (0-59)

使用示例

1
2
3
4
5
6
7
8

# 每分钟执行一次
*/1 * * * * echo "hello world" >> /opt/crontab.log

# 每天凌晨2点执行
0 2 * * * /path/to/script.sh

# 每周一上午9点执行
0 9 * * 1 /path/to/script.sh

查看执行日志

1

tail -f /var/log/cron             # 实时查看定时任务执行情况

重定向符号说明

1
2
3
4

>  a.log                          # 重定向覆盖输出
>> a.log                          # 重定向追加输出
|                                 # 管道符，左边输出作为右边输入
> a.log                           # 清空日志文件

常用组合：

1

ps -ef | grep tomcat              # 查找tomcat进程

扩展阅读：重定向详解参考博文 https://blog.csdn.net/smilehappiness/article/details/105181739

3.6 用户管理

详细教程：https://www.runoob.com/linux/linux-user-manage.html

用户操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 添加用户
useradd 用户名                     # 创建新用户

# 删除用户
userdel -r zhangsan              # 删除用户及主目录
# -r 参数：同时删除用户主目录

# 修改密码
passwd                           # 修改当前用户密码
passwd zhangsan                  # 修改指定用户密码（需root权限）

# 查看用户信息
id 用户名                         # 查看用户ID信息
# 输出示例: uid=1001(用户名) gid=1002(组名) groups=1002(组名)

用户组操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 查看用户和组
cat /etc/passwd                   # 查看所有用户
cat /etc/group                    # 查看所有用户组

# 创建和删除组
groupadd 组名                     # 创建用户组
groupdel 组名                     # 删除用户组

# 查看用户所属组
groups                           # 查看当前用户所在组
groups 用户名                     # 查看指定用户所在组

# 用户加入组
usermod -g 组名 用户名            # 修改用户主组
gpasswd -a 用户名 组名            # 将用户添加到附加组

# 从组中移除用户
gpasswd -d 用户名 组名            # 将用户从组中删除
# 注意：组名不能是用户的主组

3.7 文件权限

文件类型识别

使用 ll 命令查看文件权限信息：

1

ll                               # 显示详细文件信息

Linux 7种文件类型：

1
2
3
4
5
6
7

-rw-rw-rw   -  普通文件
drw-rw-rw   d  目录（Directory）
srw-rw-rw   s  套接字文件（Socket）
brw-rw-rw   b  块设备（Block device）
crw-rw-rw   c  字符设备（Character device）
lrw-rw-rw   l  符号链接（Link）
prw-rw-rw   p  管道文件（Pipe）

权限详解

权限表示：

• r（read）：读权限，值=4
• w（write）：写权限，值=2
• x（execute）：执行权限，值=1
• rwx：所有权限，值=7（4+2+1）

常见权限值：

• 644：rw-r–r–（文件常用）
• 755：rwxr-xr-x（目录常用）
• 777：rwxrwxrwx（完全开放，不推荐）

权限结构解析

以 drwxr-xr-x 为例：

1
2
3
4
5
6

d rwx r-x r-x
│  │   │   │
│  │   │   └─ 其他用户权限（Others）
│  │   └───── 用户组权限（Group）
│  └───────── 文件所有者权限（Owner）
└──────────── 文件类型

位置说明：

• 第1位：文件类型
• 第2-4位：属主权限（创建者）
• 第5-7位：属组权限（所属组）
• 第8-10位：其他用户权限

文件中rwx的含义

1
2
3

r : 可查看文件内容（如 cat 命令）
w : 可编辑或删除文件
x : 可作为命令执行

目录中rwx的含义

1
2
3

r : 可列出目录内容（ls 命令）
w : 可在目录中创建文件
x : 可切换进入目录（cd 命令）+ 查看详细信息（ls -l）

权限修改命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 修改权限
chmod 640 aa.txt                 # 设置文件权限为640
chmod -R 755 /usr/local         # 递归设置目录权限
# -R : 递归应用到子文件和子目录

# 修改所有者
chown centos aa.txt             # 修改文件所有者
chown -R centos /usr/local      # 递归修改所有者

# 修改所属组
chgrp centos aa.txt             # 修改文件所属组
chgrp -R centos /usr/local      # 递归修改所属组

# 同时修改所有者和所属组
chown centos:centos aa.txt      # 一次性修改
chown -R centos:centos /usr/local  # 递归修改

# 查看当前用户所在组
groups

3.8 文档处理

文本搜索与处理

1
2
3
4
5
6
7
8
9
10
11
12
13

# 文本搜索
grep 'keyword' 文件名            # 搜索包含关键词的行
ps -ef | grep tomcat            # 查找进程

# 排序和去重
sort 文件名                      # 排序输出
cat aa.log | sort               # 排序日志内容
uniq                            # 去除相邻重复行
cat aa.txt | sort | uniq        # 排序后去重

# 统计
wc 文件名                        # 统计行数、单词数、字符数
cat aa.txt | wc                 # 输出格式：行数 单词数 字符数

日志查看与分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 关键词上下文查看
grep -A 100 'Exception' catalina.out    # 关键词后100行（After）
grep -B 100 'Exception' catalina.out    # 关键词前100行（Before）
grep -C 100 'Exception' catalina.out    # 关键词上下100行（Center）

# 管道方式
cat catalina.out | grep -C 100 'Exception'
cat catalina.out | grep -A 100 'Exception'
cat catalina.out | grep -B 100 'Exception'

# 实时查看日志
tail -f catalina.out                    # 实时查看日志
tail -100f catalina.out                 # 实时查看最后100行
tail -f -n 100 catalina.out             # 同上

3.9 网络通讯

网络工具

1
2
3
4
5
6
7
8
9
10

# 网页抓取
curl https://example.com         # 抓取网页内容

# 文件下载
wget https://example.com/file    # 下载文件

# 命令确认
yes                             # 自动输入y确认
y                               # 输入y确认
no 或 n                          # 输入no或n拒绝

网络配置与测试

1
2
3
4
5
6
7

# IP查看
ifconfig                        # 查看本机IP配置
curl ipinfo.io/ip              # 查看外网IP
curl ifconfig.me               # 查看外网IP（备选）

# 连通性测试
ping 域名或IP                   # 测试网络连通性

端口与进程查看

1
2
3
4
5
6
7
8
9
10
11

# 端口占用查看
lsof -i 端口号                  # 查看端口占用情况
lsof -i 8000                   # 查看8000端口使用情况

# 安装lsof（如未安装）
yum -y install lsof

# 网络连接查看
netstat                        # 查看所有网络端口
netstat -nlp                   # 查看监听端口
netstat -tunlp | grep 8000     # 查看指定端口

netstat 参数说明：

1
2
3
4
5

-t (tcp)    : 仅显示tcp相关选项
-u (udp)    : 仅显示udp相关选项
-n          : 拒绝显示别名，全部转化为数字
-l          : 仅列出在监听(Listen)的服务
-p          : 显示建立连接的程序名

3.10 备份压缩

tar 压缩与解压

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 解压命令
tar -zxvf xxx.tar.gz                    # 解压.tar.gz文件
tar -zxvf xxx.tar.gz -C /usr/local      # 解压到指定目录
tar -xvf xxx.tar                        # 解压.tar文件

# 压缩命令
tar -zcvf xxx.tar.gz ./file/*           # 压缩为.tar.gz
tar -cvf xxx.tar ./file/*               # 压缩为.tar

# 不同格式压缩（压缩率递增，速度递减）
tar -zcvf file.tar.gz 目录               # .tar.gz格式
tar -jcvf file.tar.bz2 目录              # .tar.bz2格式
tar -Jcvf file.tar.xz 目录               # .tar.xz格式

# 通用解压
tar -xvf 压缩文件                        # 自动识别格式解压

压缩格式对比：

• tar.gz：常用，压缩适中
• tar.bz2：压缩率高，速度较慢
• tar.xz：压缩率最高，速度最慢

zip 压缩与解压

1
2
3
4
5

# 压缩
zip a.zip a.txt                         # 压缩为zip格式

# 解压
unzip a.zip                             # 解压zip文件

3.11 Linux上rz和sz的使用

对于小文件传输，可以使用rz/sz命令，无需XFTP或WinSCP。

安装

1

yum -y install lrzsz

使用

1
2

rz                              # 上传文件到服务器
sz 文件名                        # 下载文件到本地

使用场景：

• 小文件快速传输
• 临时文件上传下载
• 配合Xshell等终端使用

Shell重定向详解

标准文件描述符

1
2
3

0 : 标准输入（stdin）  - 键盘
1 : 标准输出（stdout） - 屏幕
2 : 错误输出（stderr） - 屏幕

/dev/null 黑洞设备

1
2

/dev/null                       # Linux空设备文件
                                # 所有写入内容都会被丢弃

常用重定向组合

1
2
3
4
5
6
7
8
9
10
11
12
13

command > file                  # 标准输出重定向到文件
command 2> file                 # 错误输出重定向到文件
command > file 2>&1             # 标准输出和错误输出都重定向到文件
command &> file                 # 同上（简写）
command >> file                 # 追加标准输出到文件
command 2>> file                # 追加错误输出到文件

# 丢弃所有输出
command > /dev/null 2>&1        # 标准输出和错误输出都丢弃
command &> /dev/null            # 同上（简写）

# 后台运行
nohup command > /dev/null 2>&1 &   # 后台运行并丢弃所有输出

重定向顺序的重要性

1
2
3
4
5
6
7
8
9
10
11
12
13

# 正确写法
>/dev/null 2>&1
# 执行顺序：
# 1. 标准输出重定向到/dev/null
# 2. 错误输出重定向到标准输出（即/dev/null）
# 结果：两者都被丢弃

# 错误写法
2>&1 >/dev/null
# 执行顺序：
# 1. 错误输出绑定到当前标准输出（屏幕）
# 2. 标准输出重定向到/dev/null
# 结果：标准输出被丢弃，错误输出仍显示在屏幕

nohup 命令详解

1
2
3
4
5
6

nohup command &                     # 后台运行，输出到nohup.out
nohup command > log.txt 2>&1 &     # 后台运行，输出到log.txt
nohup command > /dev/null 2>&1 &   # 后台运行，不产生任何输出

# 常用于启动Java服务
nohup java -jar xxxx.jar > /dev/null 2>&1 &

重点建议

1. 实践为主

• 购买云服务器进行实际操作
• 每个命令都亲自尝试
• 出错是正常的，重要的是理解为什么出错

2. 循序渐进

• 先掌握基础命令
• 再学习高级特性
• 最后进行综合应用

3. 善用帮助

1
2
3

man 命令                        # 查看命令手册
command --help                 # 查看命令帮助
whatis 命令                     # 查看命令简介

4. 命令组合

• 熟练使用管道符 |
• 掌握重定向符号 > >>
• 学会使用 && 和 || 连接命令

5. 安全意识

• 谨慎使用 rm -rf 命令
• 修改系统文件前做好备份
• 使用非root用户进行日常操作
• 定期备份重要数据

6. 效率提升

• 使用Tab键自动补全
• 使用历史命令（↑↓方向键）
• 学习vim或nano编辑器
• 掌握快捷键（Ctrl+C、Ctrl+Z等）

7. 日志管理

1
2
3
4

# 查看系统日志
tail -f /var/log/messages      # 系统日志
tail -f /var/log/secure        # 安全日志
tail -f /var/log/cron          # 定时任务日志

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class048的内容，总结了二维前缀和、二维差分和离散化技巧的核心思想和应用。这些技巧是处理二维矩阵问题的重要工具，特别适用于矩形区域的批量查询和修改。

前置知识

在学习二维前缀和与差分之前，需要掌握以下基础知识：

• 一维前缀和与差分的原理
• 矩阵的基本操作
• 容斥原理的理解
• 坐标系统和索引处理

048【必备】二维前缀和、二维差分、离散化技巧

核心概念

二维前缀和的基本思想

二维前缀和是一维前缀和在二维空间的扩展：

• 原理：预处理出每个位置到左上角(0,0)的矩形区域和
• 查询优化：任意矩形区域的和查询在O(1)时间内完成
• 核心公式：使用容斥原理计算矩形区域和

二维差分的基本思想

二维差分用于优化矩形区域的批量修改：

• 原理：将矩形区域修改转化为四个关键点的修改
• 适用场景：大量矩形修改操作，最后统一查询
• 实现方式：通过四点修改实现区域增减，最后二维前缀和还原

离散化技巧

离散化用于处理坐标范围过大的问题：

• 核心思想：将大范围坐标映射到小范围数组
• 关键步骤：收集关键坐标、排序去重、建立映射关系
• 应用场景：坐标值很大但关键点有限的问题

题目一：二维前缀和模板

问题描述

给定一个二维矩阵matrix，实现一个类来处理以下类型的多次查询：

• 计算其子矩形范围内元素的总和，该子矩形的左上角为(row1, col1)，右下角为(row2, col2)。

测试链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/

核心思想

通过预计算二维前缀和，实现O(1)时间复杂度的矩形区域和查询：

1. 前缀和构建：s[i][j] 存储从左上角(0,0)到右下角(i-1,j-1)的区域和
2. 容斥原理：利用四个矩形的加减关系计算目标区域
3. 边界处理：通过增加一圈0来简化边界判断

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

from typing import List

class NumMatrix:
    """
    通过预计算二维前缀和，实现O(1)时间复杂度的矩形区域和查询。
    核心思想 (Inclusion-Exclusion Principle):
    1. 创建一个比原矩阵行列各大1的前缀和矩阵 `self.s`。
    2. `self.s[i][j]` 存储原矩阵中从左上角 (0,0) 到右下角 (i-1,j-1) 的矩形区域内所有元素的和。
    3. 构建公式: s[i][j] = matrix[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
       (当前格子的值 + 上方矩形和 + 左方矩形和 - 左上方被重复计算的矩形和)
    4. 查询 (r1,c1)到(r2,c2)的区域和:
       ans = s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1]
       (大矩形 - 上方多余矩形 - 左方多余矩形 + 左上方被重复减去的矩形)
    """
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.s = [[0]]
            return
            
        n = len(matrix)
        m = len(matrix[0])
        # s 的行列都比原 matrix 大 1，方便处理边界
        self.s = [[0] * (m + 1) for _ in range(n + 1)]
        
        # 构建前缀和矩阵，在左边上边和左上补0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                self.s[i][j] = matrix[i - 1][j - 1] + self.s[i - 1][j] + self.s[i][j - 1] - self.s[i - 1][j - 1]

    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        # 传入的r1, c1, r2, c2是0-indexed, 对应到前缀和矩阵需要+1
        r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1
        return self.s[r2][c2] - self.s[r1 - 1][c2] - self.s[r2][c1 - 1] + self.s[r1 - 1][c1 - 1]