机器学习—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 { ...
数据结构与算法2—数组
数组是一种常见的线性数据结构，其将相同类型的元素存储在连续的内存空间中，我们将元素在数组中的位置称为该元素的索引。 1. 数组的常用操作1.1 初始化数组初始化数组时，我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0，但是经过实测，C++和C在数组为初始化时，大多数情况下不会将数组初始化为0，特别是使用new或malloc创建动态数组时数组元素都是随机值，因此在C++和C中建议创建完数组后就立刻将其初始化： 123456789101112/* 初始化数组arr */// 将数组存储在栈上int size = 5;int arr[5] = {0};printf("数组 arr = ");printArray(arr, 5);/* 初始化数组nums */// 将数组存储在栈上int nums[5] = {1, 2, 3, 4, 5};printf("数组 nums = ");printArray(nums,...
数据结构与算法1——基本概念与复杂度
1. 算法的定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 2. 算法的特性算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。 2.1 输入输出算法通常具有零个或多个输入，但至少有一个或多个输出。输出的形式可以是打印输出，也可以是返回一个或多个值。 2.2 有穷性有穷性指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。 2.3 确定性确定性指算法的每一步骤都具有确定的含义，不会出现二义性。 2.4 可行性可行性指算法的每一步都必须是可行的，也就是说每一步都能够执行有限次数完成。可行性意味着算法可以转化为程序上机运行，并得到正确的结果。 3. 算法设计的要求算法设计的要求包括正确性、可读性、健壮性、高效率和低内存需求。 3.1...
Python格式规范
1. Python命名规范1.1 文件名、包名、模块名、变量名、函数名、实例名全部采用小写的形式，并使用下划线连接，如下所示： 12my_car.pymy_car 1.2 类名采用驼峰命名法，即将类中的每个单词的首字母都大写，且不使用下划线，如下所示： 1ElectricCar 1.3 常量名所有字母大写，单词之间采用下划线连接，如下所示： 1MAX_NUM = 100 2. Google Python命名规范 模块名写法: module_name ;包名写法: package_name ;类名: ClassName ;方法名: method_name ;异常名: ExceptionName ;函数名: function_name ;全局常量名: GLOBAL_CONSTANT_NAME ;全局变量名: global_var_name ;实例名: instance_var_name ;函数参数名: function_parameter_name ;局部变量名: local_var_name . 3....
