记忆化搜索 记忆化搜索是一种通过存储已经计算过的结果来优化搜索过程的技术。 它结合了动态规划的效率和深度优先搜索的简洁性，特别适合解决具有重叠子问题的搜索问题。 基本概念 记忆化搜索的核心思想是：  在搜索过程中记录已经计算过的状态 当再次遇到相同状态时直接返回记录的结果 避免重复计算，提高效率 本质是"自顶向下"的动态规划  实现方式 记忆化搜索主要包含以下步骤：  设计状态表示方式 创建记忆化数组/哈希表 实现递归搜索函数 在搜索前检查是否已有记录 在返回前保存结果  基本实现   cpp   java   python   int fibonacci(int n, v...

广度优先搜索 广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树/图的算法。 它的基本思想是从一个顶点开始，先访问所有相邻节点，然后再按照同样的顺序访问相邻节点的相邻节点。 基本概念 BFS 的工作原理类似于水波纹扩散：  从起点开始，向四周扩散 访问所有距离为1的节点 再访问所有距离为2的节点 以此类推，直到访问完所有可达节点 保证先访问距离近的节点，后访问距离远的节点  实现方式 BFS 主要使用队列来实现，基本步骤：  将起始节点放入队列 取出队首节点访问 将其未访问的相邻节点加入队列 重复步骤2-3直到队列为空  基本实现 void bfs(i...

深度优先搜索 深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索树/图的算法。 它的基本思想是从一个顶点开始，尽可能深地搜索树的分支。 基本概念 DFS 的工作原理类似于走迷宫：  从起点开始，选择一个方向前进 一直走到无法继续为止 返回到上一个还有其他出路的位置 选择另一个方向继续探索 重复以上步骤直到找到目标或探索完整个迷宫  实现方式 DFS 主要有两种实现方式：  递归 栈  递归实现   cpp   java   python   void dfs(int node, set<int>& visited, vector<v...

搜索 深度优先搜索 (DFS) 深度优先搜索是一种优先走到最深的搜索算法。 特点  空间复杂度：，其中h为搜索树深度 时间复杂度：，其中b为分支因子，d为深度 适用于求解所有可能的解或最优解  分类    算法 问题描述 应用场景     普通DFS 无优化的深搜 排列、组合、子集   剪枝DFS 带优化的深搜 八皇后、数独、迷宫   记忆化DFS 状态记录的深搜 动态规划相关问题   双向DFS 从起点和终点同时搜索 最短路径、状态转换    广度优先搜索 (BFS) 广度优先搜索是一种层层推进的搜索算法。 特点  空间复杂度：，其中b为分支因子，d为深度 时间复杂度： 适用于求解最短路径或...

优先队列 问题描述 优先队列是一种特殊的队列，其中的元素都有一个优先级。 在C++中为priority_queue，Java中为PriorityQueue，Python中使用heapq模块。 默认情况下，优先队列按照元素从大到小的顺序出队。 基本概念 特点  元素有优先级 自动排序 堆实现 动态调整 支持自定义比较  代码实现  C++ Priority Queue  #include <iostream> #include <queue> #include <vector> using namespace std; int main() { // 创建优先...

队列 问题描述 队列是一种先进先出(FIFO)的数据结构。 在C++中为queue，Java中为Queue接口，Python中为queue模块。 它提供了在一端插入另一端删除的操作能力。 基本概念 特点  先进先出 只能访问队首和队尾 支持入队和出队 可以检查队空 可以查看队首元素  代码实现  C++ Queue  #include <iostream> #include <queue> using namespace std; int main() { // 创建队列 queue<int> q; // 入队 q.push(1); q.push(2); q...

栈 问题描述 栈是一种后进先出(LIFO)的数据结构。 在C++中为stack，Java中可用ArrayDeque模拟，Python中可用list模拟。 它提供了在一端进行插入和删除操作的能力。 基本概念 特点  后进先出 只能访问栈顶 支持压栈和弹栈 可以检查栈空 可以查看栈顶元素  代码实现  C++ Stack  #include <iostream> #include <stack> using namespace std; int main() { // 创建栈 stack<int> s; // 压栈 s.push(1); s.push(2); s...

映射 问题描述 映射是一种存储键值对的数据结构。 在C++中为map，Java中为HashMap，Python中为dict。 它们都提供了通过键快速访问值的能力。 基本概念 特点  键值对存储 键的唯一性 快速查找 动态添加删除 支持迭代访问  代码实现  C++ Map  #include <iostream> #include <map> #include <string> using namespace std; int main() { // 创建映射 map<string, int> m1; // 空映射 map<string, ...

集合 问题描述 集合是一种存储唯一元素的数据结构。 在C++中为set，Java中为HashSet，Python中为set。 它们都能自动去重，并提供高效的成员检测。 基本概念 特点  元素唯一性 自动去重 无序性（HashSet和Python set） 有序性（C++ set） 高效的查找  代码实现  C++ Set  #include <iostream> #include <set> using namespace std; int main() { // 创建集合 set<int> s1; // 空集合 set<int> s2 = {1...

字符串 问题描述 字符串是一种特殊的序列，用于存储字符数据。 在C++中为string，Java中为String，Python中为str。 它们都提供了丰富的字符串处理方法。 基本概念 特点  字符序列 支持随机访问 提供字符串操作 不可变性（Java和Python） 支持迭代遍历  代码实现  C++ String  #include <iostream> #include <string> using namespace std; int main() { // 创建字符串 string str1; // 空字符串 string str2 = "Hello...

序列 问题描述 序列是一种动态数组数据结构，可以根据需要动态调整大小。 在C++中为vector，Java中为ArrayList，Python中为list。 它们都提供了添加、删除、访问等基本操作。 基本概念 特点  动态调整大小 支持随机访问 支持尾部快速操作 内存连续存储 支持迭代遍历  代码实现  C++ Vector  #include <iostream> #include <vector> using namespace std; int main() { // 创建vector vector<int> nums; // 空vector vect...

类与结构体 问题描述 类和结构体是面向对象编程的基本单元，用于将数据和操作数据的方法组织在一起。它们提供了一种将相关数据和功能封装的方式。 基本概念 特点  数据封装 访问控制 继承和多态（类） 构造和析构 成员函数和变量  代码实现  结构体    c++   java   python   // 基本结构体 struct Point { int x, y; // 默认public Point(int x = 0, int y = 0) : x(x), y(y) {} // 构造函数 double distance(const Point& other) { int dx = x -...

数组 问题描述 数组是一种线性数据结构，用于存储相同类型的数据元素。它在内存中是连续存储的，可以通过索引快速访问元素。 基本概念 特点  连续存储空间 固定大小（部分语言支持动态数组） 支持随机访问 适用于线性存储和查找  代码实现  一维数组    c++   java   python   // 数组声明和初始化 int arr1[5] = {1, 2, 3, 4, 5}; // 静态数组 vector<int> arr2 = {1, 2, 3, 4, 5}; // 动态数组 // 访问元素 cout << arr1[0] << endl; // 输出第...

函数与递归 问题描述 函数是一段完成特定功能的代码块，可以被重复调用。递归是函数调用自身的一种特殊情况，常用于解决具有重复性质的问题。 基本概念 特点  函数有参数和返回值 函数体是独立的代码块 递归需要有终止条件 适用于模块化编程  代码实现  基本函数    c++   java   python   // 函数声明 int add(int a, int b); // 一般来说，只要函数之间不互相调用，可以不声明 void printMessage(string msg); // 按顺序定义在 main 函数之前即可 double average(vector<int>&amp...