CPP学习笔记—标准模板库（STL）中的容器
一、什么是容器？为什么它如此重要？简单来说，C++ 容器是用来存储和管理一组对象的类模板。它们就像是工具箱里不同种类的收纳盒：有的适合快速取放（像数组），有的适合保持物品有序（像分类文件柜），还有的适合快速查找（像带索引的卡片盒）。 使用 STL 容器的好处是巨大的： 代码更简洁：你无需从零开始实现链表、哈希表等复杂数据结构。 性能更优越：STL 容器经过了高度优化，性能通常比手写的要好。 代码更安全：它们处理了内存管理的细节，减少了内存泄漏和越界访问的风险。 互操作性强：所有容器都遵循一套统一的接口（如 begin(), end(), size()），可以与 STL 的迭代器和算法无缝协作，威力倍增。 二、容器的分类与概览C++ 的容器主要分为四大类，分别是序列容器、关联容器、无序关联容器和容器适配器。 类别 容器 特点 序列容器 vector, deque, list, array 元素按线性顺序排列，可通过位置访问。 关联容器 map, set, multimap, multiset 元素根据键值自动排序，查找速度快 (O(log...
CPP学习笔记—指针
一、指针到底是什么？—— 内存地址的“房卡”想象一下计算机的内存是一家长长的酒店，里面有无数的房间，每个房间都有一个独一无二的门牌号（内存地址）。 普通变量：就像一个房间，里面存放着具体的东西（值）。 1int age = 25; // 在一个叫 `age` 的房间里，放了数字 25。 指针：它本身也是一个变量，但它里面存放的不是普通的东西，而是一张房卡。这张房卡上写着另一个房间的门牌号。 所以，指针是一个存储了另一个变量内存地址的变量。通过这张“房卡”，我们就能找到并操作那个特定的“房间”。 二、两大核心操作符：& (取地址) 和 * (解引用)要玩转指针，必须掌握这两个“魔法”操作符。 1. & (取地址符) —— “制作房卡”& 符号的作用是获取一个变量的内存地址。可以把它读作“…的地址”。 12345int age = 25; // 一个存放 25 的房间 `age`int* p_age = &age; // 创建一张叫 `p_age` 的房卡， // 上面记录 `age`...
Python输入输出处理
核心知识点 input() vs sys.stdin.readline() input(): 内置函数，使用方便，但速度较慢。它会读取一行，去除末尾的换行符 \n，并返回一个字符串。 sys.stdin.readline(): 速度更快，因为它使用了缓冲区。它会读取一行，但保留末尾的换行符 \n。因此，通常需要配合 .strip() 或 .rstrip() 使用。 print() vs sys.stdout.write() print(): 内置函数，功能强大，可以自动在末尾添加换行符，但相对较慢。 sys.stdout.write(): 速度更快，但只接受字符串作为参数，且不会自动添加换行符，需要手动添加 '\n'。 对于追求极致性能的竞赛，推荐使用 sys 模块。 12import sys# 之后就可以使用 sys.stdin.readline() 和 sys.stdout.write() 一、 输入 (Input)场景1：读取单行数据1.1 读取一个字符串12345678910# 方法一：使用 input() (方便，但稍慢)s =...
机器学习—K近邻算法（KNN）
第一部分：KNN算法详解 (K-近邻算法)1. 核心思想KNN（K-Nearest Neighbors）是一种监督学习算法，既可以用于分类任务，也可以用于回归任务。它的核心思想是：一个样本的类别/数值，由其在特征空间中最邻近的 K 个样本的类别/数值来决定。 2. 算法步骤 (以分类任务为例)假设我们有一个带标签的训练数据集，现在来了一个新的、没有标签的数据点，我们要预测它的类别。 Step 1: 确定超参数 KK是一个正整数，代表我们要参考“邻居”的数量。这个值需要我们预先设定。比如，我们选择 K=3。 Step 2: 计算距离计算这个新的数据点与训练集中每一个数据点的距离。距离的度量方式有很多种，最常用的是： 欧氏距离 (Euclidean Distance):$$ d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2} $$ 曼哈顿距离 (Manhattan Distance):$$ d(x, y) = \sum_{i=1}^{n}|x_i - y_i|...
Python中的sort方法、sorted函数与lambda表达式
1. sort()方法1.1 sort()方法list.sort()最核心、也最需要记住的特点是：它会直接修改原始列表，使其变为有序状态。也就是原地排序。因此，sort()方法的返回值是None。部分初学者可能会将其结果赋值给新变量，这种用法是错误的。正确的用法是无需将其结果赋值给新变量，直接使用被修改后的原列表即可，如下所示： 123nums = [3, 1, 4, 1, 5, 9, 2]nums.sort()print(nums) 结果如下： 1[1, 1, 2, 3, 4, 5, 9] 1.2 基本语法和参数sort()方法的完整语法是： 1list.sort(*, key=None, reverse=False) 它接受两个可自选的关键字参数：key和reverse。 A. reverse参数这个参数非常直观 reverse = False（默认值）：升序排序 reverse = True：降序排序 123456numbers = [4, 2, 8, 1, 6]numbers.sort() # 默认升序print(numbers) # 输出:...
回溯
回溯算法（backtracking algorithm）是一种通过穷举来解决问题的办法，其本质是一种暴力搜索算法。它的核心思想是从一个初始状态出发，暴力搜索所有可能遇到的解决方案，当遇到正确的解则将其记录，直到找到解或尝试了所有可能的选择都无法找到解为止。 框架1234567891011121314151617def backtrack(state: State, choices: list[choice], res: list[state]): """回溯算法框架""" # 判断是否为解 if is_solution(state): # 记录解 record_solution(state, res) # 不再继续搜索 return # 遍历所有选择 for choice in choices: # 剪枝：判断选择是否合法 if is_valid(state, choice): #...
Python学习笔记7—集合
1. 集合的创建在前面几期已经介绍过了python中列表[]、元组()和字典{}的创建和使用，这一期要介绍的是另一个相似的结构，也就是哈希集合set()，和python中的哈希表也就是字典相似，集合set()也是用大括号{}来表示的，它可以用下面的方式进行初始化： 123456789101112nums = {1, 2, 3}print(nums)nums = set()nums.add(1)nums.add(2)nums.add(3)print(nums)nums = [1, 2, 3]num_set = set(nums)print(num_set) 上述三种方式打印的结果都是相同的，如下： 123{1, 2, 3}{1, 2, 3}{1, 2, 3} 值得注意的是，虽然集合和字典都用{}来表示，但是集合的初始化不能使用num_set = {}这种方式，因为这种方式只会创建出一个字典。 2. 集合的特性2.1...
数据结构与算法5—栈
栈（stack）是一种遵循先入后出逻辑的线性数据结构。 如图所示，我们将堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫做“入栈”，删除栈顶元素的操作叫做“出栈”。 1. 栈的常用操作栈的常用操作如下表所示： 方法 描述 时间复杂度 push() 元素入栈（添加至栈顶） $O(1)$ pop() 栈顶元素出栈 $O(1)$ peek() 访问栈顶元素 $O(1)$ 通常情况下，一些编程语言内置了栈类。当没有提供栈类时，可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。C++具有栈类stack可以直接使用，而Python的列表也有能轻易实现栈操作的方法，因此下面以C为例实现栈。 2. 栈的实现栈可以视为一种受限制的数组或链表，因为它只能在栈顶添加或删除元素。换句话说，我们可以通过屏蔽数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。 2.1...
数据结构与算法4—列表
列表（list）是一个抽象的数据结构概念，表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无需使用者考虑容量限制的问题。列表可以基于链表或数组实现。 链表天然可以看作一个列表，其支持元素增删改查操作，并且可以灵活动态扩容。 数组也支持元素增删改查，但由于其长度不可变，因此只能看作一个具有长度限制的列表。 由于数组不具备扩展长度的能力，因此可以使用动态数组来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。 许多编程语言中的标准库提供的列表是基于动态数组实现的，例如Python中的list、Java中的ArrayList、C++中的vector和C#中的List等。通常，将列表和动态数组视为等同的概念。 1. 列表常用操作1.1 初始化列表列表的初始化可以采用“无初始值”和“有初始值”这两种初始化方法： 12345/* 初始化列表 */// 无初始值vector<int> nums1;// 有初始值vector<int> nums = { 1, 3, 2, 5, 4 }; 1.2...
数据结构与算法3—链表
内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。 链表是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”或“指针”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。 链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。 链表节点ListNode除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。 1. 链表结构体不同编程语言中的链表结构体如下所示： 12345/* 链表节点结构体 */typedef struct ListNode { int val; // 节点值 struct ListNode *next; // 指向下一节点的引用} ListNode; 1234567/* 链表节点 */struct ListNode { ...
