HespethornのBlog

第一次写递归的人，脑子里通常有个挥之不去的念头："我得把每一次调用都想象清楚，才算写对。"结果越想越乱，最后放弃、改写成循环。但递归真正的法门恰恰相反——你不必追踪每一次调用的细节，你只需要相信：子问题已经被正确地解决了。这种"信仰之跃（leap of faith）"是 CS61A 教给你最重要的思维转换之一。本篇从最干净的线性递归，一直讲到会"指数爆炸"的树形递归。 一、递归是什么：函数自己调用自己是什么：递归（recursion） = 一个函数在自己的定义里调用自己。一个"正确且能停"的递归必须满足三条，CS61A 叫它"递归三定律"： 有一个或多个基例（base case）：不再自我调用，直接返回；这是递归的"刹车"。 每次递归都在向基例化简：问题规模严格变小，绝不允许越调越大。 递归调用解决子问题，再把子问题的结果组合成总结果。 缺了第 1 条 → 无限递归，栈炸；缺了第 2 条 → 永远到不了基例，同样栈炸。两条是递归的命门。 二、线...

导言作为具备一定工程实践经验的中级软件工程师，在日常软件开发工作流中，C++ 标准模板库（Standard Template Library，STL）的容器与算法体系已成为不可或缺的编程工具。vector 的动态内存管理机制、map 的有序键值对存储特性，以及 sort 算法的高效执行范式，这些看似常规的编程操作，实则蕴含着深邃的计算机科学设计思想。通过研读侯捷所著《STL 源码剖析》，得以系统性解构 STL 的底层实现逻辑，深刻体会到 "知其然更知其所以然" 在软件工程领域的重要价值。 一、数据结构：从应用层到实现层的认知跃迁在数据结构层面，STL 核心容器的底层实现机制在书中得到细致解析。以 vector 容器为例，其动态数组特性不仅体现在可扩展的存储容量上，更在于其内存管理策略的精妙设计。当容器容量不足时，vector 采用指数级扩容策略（通常为原容量的 2 倍或 1.5 倍，依具体实现而定），通过重新分配内存空间、元素迁移及旧内存释放的流程，在空间复杂度与时间复杂度之间实现了高效平衡。这种 "以空间换时间" 的策略，有效规避了频繁内...

学到这你大概已经能写"命令式"程序了：定义几个函数、调来调去、用 if/for 控制流程。但 CS61A 真正的第一个分水岭在这一篇——当你意识到"函数"可以像数字一样被传来传去、被装进盒子、被工厂批量生产，"编程"这件事的维度就升了一级。这种能"吃函数、拉函数"的函数，叫高阶函数（higher-order function）。它是后面装饰器、回调、甚至整个函数式编程的地基。 一、什么是"一等公民"：函数不是语法糖，是值是什么：在 Python 里，函数和数字、字符串一样，是货真价实的对象（object）。这意味着函数可以：被赋值给变量、当参数传给别的函、作为返回值、存进容器。具备这种待遇的，叫一等公民（first-class citizen）。 1234567def square(x): return x * xf = square # 函数赋值给变量（没加括号，不是调用！）print(f(4)) # 16print(type(f)...

在Python中，处理正则表达式的标准库是re。你可以把它想象成一把文本处理的“瑞士军刀”，专门用来在海量文本中查找、提取、替换或验证特定格式的字符串。 一、核心工具箱：5个最常用的方法在使用前，记得先导入模块：import re 方法 作用 形象比喻 返回值 re.match() 从开头匹配 “必须从门口进入” 匹配成功返回对象，失败返回None re.search() 扫描全文找第一个 “在屋里找一遍，找到就停” 匹配成功返回对象，失败返回None re.findall() 找到所有匹配项 “把所有符合条件的都抓出来” 列表 ['a', 'b', ...] re.sub() 替换文本 “把这里的A换成B” 替换后的新字符串 re.split() 按规则分割 “按这个符号切开” 分割后的列表 二、代码实战：一看就懂1. 查找与提取(search vs findall)如果你想提取文本中的手机号或数字： 123456789101112import retext = "我的手机号是 13800138000，备...

一、计算思维的本质与形式化表达1.1 信息处理的抽象模型与问题抽象计算机科学核心是信息符号操纵体系，从图灵机到现代系统，均为 "输入 - 处理 - 输出" 的具象实现。计算思维通过建立现实与符号系统映射实现问题可计算，这种抽象过程包含三个关键步骤：问题特征提取、符号系统选择与映射规则定义。这种抽象能力，正是计算机解决问题的前提，体现了从具体到抽象的认知跃迁，也印证了问题解决需建立与抽象模型间映射关系的理论。 1.2 指令序列的执行逻辑与计算思维维度计算过程的本质是按确定规则执行指令序列，这种确定性是可计算性的基础。指令通过顺序、分支和循环三种基本结构，构成复杂计算的控制流，体现了计算思维将问题拆解为可计算步骤的核心逻辑。 指令执行模型展现过程分解思维：复杂计算可拆分为有序的基本操作，执行路径明确，结果可预测。这种分解基于对问题逻辑的深入理解，需借助可计算性理论判断问题是否可解，并设计有限步骤的算法，确保在合理时间复杂度内得出确定解。 二、编程的思维框架2.1 程序结构的模块化组织与抽象层次驾驭C 语言以函数实现模块化，将复杂程序分解为相对独立的功能模块，通过接...

很多人学编程是从"记语法"开始的：先背 if 怎么写、for 怎么写，再背一堆库函数。CS61A 偏不这么干。它开篇就抛出一个看似哲学的问题：计算机到底是怎么把"名字"和"值"对应起来的？把这个想明白，后面高阶函数、递归、面向对象都不是新东西，只是同一套"名字—值"规则的变体。这一篇，我们先把最底层的"调用"和"环境"拆开看透。 一、调用表达式：你以为的"先算哪个"其实是铁律写 square(3 + 4) 时，大脑下意识就知道要先算 3+4 再平方。但"下意识"在编程里不够——它是一条求值规则，而且顺序不能乱。 是什么：Python 里 操作符(操作数, 操作数, ...) 这种结构叫调用表达式（call expression）。求值分两步，顺序很关键： 先按从左到右的顺序，把每个操作数（operand）求值成"值"； 再把操作符（也就是那个函数对象）作用在已经求好值的操作数上。 12345de...

一、什么是re.IGNORECASE？re.IGNORECASE是Python re模块中的一个标志（Flag），用于在执行正则表达式匹配时忽略字母的大小写。它的简写形式是re.I。 二、为什么使用它？默认情况下，正则表达式是区分大小写的。例如，模式python只能匹配小写的"python"，无法匹配"Python"或"PYTHON"。使用re.IGNORECASE可以解决这个问题，让匹配过程对大小写不敏感，这在处理用户输入、日志分析或关键词搜索时非常实用。 三、如何使用？1. 在函数中直接使用123456789101112import retext = "The quick Brown fox jumps over the lazy dog."pattern = "brown"# 不加re.IGNORECASE，匹配失败result1 = re.search(pattern, text)print(result1) # 输出: None# 加上re.IGNORECASE，成功匹...

引言：迭代器的核心价值在 C++ 标准模板库 (STL) 中，迭代器扮演着 "胶水" 的角色，它连接了容器与算法，使算法能够独立于具体容器类型工作。这种抽象机制带来了极大的灵活性 —— 同一个排序算法可以作用于向量 (vector)、链表 (list) 或数组 (array)，只需它们提供兼容的迭代器。 迭代适配器则是在基础迭代器之上的增强，通过包装现有迭代器，提供反向遍历、插入操作等特殊行为，进一步扩展了迭代器的能力。本文将系统解析迭代器的分类、实现原理及迭代适配器的应用场景。 一、迭代器基础：概念与分类1.1 迭代器的本质迭代器本质上是一种泛化的指针，它重载了*、->、++等运算符，使开发者能够以统一的方式访问容器中的元素，而不必关心容器的内部实现细节。 1234567891011121314151617181920212223#include <vector>#include <list>#include <iostream>// 通用打印函数，适用于任何提供输入迭代器的容器template<typenam...

一、函数对象的本质函数对象（也称为仿函数，Functor）是*重载了函数调用运算符***operator()**的类或结构体的实例。这种特殊的设计使它能够像普通函数一样被调用，同时又具备对象的所有特性。 12345678910111213141516// 一个简单的函数对象类struct Add { // 重载函数调用运算符 int operator()(int a, int b) const { return a + b; }};// 使用方式int main() { Add add; int result = add(3, 5); // 像函数一样调用对象 // 也可以直接使用临时对象 int result2 = Add()(10, 20); return 0;} 从本质上讲，函数对象是一个带行为的对象，而普通函数是一段可执行代码。这种本质差异决定了它们在功能和适用场景上的不同。 二、函数对象与普通函数的核心区别2.1 状态管理能力这是两者最根本的区别...

一、什么是模块？在Python中，模块是一个包含Python定义和语句的文件。文件名就是模块名加上.py后缀。例如，一个名为my_module.py的文件就是一个名为my_module的模块。 二、导入模块1. 基本导入1234import my_module# 使用模块中的函数my_module.say_hello() 2. 导入特定函数1234from my_module import say_hello# 直接使用函数say_hello() 3. 导入所有函数1234from my_module import *# 直接使用模块中的所有函数say_hello() 4. 导入并别名12345678910import my_module as mm# 使用别名访问模块mm.say_hello()# 或者from my_module import say_hello as sh# 使用别名访问函数sh() 三、模块的搜索路径当你导入一个模块时，Python会按照以下顺序搜索模块： 当前目录 PYTHONPATH环境变量中指定的目录 标准库目录 任何.pth文件中指定的目...

导言在现代 C++ 开发中，lambda 表达式（匿名函数）已经成为编写简洁高效代码的重要工具。尤其在配合 STL 算法（如for_each）时，lambda 表达式能够消除编写命名函数或函数对象的额外开销，使代码更加紧凑直观。 一、Lambda 表达式的基本语法lambda 表达式的完整语法结构如下： 123[capture](parameters) mutable noexcept -> return_type { // 函数体} 各组成部分的含义： [capture]：捕获列表，定义 lambda 表达式可以访问的外部变量 (parameters)：参数列表，与普通函数的参数列表类似 mutable：可选修饰符，允许修改按值捕获的变量 noexcept：可选修饰符，指定函数不会抛出异常 -> return_type：返回类型，当函数体只有 return 语句时可省略 {}：函数体，包含具体的执行逻辑 1.1 最简单的 Lambda 表达式最简化的 lambda 表达式可以省略参数列表、返回类型和修饰符，仅保留捕...

导言堆排序是一种基于二叉堆数据结构的高效排序算法，具有 O (n log n) 的时间复杂度和原地排序的特性。使用模板实现堆排序可以使其灵活适用于各种数据类型，并支持自定义比较规则。 一、堆排序算法原理堆排序主要分为两个阶段： 建堆阶段：将无序数组构建成一个二叉堆（最大堆或最小堆） 排序阶段：反复提取堆顶元素（最大值或最小值），并调整剩余元素维持堆特性 二叉堆是一种完全二叉树，对于最大堆，每个父节点的值大于或等于其子节点的值；对于最小堆，每个父节点的值小于或等于其子节点的值。 二、模板类实现下面是完整的HeapSort模板类实现，基于提供的框架结构： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <vector>#include <functional>...

一、文件操作的基本概念在Python中，文件操作是一个非常基础但重要的功能。Python提供了多种方式来处理文件，包括打开、读取、写入、关闭等操作。 二、文件的打开与关闭1. 基本打开方式12345# 打开文件f = open('file.txt', 'r')# 关闭文件f.close() 2. 使用with语句为了避免忘记关闭文件，我们可以使用with语句，它会自动处理文件的关闭： 1234with open('file.txt', 'r') as f: # 处理文件 pass# 文件会自动关闭 三、文件的读取1. 读取整个文件123with open('file.txt', 'r') as f: content = f.read() print(content) 2. 逐行读取123with open('file.txt', 'r') as f: for line in f: ...

一、引言上一篇文章介绍了unordered_map存放自定义类型的六种方法的理论框架，本文将通过完整可运行的代码示例，详细展示每种方法的具体实现细节。这六种方法是通过 2 种哈希实现方式与 3 种相等性比较方式组合而成，每种组合都有其独特的实现要点。 二、基础准备首先定义基础的Point类和测试函数，作为六种方法的共同基础： 12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <unordered_map>#include <string>#include <functional>// 自定义点类型class Point {private: int x; int y;public: Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {} int getX() const { re...

导言快速排序是一种高效的分治排序算法，平均时间复杂度为 O (n log n)。使用 C++ 模板实现快速排序可以使其适用于各种数据类型，配合比较器还能灵活调整排序规则。 一、快速排序算法原理快速排序的核心思想是： 选择一个元素作为 "基准"(pivot) 将数组分区，所有比基准值小的元素移到基准前面，比基准值大的元素移到基准后面 递归地对前后两个子数组进行排序 这种分治策略使快速排序成为实际应用中最快的排序算法之一。 二、模板类实现下面是完整的MyQsort模板类实现，支持任意可比较的数据类型和自定义比较规则： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <vector>#include <functional>#include &...

一、什么是海象运算符？海象运算符（Walrus Operator）是Python 3.8引入的新特性，它的语法是:=，读作“赋值表达式”。这个运算符的名字来源于它的外观，:= 看起来像一只眼睛和两颗长牙的海象。 二、与C++=运算符的区别与C++中=运算符不同，Python中的:=运算符在赋值后返回结果，而不是赋值前返回结果： C++：=运算符在赋值前返回结果，而不是赋值后返回结果 Python：:=运算符在赋值后返回结果，而不是赋值前返回结果 三、海象运算符的使用场景1. 在if语句中12345678# 传统写法user_input = input("请输入：")if user_input: print(f"你输入了：{user_input}")# 使用海象运算符if (user_input := input("请输入：")): print(f"你输入了：{user_input}") 2. 在while循环中123456789# 传...

引言std::unordered_map是 C++ 标准库中提供的无序关联容器，与std::map不同，它通过哈希表实现，因此需要两个关键组件：哈希函数（用于计算键的哈希值）和相等性比较函数（用于判断两个键是否相等）。当使用自定义类型作为unordered_map的键时，我们需要显式提供这两种组件。 一、核心概念std::unordered_map的模板定义如下： 1234567template< class Key, class T, class Hash = std::hash<Key>, // 哈希函数类型 class KeyEqual = std::equal_to<Key>, // 相等性比较类型 class Allocator = std::allocator<std::pair<const Key, T>>> class unordered_map; Hash类型必须满足Hash概念：Hash对象的operator()接受const Key&参数，返回s...

一、关联式容器与无序关联容器的核心区别关联式容器（如set、map、multiset、multimap）和无序关联式容器（如unordered_set、unordered_map、unordered_multiset、unordered_multimap）是 C++ STL 中两种不同的数据结构，核心区别在于底层实现和特性： 关联式容器：基于红黑树（一种自平衡二叉搜索树）实现，元素按照键（key）的有序性存储，默认通过less比较键的大小。 无序关联式容器：基于哈希表实现，元素存储顺序与键的大小无关，依赖哈希函数计算存储位置，通过键的哈希值快速访问元素。 二、如何选择：关联式容器 vs 无序关联式容器选择需根据具体场景的需求，主要从以下维度判断： 2.1 有序性需求 需要元素有序：优先选择关联式容器。例如： 需遍历元素时按键的大小排序（如set遍历默认升序）； 需频繁执行范围查询（如map::lower_bound、map::upper_bound获取键在[a, b]之间的元素）。 无需有序性：优先选择无序关联式容器，其插入、查找、删除的平均效率更高。 2.2 ...

一、异常继承体系的基本结构Python的内置异常继承体系是一个典型的“基类-派生类”家族结构。这个体系设计得非常精巧，它允许我们在写代码时，既可以抓具体的错，也可以抓“一类”错。 1. 核心继承关系 BaseException：所有异常的基类，包含系统退出相关的异常（如SystemExit） Exception：所有用户代码可处理的异常的基类 常见的派生异常： ArithmeticError：算术错误（如ZeroDivisionError） LookupError：查找错误（如KeyError, IndexError） ValueError：值错误 TypeError：类型错误 ImportError：导入错误 二、多态（Polymorphism）的绝佳体现Python的异常处理机制底层利用了“子类对象可以被视为父类对象”的多态特性。 1. 示例：捕获LookupError12345678data = {"name": "Alice"}try: # 尝试访问不存在的键 print(data["...

一、异常的基本概念在Python中，异常是指程序执行过程中发生的错误。当程序遇到错误时，会抛出异常，如果不处理这些异常，程序会终止执行。 二、异常处理的基本语法1. try-except语句123456try: # 可能会抛出异常的代码 result = 10 / 0except ZeroDivisionError: # 处理ZeroDivisionError异常 print("除数不能为零") 2. 捕获多个异常12345678910try: # 可能会抛出异常的代码 result = int(input("请输入一个数字")) print(10 / result)except ZeroDivisionError: # 处理ZeroDivisionError异常 print("除数不能为零")except ValueError: # 处理ValueError异常 print("请输入有效的数字") 3. 捕获所有异常123456t...

引言C++ 标准模板库（STL）提供了一系列功能丰富的容器，这些容器不仅封装了数据结构，还提供了大量成员函数用于操作数据。此外，STL 还包含许多与容器配合使用的非成员函数，它们扩展了容器的功能，使操作更加灵活。 一、通用成员函数几乎所有 STL 容器都提供了一组基础的通用成员函数，用于获取容器信息、修改容器状态等。 1.1 基本信息函数12345678910111213141516171819202122#include <iostream>#include <vector>#include <list>int main() { std::vector<int> vec = {1, 2, 3, 4, 5}; std::list<std::string> lst = {"apple", "banana", "cherry"}; // 容器大小相关 std::cout <<...

引言在 C++ 中使用std::map存储自定义类型作为键时，需要确保该类型能够被正确比较大小，因为std::map是一个有序关联容器，其内部通过比较操作来组织元素。本文将介绍三种方法来解决map中存放pair<Point, string>元素的问题，其中Point是一个自定义点类型。 核心概念std::map要求其键类型必须支持比较操作（默认使用<运算符）。对于自定义类型Point，我们需要通过以下三种方式之一提供比较能力： 为Point类重载<运算符 定义一个比较结构体（仿函数） 为Point准备std::less的特化模板 代码示例首先定义基础的Point类： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <math.h>#include <iostream>#include <set>using std::cout;using std::endl;...

一、引言：一个“错误”的直觉从初学者的视角切入：我们通常认为 self.name = name 就是把数据存进字典，self.name 就是把数据取出来。但在处理复杂对象（如Django模型、Pydantic、@property）时，这种理解是完全错误的。在Python的高级世界里，. 和 = 只是表象，真正的幕后黑手是 Getter 和 Setter。 二、第一层洋葱：@property 的伪装展示一段标准的 @property 代码： 12345678910111213141516class Student: def __init__(self, name): self.name = name @property def name(self): return self._name @name.setter def name(self, value): self._name = value# 看起来像是在访问属性，但实际上是在调用方法s = Student("Alice")print(s...

引言在 C++ 中，迭代器 (iterator) 和指针 (pointer) 是两个密切相关但又有所区别的概念。它们都可以用来访问内存中的数据，都支持类似的操作符 (如*和->)，但应用场景和功能范围却有显著差异。本文将深入解析迭代器与指针的关系、区别及各自的应用场景。 核心概念指针的本质指针是 C++ 从 C 语言继承而来的概念，是一个变量，其值为另一个变量的内存地址。指针直接指向内存中的某个位置，可以是： 普通变量的地址 数组元素的地址 动态分配内存的地址 函数的地址 迭代器的本质迭代器是 C++ 标准库提供的一种抽象，它模拟了指针的行为，为各种容器提供了统一的访问接口。迭代器可以看作是 "广义指针"，它使得算法可以独立于容器类型工作。 两者的核心关系 迭代器在很多方面模仿了指针的行为 指针可以看作是一种特殊的迭代器（用于原生数组） 所有指针都满足随机访问迭代器的要求 迭代器通常通过重载运算符来模拟指针的操作 代码示例指针与迭代器的基本使用对比123456789101112131415161718192021222324252627282930...

一、多进程的基本概念在Python中，进程是程序执行的独立单元。多进程编程允许程序同时执行多个任务，充分利用多核CPU的性能。与多线程不同，多进程不受GIL（全局解释器锁）的限制，可以真正实现并行执行。 二、进程的创建与启动1. 使用multiprocessing模块123456789101112131415161718192021import multiprocessingimport timedef task(name): print(f"Task {name} started") time.sleep(2) print(f"Task {name} completed")# 创建进程process1 = multiprocessing.Process(target=task, args=('A',))process2 = multiprocessing.Process(target=task, args=('B',))# 启动进程proce...