哈希表（Hash Table），也常被称为散列表，是一种非常高效的数据结构，它可以以平均 O (1) 的时间复杂度完成插入、删除和查找操作。哈希表的核心思想是将 “键（Key）” 通过一个哈希函数（Hash Function）映射到一个数组的特定索引位置，从而实现快速的数据访问。1. 核心思想与组成一个哈希表主要由以下几个部分组成：哈希函数 (Hash Function)：这是哈希表的灵魂。它接收一个任意类型的 “键”（如字符串、数字等），并返回一个固定范围的整数，这个整数被称为哈希值（Hash Value）或索引（Index）。一个好的哈希函数应该具备以下特点：计算速度快。均匀分布：能将不同...

前缀和（Prefix Sum） 是一种非常重要且常用的算法技巧，它可以将多次查询数组区间和的时间复杂度从 O (N) 优化到 O (1)。其核心思想是空间换时间：通过预先计算并存储一个辅助数组（前缀和数组），来快速回答后续的大量区间和查询。1. 核心思想假设我们有一个原始数组 nums。我们定义一个前缀和数组 prefixSum，其中 prefixSum[i] 表示原始数组 nums 中从第 0 个元素到第 i 个元素的和。公式定义：prefixSum[0] = nums[0]prefixSum[1] = nums[0] + nums[1]prefixSum[2] = nums[0] + nu...

kmpKMP (Knuth-Morris-Pratt) 算法是一种高效的字符串匹配算法，用于在一个主字符串（文本 T）中查找一个模式字符串（P）的出现位置。与朴素的暴力匹配算法相比，KMP 算法通过一个巧妙的预处理步骤，避免了不必要的字符比较，从而将时间复杂度从 O (N*M) 降低到了 O (N+M)，其中 N 是文本长度，M 是模式长度。1. 核心思想KMP 算法的核心思想是利用已经匹配过的信息，避免主串指针的回溯。让我们通过一个例子来理解朴素算法的低效之处：文本 T: BBC ABCDAB ABCDABCDABDE模式 P: ABCDABD朴素算法的过程：BBC ABCDAB ABCDA...

暴力枚举与贪心算法相对的一种更基础、更直接的算法思想 ——暴力枚举（Brute-force Enumeration），也常被称为穷举法。1. 暴力枚举的核心思想暴力枚举的核心思想非常简单直接：生成所有可能的解，并逐一检查每个解是否满足问题的条件。它不依赖任何复杂的策略或启发式规则，而是通过系统性地探索问题解空间中的每一个候选解来寻找答案。工作流程通常是：定义解空间：明确问题的所有可能候选解构成的集合。生成候选解：按照某种顺序（例如，从小到大、从左到右）逐一生成每一个候选解。验证解：对于每一个生成的候选解，检查它是否符合问题的目标和约束条件。记录最优解：如果候选解满足条件，则记录下来。如果问题要...

贪心算法1. 贪心算法的核心思想贪心算法的核心在于 **“贪心”** 二字，它遵循以下原则：贪心选择性质 (Greedy Choice Property)：可以通过做出局部最优选择（即贪心选择）来构造全局最优解。也就是说，每一步都选择当前状态下最好的、最有利的选择，然后再去解决剩下的子问题。最优子结构 (Optimal Substructure)：一个问题的最优解包含其子问题的最优解。这是动态规划和贪心算法都需要满足的性质。关键点：贪心算法并不保证对所有问题都能得到最优解。它是否有效完全取决于问题本身的性质。2. 贪心算法的适用场景当一个问题同时具备贪心选择性质和最优子结构时，贪心算法通常是求...

二叉树是计算机科学中一种非常基础且重要的数据结构。它不仅是许多更高级数据结构（如红黑树、B + 树）的基础，也广泛应用于算法设计、数据库索引、编译器等领域。什么是二叉树？一个二叉树是由节点 (Node) 组成的有限集合，这个集合要么为空，要么由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。简单来说，一个二叉树的节点最多只能有两个子节点：一个左子节点和一个右子节点。核心特点：节点 (Node)：包含数据元素和指向左右子节点的指针（或引用）。根 (Root)：树的最顶层节点，没有父节点。子节点 (Child)：一个节点的直接后继节点。父节点 (Parent)：一个节点的直接前驱节...

1.map函数C++ 中的 std::map 是一个关联容器 (Associative Container)，它存储的是键值对 (key-value pairs)。它的主要特点是能够根据键（key）快速、高效地查找对应的值（value）。std::map 的底层实现通常是红黑树 (Red-Black Tree)，这是一种自平衡的二叉搜索树。键值对存储：每个元素都是一个 std::pair<const Key, Value> 对象。键的唯一性：在一个 map 中，所有的键都是唯一的，不能重复。自动排序：map 中的元素会自动根据键的大小进行排序。默认情况下，它使用 < 运算符进...

实验三1.int fun(vector <float>&s,int n){//传单个 vector<float>2. stu *a=new stu[n];//不支持传引用3.//固定数组的引用//const int MAX_STU = 50; //void shuchu(stu (&a)[MAX_STU], int n)3.单项链表（普通版）#include<iostream>using namespace std;struct node{ int num; node*next; // 构造函数，简化结点初始化 // node(int n =...

结构体下1./*子字符串查询：1.模糊查询a[i].name.find(cha)!=string::npos;pos 变量名，用来存储「子串 sub 在字符串 s 中的起始位置」（索引）std::string 类的一个静态常量，核心作用是表示 “字符串中未找到指定子串 / 字符”，也可理解为 “无效的索引值”s.find(sub) 从左到右查找第一个子串 sub s.find("abc")s.rfind(sub) 从右到左查找最后一个子串 sub s.rfind("abc")s.find_first_of(c) 查找第一个字符 c（或字符集合） s.fi...

结构体上1.结构体中如果有数组成员要一个个输入。2.排序sort(a,a+n,compare);//初始地址，结束地址，比较规则/* 降序排列1#include<functional> sort(arr,arr + n, greater<int>()); 2 lambda 表达式（仅供一次性使用）sort(a,a+m,[](stu &a,stu &b){return a.grade>b.grade;});[capture（必选）](parameters（必选）) -> return_type （可选）{ function_body }（必选）...

函数下1.求矩阵每行元素的和int sum_(int *p,int m,int n,int i){ int sum=0; for(int j=0;j<n;j++){ sum+=*(p+i*n+j); } return sum; } int main(){ int m,n; cin>>m>>n; int *p=new int[m*n];//动态分配 int *a=p;//保存首地址 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ cin>>*a; a++; } } for(int i=0;i<m;...

指针上1.用法int *p;p=&a;2.c++中swap函数接收的是值3.指针的引用void swap(int *&p1,int *&p2){//指针的引用}4.sort(p, p + t, greater<int>()); 降序排序5.求和函数#include<numeric>//求和头文件double solve(double *p,int t){ sort(p,p+t); double aver=accumulate(p,p+t,0);//初始值 return aver/t;}/*introsort内省排序(快速排序（Quicksort）...

函数下1.完数：该数恰好等于除自身外的因子之和。2。集合中没有重复元素。 集合A和集合B的“行知乘”被定义为：A中的每一个元素都与B中的每一个元素相乘，得到的所有乘积构成“行知乘”的结果集合。 例如：A={1,2,3,0};B={4,8,16},则A与B的“行知乘”结果为集合{4,8,16,32,12,24,48,0}。3.全局变量和局部变量1. 局部变量定义：在函数、循环、条件语句、代码块（如 {} 包裹的范围）内部定义的变量，只在这个 “小范围” 内生效。生命周期：从变量定义的位置开始创建，代码块 / 函数执行结束后立即销毁，占用的内存会被释放。作用域：仅限定义它的代码块内部，外部无法访问...

函数递归 1。递归两种不同的传法long long jiecheng(int *p){if(*p==0||*p==1){return 1;}int current = *p;(*p)--;//用指针return current*jiecheng(p);}long long Fibonacci(int p){if(p==1||p==2){return 1;}return Fibonacci(p-1)+Fibonacci(p-2);//传值}2.可记忆化递归记忆化递归是动态规划（Dynamic Programming）的一种实现形式（自顶向下的动态规划），是算法面试和竞赛中必须掌握的核心技巧，它能将原本效率低下的递归算法优化到极高的水平。这样做可以避免大量重复的计算，从而将算法的时间复杂度从指数级（如 O(2n)）降低到线性或线性对数级（如 O(n)或 O(nlogn)）。我们需要一个数据结构来存储已经计算过的结果。最常用的数据结构是哈希表（Hash Table）或数组（Array）。实现步骤：创建 “备忘录”（Memo）：定义一个全局或静态的哈希表 / 数组，用于存储已经计算过的子问题结果。键（Key）是子问题的参数，值（Value）是子问题的解。检查 “备忘录”：在递归函数的开头，首先检查当前要解决的子问题是否已经存在于 “备忘录” 中。如果存在，直接返回 “备忘录” 中存储的结果。如果不存在，才执行正常的递归计算。存入 “备忘录”：在计算出子问题的结果后，将其存入 “备忘录”，然后再返回该结果。典型样例：斐波那契数列#include <iostream>#include <unordered_map>// 1. 创建“备忘录”，使用静态变量确保在多次函数调用间共享// 键是 n，值是 fibonacci(n) 的结果static std::unordered_map<int, long long> memo;long long fibonacci_memo(int n) {// 基准条件 (Base Case)if (n <= 1) {return n;}// 2. 检查“备忘录”// 如果备忘录中已经有结果，直接返回，避免重复计算if (memo.find(n) != memo.end()) {return memo[n];}// 3. 如果备忘录中没有，则进行递归计算long long result = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);// 4. 将计算结果存入“备忘录”memo[n] = result;// 返回结果return result;}int main() {int n = 45;// 每次运行前清空备忘录，以防多次调用main函数时数据干扰memo.clear();std::cout << "Fibonacci(" << n << ") = " << fibonacci_memo(n) << std::endl;return 0;}核心思想：用空间换时间。通过存储中间结果，避免重复计算。适用场景：当递归函数存在大量重叠子问题时，记忆化递归是首选的优化方法。实现方式：通常使用一个哈希表或数组作为 “备忘录”，在递归函数中先查备忘录，再决定是否计算。3.十进制转二进制#include<iostream>#include<string>using namespace std;string exchange(int a){if(a==0)return "";char bit=(a%2)+'0';//转换成ASCII;string output=exchange(a/2);return output+bit;}