WPIRONMAN

基础知识--图论

代码随想录--回溯算法

回溯算法 ​ 回溯算法 是一种通过试错的方式寻找问题解的算法。它尝试逐步构建解决方案，如果在构建过程中的某一步发现当前的构建方案不可行，它会回溯（即取消最近一步的选择），然后尝试其他的可能性。这个过程就像是在迷宫中探索路径，当遇到死路时就退回上一个岔路口，选择另一条路继续前进。 核心思想 试探性选择: 在每一步，都面临多个选择，回溯算法会先选择其中一个进行尝试。 逐步构建: 它一步一步地构建可能的解。 可行性判断 (约束条件): 在每一步构建后，都会检查当前的部分解是否满足问题的约束条件。 回溯 (撤销选择): 如果发现当前部分解不可行，则撤销上一步的选择，回到之前的状态，并尝试其他的选择。 终止条件: 当找到一个完整的可行解，或者当所有可能的选择都尝试完毕且没有找到解时，算法终止。 基本步骤 定义问题的解空间： 确定问题的解可能存在的所有可能组合。例如，对于一个排列问题，解空间就是所有可能的排列。 确定约束条件： 定义问题解必须满足的条件。这些条件用于判断当前构建的部分解是否有效。 选择搜索策略 (通常是深度优先搜索 DFS)： ...

线性表 线性表是⼀对⼀的逻辑结构，线性表中除了表头元素每个元素有且仅有唯⼀⼀个前驱元素，除了表尾元素，每个结点都有唯⼀⼀个后继节点。 顺序存储（顺序表） 存取 顺序表随机存取，存取某个元素的时间复杂度为O(1)。 查找 平均时间复杂度O(n) 插入删除 平均时间复杂度O(n)，删除插⼊元素需要移动⼤量元素。（如果是删除最后⼀个元素或者在最后⼀个节点后⾯插⼊⼀个新的节点，则复杂度为O(1)，因为不需要移动元素） 链式存储（链表） 链表因其链状的结构，能方便地删除、插入数据，操作次数是 O(1)。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 O(n)。 单链表 单链表的基本组成单元是节点 (Node)。 每个节点通常包含两个主要部分： 数据域 (Data): 用于存储实际的数据元素。 数据域可以是任何数据类型，例如整数、浮点数、字符、字符串，甚至更复杂的数据结构。 指针域 (Pointer) 或 下一个节点指针 (Next Pointer): 用于存储指向链表中下一个节点的地址（或引用）。 对于单链表，每个节点只有一个指针，指向它后面的节点。 ...

绪论 数据结构 数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 逻辑结构 线性结构 一般线性表：线性表 特殊线性表：栈、队列、字符串 线性表的推广：数组、广义表 非线性结构 树结构：树、二叉树 图结构：有向图、无向图 集合结构 存储结构 顺序存储 逻辑上连续，物理上连续 优点： 随机访问高效：通过下标可直接访问元素，时间复杂度为 O(1)。 内存连续，缓存友好：数据连续存放，充分利用 CPU 缓存机制，访问效率高。 空间开销小：仅需存储数据，无需额外指针字段，内存利用率高。 缺点： 插入/删除效率低：在中间或头部操作时，需移动大量元素，时间复杂度为 O(n)。 固定容量：需预先分配连续内存空间，扩容需复制全部数据，动态扩展成本高。 内存浪费：若预分配空间过大，可能造成内存冗余。 链式存储 逻辑上不要求连续，物理上⼀定连续 优点： 动态内存分配：无需预先分配固定空间，按需动态扩展，内存利用率高。 插入/删除高效：仅需修改指针指向，时间复杂度为...

代码随想录--二叉树（3）

代码随想录--二叉树（2）层序遍历

代码随想录--二叉树（1）前中后序遍历

标准模板库（STL） STL 即标准模板库（Standard Template Library），是 C++ 标准库的一部分，里面包含了一些模板化的通用的数据结构和算法。由于其模板化的特点，它能够兼容自定义的数据类型，避免大量的造轮子工作。NOI 和 ICPC 赛事都支持 STL 库的使用，因此合理利用 STL 可以避免编写无用算法，并且充分利用编译器对模板库优化提高效率。 STL容器 迭代器 ​ 在 STL 中，迭代器（Iterator）用来访问和检查 STL 容器中元素的对象，它的行为模式和指针类似，但是它封装了一些有效性检查，并且提供了统一的访问格式。 ​ 迭代器听起来比较晦涩，其实迭代器本身可以看作一个数据指针。迭代器主要支持两个运算符：自增 (++) 和解引用（单目 * 运算符），其中自增用来移动迭代器，解引用可以获取或修改它指向的元素。 12345678vector<int> data(10);//下面两个 for 循环的效果是一样的for (int i = 0; i < data.size(); i++) cout <<...

代码随想录--栈·队列