数据结构和算法

算法

枚举算法

描述：也称为穷举算法，按照问题本身性质，列举出该问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解。通常用于求解问题规模比较小的问题，或者作为求解问题的一个子算法。

核心思想：通过列举问题的所有状态，将它们逐一与目标状态进行比较，从而得到满足条件的解，关注枚举的上下界。

优点：简单基本，便于实现，容易调试，正确性容易证明。

流程：

• 确定枚举对象、枚举的上下界、判断条件。

• 枚举可能的情况并验证是否是问题的解。

• 考虑提高效率（缩小状态空间，限制枚举条件，找特殊性质避免重复求解）。

  题库：百钱买百鸡，LeetCode78，611，1504，1733，2048，2749。

 

贪心算法

描述：每一步都做出在当前看来是最好的选择，期望通过局部最优选择来达到全局最优解。

核心思想：局部最优，不可回溯，期望全局最优。

贪心只做局部最优选择，不保证全局最优。

优点：高效，简单直观。

流程：

• 建立数学模型
• 分解问题
• 制定贪心策略
• 求解子问题
• 合并成原问题解

题库：LeetCode134，1792，2598，3350，3397。

 

回溯算法

描述：通过深度优先(DFS)搜索策略来遍历所有可能的候选解，并在搜索过程中利用剪枝来避免无效搜索，提高效率。

核心思想：

• 路径：从根节点到当前节点所做出的选择序列。
• 选择列表：在当前节点可以做出的所有选择。
• 结束条件：找到一个解或停止。

流程：

• 在当前节点遍历所有选择
• 找到解做出选择并加入当前路径
• 递归进入下一个状态
• 递归返回后，撤销刚才的选择（回溯）

模板：

class Solution {
public:
    vector<result_type> result;  // 存储最终结果
    vector<current_path> path;   // 当前路径或状态

    void backtrack(参数列表) {
        if (满足终止条件) {
            result.push_back(path);
            return;
        }

        for (选择 in 选择列表) {
            if (不满足约束条件) continue;  // 剪枝

            path.push_back(选择);         // 做选择
            backtrack(更新参数);          // 递归进入下一层

            path.pop_back();              // 撤销选择（回溯）
        }
    }
};

可以配合lamdba表达式auto dfs{};

题库：LeetCode 22，39，77。

 

动态规划

描述：把原问题分解为相对简单的子问题的方式求解复杂问题的方法，能够避免重复计算子问题。

分成记忆化递归（自顶向下）和DP数组（自底向上）两种动态规划。

核心思想：拆分子问题、记住过往、减少重复计算。

流程：

• 穷举分析

• 确认边界

  • 找出规律，确定最优子结构
    • 动态规划问题即是递推问题，当前的决策结果是f(n)，则最有子结构就是要让f(n-k)最优，并且与后面的决策没有关系，能让后面的决策安心使用局部最优解。
  • 写出状态转移方程

题库：LeetCode62，120，1277，1504，2327，3186，3494。

 

位运算算法

大大提高程序的性能，0/1问题时好用。

题库：LeetCode78，2749。

 

模拟

描述：完全按照题目的描述或者问题的真实发生过程，一步步地用代码复现出来从而得到答案。

核心思想：重视还原，过程再现。

流程：

• 提炼规则
• 设计数据结构
• 分解步骤，模块化
• 注意边界

特点：思路直观，实现繁琐。

题库：LeetCode6，54，3446。

 

堆算法

描述：特殊的完全二叉树，可以用一维数组存储。

堆的更新和维护：

 入堆push()，时间复杂度O(log n)

 出堆pop()，时间复杂度O(log n)

 访问栈顶top()，时间复杂度O(1)

 建堆，时间复杂度O(nlog n)

# 即堆中插入n个元素

应用：优先队列。

题库：LeetCode 1792。

 

分支限界法

描述：

• 分支：将大问题划分为若干子问题，形成解空间树，每个结点代表一个子问题，每条分支表示对子问题的一种约束或决策。
• 限界：对每个子问题，计算一个上下界，即它可能取得的最优解的范围，如果某个子问题的最优解范围不可能优于当前已知的最优解，就剪枝（丢弃该子问题）。

流程：

• 定义问题的解空间
• 从根结点开始分支，产生子问题
• 对每个子问题计算限界
• 子问题放入候选结点表（队列/堆等）
• 从候选结点表中选择结点展开（搜索策略）
• 结点满足约束并且更优就继续分支，不满足就剪枝
• 重复直到候选结点表为空或者找到全局最优

题库：0-1背包问题。

 

双指针

描述：使用两个指针（索引）在数据结构中协同工作，一般分为同向指针或者相向指针。

滑动窗口也是一种双指针，左指针收缩窗口，右指针扩展窗口。

流程：

• 数据结构进行排序
• 边界
• 指针移动条件
• 重复元素处理

题库：LeetCode15，16，75，611， 2348。

 

前缀和

描述：高效处理区间和的技巧。

将区间求和的操作从O(n)优化为O(1)，例如，求sum[l,r]的暴力解法是遍历[l,r]；而预先处理prefix[i]，sum[l,r]即为prefix[r]-prefix[l-1]。

构造时prefix[x]=prefix[x-1]+a[x]。

核心思想：预处理前缀和，换取查询效率；适合于频繁查询但不修改。

题库：LeetCode3147，3346。

差分数组

描述：高效处理区间加法更新的技巧，在区间的边界上做标记，最后通过前缀和恢复原数组。

前缀和的互补技巧。

构造时d[i]=a[i]-a[i-1]，恢复时a[i]=a[i-1]+d[i]。

同理，例如将遍历[l,r]的数组区间，每个加x，转换为d[l]+=x和d[r+1]-=x。

题库：LeetCode3346。

 

 

结构

折半查找树

即二叉搜索树，Binary Search Tree，BST

每个结点最多有两个孩子，对于任一结点node：

左子树上的所有键小于node->key，右子树上的所有键大于node->key。

若树的高度为h，查找/插入/删除复杂度为O(h)，遍历O(n)。

 

二叉树的遍历方式

包括深度优先遍历（DFS）和广度优先遍历（BFS）

1、深度优先遍历

按访问顺序不同，可分为前序遍历，中序遍历，后序遍历。

（1）前序遍历

顺序：根 -> 左子树 -> 右子树

可以用于复制树。

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

（2）中序遍历

顺序：左子树 -> 根 ->右子树

对于二叉搜索树来说，中序遍历的结果就是升序。

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

（3）后序遍历

顺序：左子树 -> 右子树 -> 根

删除树节点或者释放内存。

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

2、广度优先遍历

又叫层序遍历，从根节点开始逐层从左到右访问。

输出层次结构，求出树的高度、最短路径等。

void levelOrder(TreeNode* root) {
    if (!root) return;
    //队列，FIFO
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

 

有向图邻接表

常用的图存储结构，适合存储稀疏图（顶点多，边少）

• 有向图：每条边都有方向，比如u->v表示从顶点u指向顶点v。
• 邻接表：为图中的每个顶点建立一个链表/动态数组，存储从该顶点出发的所有边。

int n = 4; // 顶点个数
vector<vector<int>> adj(n + 1); // 邻接表，1-based

// 加边
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[3].push_back(4);

 

 

STL

ASCII

小写字母的ASCII码=大写字母的ASCII码+32。

 

正整数向上取整

方法：int div=(a+b-1)/b

如果a整除b，那么加上的b+1还不足以跨越到下一个整数；如果a不整除b，那么跨越下一个整数。

 

int最小数和最大数

INT_MIN和INT_MAX，分别为-2³¹和2³¹-1。

 

整数取模的最小非负整数

(x%m+m)%m，x如果为负数，加上m变为正数再取模；x为正数和0无影响。

 

swap()

格式：void swap(T& a,T& b)

时间复杂度和空间复杂度都是O(1)。

 

sort()

格式：void sort (RandomAccessIterator first, RandomAccessIterator last);

额外的：ranges::sort(xx)等价于std::(sort.begin(),sort.end())

注意：

• 迭代器范围：[first, last)是一个左闭右开的区间，例如使用索引和迭代器结合时要用begin()+i和begin()+j+1。
• 性能：时间复杂度为O(nlogn)。

 

min_element()

格式：min_element(begin(),end())

作用：返回[begin,end)范围内最小的迭代器，可以在前面加解引用符号*，即为返回值。

示例：return *min_element(matrix.begin(),matrix.end())

 

lower_bound()

格式：auto it = lower_bound(xx.begin(),xx.end(),x)

作用：找到这个容器下第一个大于等于x的元素，并返回迭代器（要求容器有序）。

平均时间复杂度：O(log n)。

 

clamp()

格式：int x=clamp(value,lo,hi)

作用：返回区间[lo,hi]之间最接近value的值。

即为min(max(value, lo), hi)

 

static

作用于局部变量时：使得变量的生命周期延长至整个程序运行期间，而不是随着函数调用结束而销毁。

作用于成员变量时：所有该类的对象共享同一个静态成员变量。

 

优先队列

特殊的队列，每个元素都有优先级，最先取出优先级最高的元素，在struct{};中提前声明。

核心实现：二叉堆（最大堆priority_queue/最小堆），堆顶是最大/最小元素。

格式：priority_queue<元素类型,底层容器类型,比较函数类型>

# 注：声明忽略后面两个参数时自动按照最大堆排列，即按照从前往后比较的最大元素的排列。

// 初始化，char可以换成自定义的struct
priority_queue<char,vector<char>,CompareASCII>pq;

重载运算符：

# 一般const修饰，重载运算符不必修改对象，引用传递避免不必要的拷贝，提高效率，返回值必须为bool。

// 最小堆，栈顶是优先级最小的，最大堆反之用<。
struct CompareASCII{
    bool operator() (const char& a,const char& b){
        return a>b;
    }
};

插入：push()（只能接受一个参数，必须是已经构造好的元素）或者emplace()

# 不支持随机访问修改

时间复杂度：插入和删除都是O(log n)。

 

Vector

 长度：size()

 在末尾添加一个元素：push_back(数组的一个数据)

 直接在末尾构造对象：emplace_back(构造需要的数据)，和push_back()区别不大，省去一次拷贝。

# 二维数组添加一维数组同理

 释放原有资源并构造新的容器，属性和传进来的容器一致：新的容器=move(数组)

 清空所有元素：clear()

 是否为空矩阵：empty()

 

String

 长度：length()

 获取子字符串：substr(size_t pos,size_t len)

 找到子字符或子字符串：find()，返回起始位置

# pos：子字符串的起始位置，默认0；len：提取的字符数量，默认一直提取到末尾

 将字符串转换为整数：stoi(const string& s,size_t* idx,int base)

# s：需转换的字符串；idx：可选指针；base：可选的转换的进制

 删除最后一个字符：pop_back()

# 字符串不能为空

 

位运算

 计算整数中二进制为1的个数：popcount(T x)

# T：无符号的整数类型，例如unsigned int，unsigned long，uint64_t等；x：整数

 

模板类

<pair>

定义好的迷你结构体，将两个数据打包成一个整体。

struct pair {
    T1 first;   // 第一个元素
    T2 second;  // 第二个元素
};

T1和T2可以为其他不同类型，例如pair<int,string>，经常用于键值对，函数返回值，构造容器等。

 

<tuple>

固定大小，异质（可以是不同类型）的容器

构造：tuple<T1,T2,T3> myTuple(t1,t2,t3)

访问：T1 first=get<0>(myTuple)，也可以修改

支持比较：比较的是字典序

 

无序/有序关联容器

无序：基于哈希表实现

1、哈希集合：unordered_set<key>

• 元素是唯一的，检查一个元素是否存在于集合当中

• 用法：

  • 插入：insert(key)

  • 查找：find(key)，返回的是迭代器，一般配合end()使用进行判断

  • 删除：erase(key)

2、哈希表：unordered_map<key,value>

• key是唯一的

• 用法：

  • 插入：insert({key,value})，或者map[key]=value

  注意，it指向pair<const Key, Value>的对象，不能通过it修改键，但可以修改值，it->first是键，it->second是值。

  • 访问：map[key]

3、性能：

• 平均时间复杂度：插入、删除、查找都是O(1)，但最坏情况可能是O(n)。
• 元素顺序：无序

有序：基于红黑树实现

红黑树是一种自平衡的二叉搜索树，保证了树的高度始终保持在 O(log n)，从而确保了所有主要操作的时间复杂度都是稳定的 O(log n)。

有序集合：set<key>和有序表：map<key,value>

用法同哈希集合和哈希表。

性能：

• 平均时间复杂度：插入、删除、查找都是O(log n)
• 元素顺序：默认按键排列升序

 

List，Set，Map

特性	List	Set	Map
顺序	有序	无序	无序
可重复	可以	不可以	键不重复
访问方式	下标索引	无索引	key查找
用途	保存序列	保存唯一元素	键值对应关系

 

链表

线性数据结构，链表中的元素在内存中不是连续存放的，通过指针将一系列节点连接起来，形成逻辑上的序列。

节点：

• 数据域：用于存储实际的数据（可以是整数、字符串、对象等）。
• 指针域：一个指向下一个节点的指针。

单向链表：

struct ListNode {
    int data;           // 数据域，这里以整数为例
    ListNode* next;     // 指针域，指向下一个节点
    
    // 构造函数，方便创建节点
    ListNode(int val) : data(val), next(nullptr) {}
};

结构：

• 头节点：链表的第一个节点。通过一个指向头节点的指针（head）来访问整个链表。如果链表为空，head 指针为 nullptr。
• 尾节点：链表的最后一个节点。它的 next 指针指向 nullptr。

方法：

• 创建链表：

// 创建几个节点
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);

• 遍历链表：

void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

• 头部插入节点（时间复杂度O(1)）：

ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head; // 新节点的next指向原来的头节点
    return newNode;       // 新节点成为新的头节点
}

• 尾部插入节点（时间复杂度O(n)）：

ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        return newNode; // 如果链表为空，新节点就是头节点
    }
    
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode; // 将尾节点的next指向新节点
    return head;
}

• 删除节点（时间复杂度O(n)，已知位置就是O(1)）：

ListNode* deleteNode(ListNode* head, int val) {
    if (head == nullptr) return nullptr;
    
    // 如果要删除的是头节点
    if (head->data == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    
    // 查找要删除节点的前一个节点
    ListNode* current = head;
    while (current->next != nullptr && current->next->data != val) {
        current = current->next;
    }
    
    // 找到了要删除的节点
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
    return head;
}

注意：

• 内存管理：在 C++ 中使用 new 创建的节点，必须使用 delete 手动释放，否则会导致内存泄漏。
• 指针安全：操作指针时要格外小心，避免访问 nullptr 或已删除的内存（野指针）。
• 边界条件：处理空链表、单节点链表等情况时要特别注意。

 

inline

内联函数，编译器会尝试用函数内的代码替换掉函数调用语句

传统函数调用过程：

• 执行到函数调用语句
• 将返回地址，参数等压入栈
• 跳转到函数体的内存地址开始执行
• 函数执行完毕，将返回值存入指定位置
• 跳转回之前保存的地址，继续执行调用处的下一条指令

这个过程对于功能简单，调用频繁的小函数，这种开销可能比函数本身执行的时间还长。

inline return_type function_name(parameters) {
    // function body
}

优点：

• 减少调用开销
• 避免宏定义的缺点

 

Lambda表达式

   // lambda 递归函数例子1
   auto dfs = [&](this auto&& dfs, int i, int j) -> int {
       if (i + 1 == j) {
           return 0; // 只有两个点，无法组成三角形
       }
       int& res = memo[i][j]; // 注意这里是引用，修改 res 相当于修改 memo[i][j]
       if (res != -1) { // 之前计算过
           return res;
       }
       res = INT_MAX;
       for (int k = i + 1; k < j; k++) { // 枚举顶点 k
           res = min(res, dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]);
       }
       return res;
   };
// lambda 递归函数例子2
   auto dfs=[&](this auto&& dfs,int i)->long long{
       if(i<0){
           return 0;
       }
       long long& res=memo[i];
       if(res!=-1){
           return res;
       }
       auto& [d,count]=damage[i]; //单纯读取，此处不使用引用也可以
       int j=i;
       while(j>0&&damage[j-1].first>=d-2){
           j--;
       }
       res=max(dfs(i-1),dfs(j-1)+(long long)d*count);
       return res;
   };

# [&]表示能够访问外部作用域所有变量，this auto&&允许Lambda实现自递归，->int表示返回类型为整数，int & res表示修改这个值同时会修改对应的的memo的值，实现记忆化。