解题思路 1. 基本原理  后序遍历：左子树 -> 右子树 -> 根节点 中序遍历：左子树 -> 根节点 -> 右子树 关键点：后序遍历的最后一个元素一定是根节点  2. 解题步骤 以输入 [2,1,4,3,5]（中序）和 [2,4,5,3,1]（后序）为例：   找到根节点：  后序遍历的最后一个元素1是根节点    在中序遍历中定位根节点：  中序：[2, (1), 4,3,5] 1的位置将中序序列分成左右子树    划分子树：  左子树：中序 [2]，后序 [2] 右子树：中序 [4,3,5]，后序 [4,5,3]    递归构建：  对左右子树重复上述过程 左子...

解题思路 1. 基本概念 二叉树的三种遍历方式是按照访问根节点的顺序来定义的：  前序遍历：根节点 -> 左子树 -> 右子树 中序遍历：左子树 -> 根节点 -> 右子树 后序遍历：左子树 -> 右子树 -> 根节点  2. 图解示例  1 / \ 2 3 / \ / \ 4 5 6 7  前序遍历过程：  先访问根节点 1 然后访问左子树 (2,4,5) 最后访问右子树 (3,6,7) 结果：1,2,4,5,3,6,7  中序遍历过程：  先访问左子树 (4,2,5) 然后访问根节点 1 最后访问右子树 (6,3,7) 结果：4,2,5,1,6,3,7 ...

解题思路    使用邻接表存储图     使用 (可见文末) 算法求解从 号点到其他所有点的最短距离。     检查是否能到达 号点，如果不能到达则输出 。    代码    cpp   java   python   #include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; struct Edge { int v, w; Edge(int _v, int _w) : v(_v), w(_w) {} }; vector<vector<Edge>> g; // 邻接表 v...

解题思路：   使用  算法求最小生成树：  将所有边按权重排序 使用并查集维护节点的连通性 依次选择权重最小的边，如果不会形成环就加入最小生成树    并查集优化：  使用路径压缩优化 find 操作 使用按秩合并优化 union 操作    算法步骤：  初始化并查集 对边按权重排序 遍历边，使用并查集判断是否形成环 统计总成本和使用的边数 检查图的连通性    代码   c++   java   python   class Solution { public: // 并查集数据结构 class UnionFind { private: vector<int> parent;...

解题思路   构建图：  使用邻接表存储图 记录每个节点的入度    Kahn算法：  将所有入度为  的节点加入队列 每次从队列取出一个节点，将其加入结果 减少其所有邻接节点的入度 如果邻接节点入度变为 ，则加入队列    检查有效性：  如果最终结果数组长度不等于 ，说明图中有环 否则得到的就是一个有效的拓扑序     代码   cpp   java   python   #include <iostream> #include <vector> #include <queue> using namespace std; class Solution {...

解题思路   使用三个指针：  prev：指向前一个节点 curr：指向当前节点 next：指向下一个节点    反转步骤：  保存当前节点的下一个节点(next = curr.next) 反转当前节点的指针(curr.next = prev) 移动prev和curr指针  prev = curr curr = next      特殊情况处理：  空链表：直接返回null 单节点链表：直接返回该节点    代码   cpp   java   python   class Solution { public: ListNode* ReverseList(ListNode* pHead) { /...

解题思路   插入操作：  创建一个新节点。 如果链表为空，直接将新节点作为头节点。 遍历链表，找到第一个值为 x 的节点，在其前插入新节点。 如果没有找到 x，将新节点插入到链表末尾。    删除操作：  如果链表为空，直接返回。 如果头节点的值为 x，直接删除头节点。 遍历链表，找到第一个值为 x 的节点，删除该节点。    输出链表：  遍历链表输出每个节点的值。 如果链表为空，输出 "NULL"。    代码   cpp   java   python   #include <iostream> #include <string> using...

解题思路  使用一个固定大小的数组来存储队列元素。 维护两个指针 head 和 tail，分别指向队首和队尾。 push 操作：将元素加入队尾，更新 tail 指针。 pop 操作：输出并移除队首元素，更新 head 指针。 front 操作：输出队首元素。 检查队列是否满或空，以决定是否输出 "full" 或 "empty"。  代码   cpp   java   python   #include <iostream> #include <vector> #include <string> using namesp...

解题思路  使用队列来存储数据。 对于 push 操作，将元素加入队尾。 对于 pop 操作，检查队列是否为空：  如果为空，输出 "error"。 否则，输出队首元素并将其出队。   对于 front 操作，检查队列是否为空：  如果为空，输出 "error"。 否则，输出队首元素。    代码   cpp   java   python   #include <iostream> #include <queue> #include <string> using namespace std; int main() {...

解题思路  使用栈来模拟消除过程：  遍历字符串中的每个字符 如果栈不为空且当前字符与栈顶字符相同，则消除（弹出栈顶） 否则将当前字符入栈   最后栈中剩余的字符就是最终结果：  如果栈为空，输出"0" 否则将栈中字符拼接成字符串输出    代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; string solve(string s) { stack<char> st; for(char c : s) { if(!st.empty() &&...

解题思路  使用栈来存储数字 遍历表达式：  如果是数字，直接入栈 如果是运算符：  弹出栈顶的两个数字（注意顺序） 进行相应的运算 将结果压入栈中     最后栈顶的数字就是表达式的值  代码   cpp   java   python   class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(string& s : tokens) { if(s == "+" || s == "-" || s == &q...

解题思路 这道题目主要考察栈的基本操作：入栈(push)、出栈(pop)和查看栈顶(top)。需要注意的是空栈的处理。 主要实现要点：  使用栈数据结构存储数据 对于  操作，直接将数字压入栈中 对于  和  操作，需要先判断栈是否为空  如果栈为空，输出"error" 如果栈不为空，执行相应操作    代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int ...

A.构造 A+B 可以发现  都可以找到一个正整数配对，所以当  时，则有解，否则无解。 void solve(){ int n,k; cin>>n>>k; if(n-1>=k){ cout<<"YES"; }else{ cout<<"NO"; } }  B.宝石手串 可以把每个字符放进对应的容器，然后比较同一类字母中，相邻两个字母的距离，由于是环，所以需要比较两边的距离，然后取最小值即可。 void solve(){ int n; cin>>n; string s; cin>&gt...

牛客周赛70题解 本篇题解由 Null_Resot 提供。 观前阅读 以下是本文中用到的一些符号或表示 数组在区间中的最大值 的表示： 异或 符号： 数组在区间的异或和 的表示 ： 数组在区间的区间和 的表示  属于 符号: 非负整数 符号: 艾佛森括号：，如果表达式的结果为，那么，否则 A 小苯晨跑 题意  小苯生活在计算机网络世界中，网络空间中到处都是数据，小苯每次晨跑，风都会带着这些数据乱飞。  现在正在晨跑的小苯面前有四个数据，他想知道这些数据是否乱飞了，请你帮他确定吧。 （如果所有数据都相等，则认为数据没有乱飞，反之则乱飞了。） 思路 我们可以用四个元素两两之间相互判断是否相同，也可...