链表
无标记查找链表循环点
双指针变步长循环遍历：
// 抓兔子
rabi=H.head;
turtle=H.head;
while(rabi!=turtle){
rabi=rabi.next.next;
turtle=turtle.next;
}
// 测算周长
int R=0;
while(rabi!=turtle){
turtle=turtle.next;
R++;
}
// 查找相交结点
rabi=H.head;
turtle=H.end;
for(int i==0;i<R;i++){
rabi=rabi.next; //兔子先走R步
}
while(rabi!=turtle){
rabi=rabi.next;
turtle=turtle.next;
}
return turtle;栈
数制转换
类似于十进制“除 10 模 10”的操作
// 十进制转B进制
int target;int B;
stack<int> stack;
while(target!=0){
stack.push(target%B);
target=target/B;
}
// 顺序弹出即可
vector<int> ans;
while(!stack.empty()){
ans.push_back(stack.top());
stack.pop();
}
return ans;输出序列合法性判定
核心：原序列所有字符都要入栈一次，出栈一次；
string processStack(const string &pushSeq, const string &popSeq){
stack<char> s;
string operations;
int popIndex = 0; // 用于跟踪 popSeq 的索引
//pushSeq中所有字符都要入栈
for (char pushChar : pushSeq){
s.push(pushChar);
operations += 'P'; // 记录入栈操作
//检测是否可以弹出
while (!s.empty() && s.top() == popSeq[popIndex]){
s.pop();
operations += 'O'; // 记录出栈操作
popIndex++;
}
}
// 检查是否所有 pop 操作都成功
if (popIndex == popSeq.size()){
return "right\n" + operations;
}
else{
// 无法匹配，返回剩余栈元素
string remaining;
while (!s.empty()){
remaining = s.top() + remaining;
s.pop();
}
return "wrong\n" + remaining;
}
}
int main(){
string pushSeq, popSeq;
cin >> pushSeq >> popSeq;
cout << processStack(pushSeq, popSeq) << endl;
return 0;
}括号语句判定
无优先级
左括号入栈，右括号弹出；
stack<char> stack;
string target; //目标字符串
int k=0; //字符串上的指针
bool valid=true; //答案初始化
while(valid && k<target.size()){
if(target[k]=='(' || target[k]=='[' || target[k]=='{'){
stack.push(target[k]);
}else{
if(!stack.empty() && isMatch(stack.top(), target[k])){
stack.pop();
}else{
valid=false;
}
}
k++;
}
// 上面的循环有两个跳出条件，需要进一步检测
if(valid && !stack.empty()){
valid=false;
}
return valid;带优先级
在不含优先级的判定过程中，对于左括号全部都入栈；有优先级的情况下，只需要判定栈顶和准备入栈的左括号是否满足优先关系即可。
//判定匹配
bool isMatch(char top, char other){
if(top=='<' && other=='>')
return true;
if(top=='(' && other==')')
return true;
if(top=='[' && other==']')
return true;
if(top=='{' && other=='}')
return true;
return false;
}
//判定入栈的优先级
bool isPriority(char top, char other){
if(top=='<' && other!='<')
return false;
if(top=='(' && other!='<' && other!='(')
return false;
if(top=='[' && other=='{')
return false;
return true;
}
string isValid(string& target){
stack<char> stack;
bool valid=true;
int k=0;
while(valid && k<target.size()){
//左括号判定优先级并入栈
if(target[k]=='<' || target[k]=='(' || target[k]=='[' || target[k]=='{'){
if(stack.empty() || isPriority(stack.top(),target[k])){
stack.push(target[k]);
}else{
valid=false;
}
}else{//右括号判定匹配
if(!stack.empty() && isMatch(stack.top(),target[k])){
stack.pop();
}else{
valid=false;
}
}
k++;
}
if(valid && !stack.empty())
valid=false;
return valid;
}生成所有合法出栈序列
核心：遍历每一个元素作为出栈的最后一个元素，然后进行分治递归；
//生成从left到right之间整数的所有合法出栈序列
vector<vector<int>> validSq(int left, int right){
vector<vector<int>> sq;
if(left>right){
sq.push_back({}); //必须加一个空的vector，不能直接返回！
return sq;
}
for(int last=left;last<=right;last++){
vector<vector<int>> leftSq=validSq(left,last-1);
vector<vector<int>> rightSq=validSq(last+1,right);
for(int l=0;l<leftSq.size();l++){
for(int r=0;r<rightSq.size();r++){
sq.push_back(leftSq[l]);
sq.back().insert(sq.back().end(),rightSq[r].begin(),rightSq[r].end());
sq.back().push_back(last);
}
}
}
return sq;
}
//用于排序，可以生成字典序
bool cmp(const vector<int>& a, const vector<int>& b) {
return a < b;
}后缀表达式计算
思路：遇见数值输入则入栈，遇见字符输入则弹出两个数值进行操作，然后再入栈；异常处理先处理 # 再处理其他操作符。
//输入样例：5 -2 + 3 * #
//输出样例：9
string temp=""; //临时存放输入变量
stack<int> stack; //整数操作栈
while(cin>>temp){
try{
int num=stoi(temp);
stack.push(num);
}catch(const invalid_argument& e){
if(temp=="#"){
cout<< ((stack.size()==1)? "":"Expression Error: ")<<stack.top();
return 0;
}
if(stack.size()<2){
cout<<"Expression Error: "<<stack.top();
return 0;
}
if(temp=="+"){
int num2=stack.top();stack.pop();
int num1=stack.top();stack.pop();
stack.push(num1+num2);
}
if(temp=="-"){
int num2=stack.top();stack.pop();
int num1=stack.top();stack.pop();
stack.push(num1-num2);
}
if(temp=="*"){
int num2=stack.top();stack.pop();
int num1=stack.top();stack.pop();
stack.push(num1*num2);
}
if(temp=="/"){
int num2=stack.top();stack.pop();
int num1=stack.top();stack.pop();
if(num2==0){
cout<<"Error: "<<num1<<"/"<<num2;
return 0;
}
stack.push(num1/num2);
}
}
}中缀转后缀
// 运算符优先级
unordered_map<char, int> precedence = {
{'+', 1},
{'-', 1},
{'*', 2},
{'/', 2},
{'^', 3}
};
// 判断字符是否是操作符
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
// 判断字符是否是数字或字母（操作数）
bool isOperand(char c) {
return isalnum(c);
}
// 进行中缀到后缀的转换
string infixToPostfix(const string& infix) {
stack<char> ops; // 存储运算符
string postfix; // 存储后缀表达式
for (char c : infix) {
// 如果是操作数，直接加入后缀表达式
if (isOperand(c)) {
postfix += c;
}
// 如果是左括号，压栈
else if (c == '(') {
ops.push(c);
}
// 如果是右括号，弹出栈中的运算符直到遇到左括号
else if (c == ')') {
while (!ops.empty() && ops.top() != '(') {
postfix += ops.top();
ops.pop();
}
ops.pop(); // 弹出左括号
}
// 如果是运算符，优先级高的会沉底，将其他符号强制弹出
else if (isOperator(c)) {
while (!ops.empty() && precedence[ops.top()] >= precedence[c]) {
postfix += ops.top();
ops.pop();
}
ops.push(c);
}
}
// 弹出栈中剩余的所有运算符
while (!ops.empty()) {
postfix += ops.top();
ops.pop();
}
return postfix;
}
int main() {
string infix;
cout << "请输入中缀表达式：";
getline(cin, infix);
string postfix = infixToPostfix(infix);
cout << "对应的后缀表达式是：" << postfix << endl;
return 0;
}
排序
求逆序对数量
将整个数组分成两块，整个逆序数分成：左边子数组的逆序数、右边子数组的逆序数、再是左右子数组之间的逆序数；逆序对的数量可能很多，要用 long 来存储；
//先默写归并排序的代码，然后再进一步修改
long merge(vector &nums, int left, int mid, int right){
long ans=0;
int i=left, j=mid+1, k=0;
vector<int> temp;
while(i<=mid && j<=right){
if(nums[i]<=nums[j])
temp[k++]=nums[i++];
else{
temp[k++]=nums[j++];
ans+=(mid-i+1);
}
}
while(i<=mid){
temp[k++]=nums[i++];
}
while(j<=right){
temp[k++]=nums[++];
}
for(k=0;k<temp.size();k++){
nums[left+k]=temp[k];
}
return ans;
}
long mergSort(vector &nums, int left, int right){
// 终止条件
if(left>=right)
return 0;
int mid = left + (right-left)/2;
long left_num = mergSort(nums, left, mid);
long right_num = mergSort(nums, mid+1, right);
long between_num = merg(nums, left, mid, right);
return (left_num + right_num + between_num);
}树
前中序列建树
string preorder, inorder;
void buildPostorder(int preStart, int preEnd, int inStart, int inEnd, string& postorder) {
if (preStart > preEnd || inStart > inEnd) return;
// 当前子树的根节点
char root = preorder[preStart];
// 在中序遍历中找到根节点的位置
int rootIndex = inorder.find(root);
// 递归地构建左子树和右子树，并按照“左-右-根”的顺序形成后序遍历序列
buildPostorder( preStart + 1, preStart + rootIndex - inStart, inStart, rootIndex - 1, postorder);
buildPostorder( preStart + rootIndex - inStart + 1, preEnd, rootIndex + 1, inEnd, postorder);
postorder += root;
}
string findPostorder() {
string postorder;
buildPostorder( 0, preorder.size() - 1, 0, inorder.size() - 1, postorder);
return postorder;
}
int main() {
cin >> preorder >> inorder;
cout << findPostorder() << endl;
return 0;
}二叉树的反序列化
核心：用 index 标记构建到哪里了，然后递归构建“根-左-右”，当 index 超限或者遇到空字符 # 就跳过并返回空指针；
// 通过一个前序遍历字符串来重建二叉树结构
// 测试输入：FCA##DB###EHM###G##，“#”代表空结点
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* construct(string& data, int& index) {
if (index >= data.length() || data[index] == '#') {
index++; // 跳过空节点
return nullptr;
}
// 创建当前节点
TreeNode* node = new TreeNode(data[index++]);
// 递归创建左子树
node->left = construct(data, index);
// 递归创建右子树
node->right = construct(data, index); //index看似一样实则不同！
return node;
}
// 两个同名函数构成重载
TreeNode* construct(string data) {
int index = 0;
return construct(data, index);
}
二叉搜索树判定
// 输入一个序列化字符串，判定是否为合法二叉搜索树
// 输入样例：56**87***
// 输出样例：NO
// 假定已经完成反序列化
bool isValidBFT(TreeNode* root, int leftbound, int rightbound){
if(!root)
return true; //空树是二叉搜索树
// 判断条件中的等于号可选，控制区间开闭
if(root->val<leftbound || root->val>rightbound){
return false;
}
// 递归检查左子树和右子树
return isValidBFT(root,leftbound,root->val) && isValidBFT(root,root->val,rightbound)
}生成所有二叉树
思路：枚举根节点，分别生成左右子树，再进行拼接
//给定一个数n，要求生成所有从由1~n构成的二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int left, int right) {
//递归终止条件
if(left>right){
return {nullptr};
}
vector<TreeNode*> all_trees;
//枚举根节点
for (int root_val = left; root_val <= right; root_val++) {
vector<TreeNode*> left_tree = generateTrees(left, root_val - 1);
vector<TreeNode*> right_tree = generateTrees(root_val + 1, right);
//由于生成的是左右子树的总集合，所以还要再进行全排列
for(auto left:left_tree){
for(auto right:right_tree){
TreeNode* curr=new TreeNode(root_val);
curr->left=left;
curr->right=right;
all_trees.push_back(curr);
}
}
}
return all_trees;
}
vector<TreeNode*> generateTrees(int n) {
if(n==0){
return {};
}
return generateTrees(1,n);
}
};图
图的连通度计算
核心：保存 visited 数组，然后让所有的结点都当一次源点，如果有没访问过的结点则连通度增加；
// 先默写BFS/DFS遍历算法，然后再进一步修改
欧拉回路求解
核心：先判断存不存在欧拉回路；如果存在，则进行魔改版深度优先遍历，从起点开始找下一个结点，然后抹除关联，入栈然后继续找下一个；直到某个结点没有未访问的邻接节点，那么就返回
int v_num; // 结点数目
unordered_map<int, vector<int>> adjList; // 图的邻接表
// 判断图的每个顶点的度是否为偶数
bool hasEulerianCircuit(int n){
for (int i = 0; i < n; ++i){
if (adjList[i].size() % 2 != 0)
return false;
}
return true;
}
// 寻找欧拉回路
vector<int> findEulerianCircuit(int start){
vector<int> circuit; // 答案数组
stack<int> currentPath;
currentPath.push(start);
unordered_map<int, vector<int>> copy = adjList; // 图的副本
while (!currentPath.empty()){
int v = currentPath.top();
if (!copy[v].empty()){
int next = copy[v].back(); //取出结点
//删除相互关联，避免重复访问
copy[v].pop_back();
copy[next].erase(find(copy[next].begin(), copy[next].end(), v)); // 将上一个节点直接删除，避免使用visited数组
//入栈
currentPath.push(next);
}
else{
circuit.push_back(v); // 当结点v没有未访问的邻接结点，加入答案
currentPath.pop();
}
}
return circuit;
}拓扑排序
BFS 实现
核心：将入度为零的点入队，然后再从队首取出一个，遍历其邻接节点，扣除他们的入度，创造新的入度为零的结点然后入队；
int v_num, e_num;
vector<vector<int>> graph(v_num + 1); //邻接表
vector<int> inEdgeNum(v_num + 1, 0); //入度表
queue<int> q;
vector<int> ans; // 存放拓扑序列
bool bfs_topsort(){
for (int i = 1; i <= v_num; i++)
if (inEdgeNum[i] == 0)
q.push(i); // 将入度为0的点入队列
while (!q.empty()){
int u = q.front();
q.pop(); // 选一个入度为 0 的点，出队
ans.push_back(u);
for (int i = 0; i < graph[u].size(); i++){
int v = graph[u][i];
inEdgeNum[v]--;
if (inEdgeNum[v] == 0)
q.push(v); // 当某一条边的入度为0，入队
}
}
if (ans.size() == v_num){ //所有节点都已经排序完成
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << (i == ans.size() - 1) ? "\n" : " ";
return true;
}
return false; //还有结点没排序，说明图中有环
}最小生成树
Kruskal 算法
核心：就是从小到大依次选边；但是有些边不能选，因为选了就会产生回路，可以使用并查集来判断是否会产生回路
int v_num, e_num;
// 初始化并查集
vector<int> DJSet(v_num + 1);
void initSet(){
for (int i = 1; i <= v_num; i++){
DJSet[i] = i;
}
}
//定义查询
int findRoot(int x){
return DJSet[x] == x ? x : DJSet[x] = findRoot(DJSet[x]);
}
//定义合并
void Merge(int x, int y){
int x_root = findRoot(x);
int y_root = findRoot(y);
//根结点相互连接
if(x_root<y_root){
DJSet[y_root] = x_root;
}else{
DJSet[x_root] = y_root;
}
}
bool cmp(array<int, 3> a, array<int, 3> b){
return a[0] < b[0];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> v_num >> e_num;
//初始化并查集
initSet();
vector<array<int, 3>> edges;
edges.reserve(e_num); //分配内存
for (int i = 0; i < e_num; i++){
int u, v, w;
cin >> u >> v >> w;
edges.push_back({w, u, v}); //内存分配后可以这样操作
}
sort(edges.begin(), edges.end(), cmp);
for (auto &[w, u, v] : edges){
int root_u = findRoot(u);
int root_v = findRoot(v);
if (root_u != root_v){
Merge(u, v);
cout << min(u, v) << "," << max(u, v) << "," << w << endl;
}
}
}Prim 算法
每次加入距离最小的点，用堆来维护
//某个结点的邻接结点结构体
struct adjNode{
int index; // 连接的顶点
int cost; // 边的权值
};
int v_num, e_num, src;//全局变量
void Prim(vector<vector<adjNode>> adj){
//初始化关键数据结构
vector<bool> visited(v_num);
//将将结点和边一起存储，顺序为cost,u,v
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
//初始化源点
visited[src]=true;
for(auto &adj_node:adj[src]){
pq.push({adj_node.cost, src, adj_node.index});
}
int edgeChosen=0; //已经选中的边,最多v_num-1条
while(edgeChose<v_num-1 && !pq.empty()){
auto [cost, u, v]=pq.top();
pq.pop();
if(visited[v])
continue;
//选中这条边
visited[v]=true;
edgeChosen++;
//输出结果
cout<<u<<" "<<v<<" "<<cost<<endl;
//刷新邻接结点
for(auto &adj_node:adj[v]){
if(!visited[adj_node.index]){
pq.push({adj_node.cost, v, adj_node.index});
}
}
}
}
int main(){
cin >> v_num >> e_num >> src;
vector<vector<adjNode>> adj(v_num + 1); //邻接结点矩阵
for (int i = 0; i < e_num;i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
Prim(adj);
}