数据结构和算法

算法

枚举算法

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

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

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

流程：

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

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

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

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

 

贪心算法

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

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

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

优点：高效，简单直观。

流程：

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

题库：LeetCode45，134，1578，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{};

auto dfs=[&](this auto&& dfs,int i,int t)->void{
    if(t==0){
        res.push_back(path);
        return;
    }
    if(i>=n||t<0) return;
    if(candidates[i]>t) return;
    // 不选i+1
    int k=i;
    while(k<n-1&&candidates[k+1]==candidates[k]){
        k++;
    }
    dfs(k+1,t);
    // 选i+1
    path.push_back(candidates[i]);
    dfs(i+1,t-candidates[i]);
    path.pop_back();
    return;
};

题库：LeetCode 22，39，40，77，79，131。

 

动态规划

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

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

思路：

• 找出规律，找到子问题（最优子结构）。

动态规划问题即是递推问题，当前的决策结果是f(n)，最优子结构就是要让f(n-k)最优。

• 状态定义，写出状态转移方程。

注意递归边界和递归入口。

可以运用auto dfs和memo记忆化递归，此时如果入口从n开始要注意区间，最好左闭右开。

题库：0-1背包问题，LeetCode62，97，120，139，474，1262，1277，1504，2327，3186，3494。

 

位运算算法

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

题库：LeetCode50，78，2749。

 

模拟

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

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

流程：

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

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

题库：LeetCode6，54，3446。

 

堆算法

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

堆的更新和维护：

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

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

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

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

即堆中插入n个元素

应用：优先队列。

题库：LeetCode 1792。

 

分支限界法

描述：

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

流程：

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

题库：0-1背包问题。

 

双指针

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

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

在窗口的贡献可以被增量维护的时候，可以使用滑动窗口。

思路：

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

题库：LeetCode11，15，16，75，611， 2348。

 

前缀和

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

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

如果存在贪心/动态规划，可以只用prefix不用数组。

如果和模结合，可以变成取模后的前缀和数组，寻找模的数学公式。

如果和哈希表结合，可以一次遍历就处理枚举前后的两个前缀哈希表。

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

题库：LeetCode53，1590，3147，3346，3583。

差分数组

描述：在区间的边界上做标记，最后通过前缀和恢复原数组。

前缀和的互补技巧。

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

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

二维的时候，mat[i][j]=diff[i][j]+mat[i−1][j]+mat[i][j−1]−mat[i−1][j−1]，如果要将区间row1,row2,col1,col2内的矩形元素全部+x，则为

diff[row1][col1]+=x;
diff[row2+1][col1]-=x;
diff[row1][col2+1]-=x;
diff[row2+1][col2+1]+=x;

注意边界。

题库：LeetCode2536，3346。

 

 

结构

折半查找树

即二叉搜索树，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，那么跨越下一个整数。

快速幂算法

double ans = 1;
while (N > 0) {
    if (N % 2 == 1) ans *= x;
    x *= x;
    N /= 2;
}

原理：将指数作为二进制，每次向右移动一位，将x翻倍，最低位为1的就累乘到ans中，将时间复杂度从O(n)变成O(logn)。

正常幂可以用pow(base, exponent)，返回double。

鸽巢原理

在repunit的问题中出现，在取模的时候余数个数（鸽子数）如果大于模（容器数），那么至少有一个余数出现两次，即必定循环，所以就没有结果。

涉及到取模的时候，通常运用(a+b)mod m=((a mod m)+(b mod m))mod m和(a⋅b)mod m=((a mod m)⋅(b mod m))mod m。

sort()

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

变形：ranges::sort(xx)等价于std::(sort.begin(),sort.end())

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

性能：时间复杂度为O(nlogn)。

结合Lambda表达式，第三个参数可以为匿名的函数对象。[](const vector<int>& x, const vector<int>& y)->bool{return x[1]<y[1]}，即为按照第二列升序排序。

 

短路求值

C++逻辑中的||是短路机制，只要前者条件满足就不会计算后者，因此在遍历容器时如果遇到i+1这种可以if(i==length-1||colors[i]!=colors[i+1])，只要没到最后一个元素就不会越界访问。

 

最小公约数/最大公倍数

格式：gcd()和lcm()

C++中自带，0和其他数的gcd()是其他数，区间求gcd()可以用枚举更新。

 

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)

 

getline()

格式：istream& getline(istream& is, string& str, char delim);

is是输入流对象，可以是cin或者stringstream，str是用来存储的字符串变量，delim是可选的分隔符。

作用：默认从当前位置读到换行符\n为止，例如getline(cin, str, ',')可以读取输入流直到,为止。

和cin>>混用时注意要清空缓冲区cin.ignore()。

 

move()

作用：避免深拷贝操作，将容器的内容全部转移，转移后的容器会变为空。

可以和emplace_back配合xxx.emplace_back(move(xx))

 

static

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

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

 

优先队列

特殊的队列，每个元素都有优先级，最先取出优先级最高的元素，堆顶是最大/最小元素，可以在struct{};中提前声明，

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

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

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

默认最小堆/最大堆

// 最小优先
priority_queue<int, vector<int>, greater<>> pq;
// 最大优先
priority_queue<int, vector<int>, less<int>> pq;

重载运算符：

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

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

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

# 不支持随机访问修改

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

 

容器

Vector

构造：vector(size_type n, const T& val)

直接在末尾构造对象：emplace_back(构造需要的数据)

省去一次拷贝。

清空所有元素：clear()

清空可以用empty()判断

是否为空矩阵：empty()

0不能用此判断

 

String

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

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

找到子字符或子字符串：find()

返回起始位置

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

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

在遇到边界的时候考虑手写转换

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

字符串不能为空

字符构建字符串：push_back()或者str+=c

遇到字母的string，解题时可以考虑枚举26个英文字母。

 

无序/有序关联容器

无序

基于哈希表实现

1、哈希集合：unordered_set<key>

• 构造：unordered_set<key> st(nums.begin(),nums.end())

• 插入：insert(key)

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

  count(num)，返回的是0/1，表示集合中是否存在num。

• 删除：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)
• 元素顺序：默认按键排列升序

 

输入流

>>

stringstream ss(s);
string token;
while(ss>>token){}

跳过了各种空白符的token，可以用来分割字符串。

 

Stack

初始化：stack<T> s

栈的元素个数：size()

自底向上拼接栈中元素(string)：

string res;
vector<string> parts;
while (!s.empty()) {
    parts.push_back(s.top());
    s.pop();
}
for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
    res += *it;
}

使用了vector的反向迭代器从后向前。

 

位运算

 计算整数中二进制为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)，也可以修改

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

 

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 递归函数例子
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;
};

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

由捕获列表，参数列表，返回类型和函数体构成。