方法1：暴力我们使用一个vector来存数组并且对于每次中位数的计算，我们直接排序一遍，然后寻找中位数即可时间复杂度：插入数字O(1)，查找中位数O(nlogn)空间复杂度：O(n) class Solution { public: vector<int> v;//用于存数组 void Insert(int num) { v.push_back(num); } double GetMedian() { sort(v.begin(), v.end()); int sz = v.size(); if (sz & 1) return v[sz / 2];//如果是奇数个，则是中间...

方法1：递归我们要知道二叉搜索树的性质，对于每个节点，其左子树中所有点的点权小于(等于)它，其右子树的所有点的点权大于它。我们可以根据这个性质来递归查找第k小的值有一个巧妙的处理方法，我们从根开始一直往左子树深搜，那么搜索结束的时候所在的节点一定是最小的。然后我们回溯，这样就能按照从小到大的顺序回去，一边回去一边让k - 1，当k为1的时候，当前节点就是答案了。我们假设有这么一个二叉搜索树然后我们要找到它的第4小的值，于是我们可以这样找我们从根节点开始，一直递归到底部，当前k为4当前值不是1，所以要减去1然后回溯当前值不是1，所以要减去1然后回溯当前值不是1，发现有右子树，于是我们减去1之后到...

方法1：递归例如，我们给定前序遍历：1、2、3、4、5、6、7中序遍历：3、2、4、1、6、5、7我们知道，前序遍历的顺序是根，左子树，右子树，所以在一段前序遍历中，第一个一定是当前子树的根。我们找到这个根，然后我们知道中序遍历中，顺序是左子树，根，右子树。于是我们可以找到根的位置，其左边就是左子树，右边就是右子树，如此递归构造即可。接下来对于我们给定的例子来模拟构造一遍先找根，找到左右子树的范围然后在前序序列中把左子树，右子树的范围找出来再继续对左子树找根，找到其左右子树的范围依次类推，对每个子段都做类似操作即可时间复杂度：每个节点都遍历了一遍，所以是O(n)空间复杂度：存了一棵二叉树，所以...

方法1：模拟我们假设只有一个栈的时候，然后当我们依次推入1、2、3这些元素，这个栈就变成了这样那么当我们这个时候要将队头，也就是栈底弹出的时候，我们发现有很多挡在他前面，所以我们需要另外一个“中转栈”来存储这些元素，就像这样于是我们发现，此时第二个栈的栈顶就是我们要弹出的元素，弹出即可。然后把之后的元素都放回到原栈中即可时间复杂度：push操作为O(1)，pop操作由于需要讲全部元素弹出，为O(n)空间复杂度：需要用栈来存，O(n) class Solution { public: void push(int node) {//这里直接push即可 stack1.push(node); } i...

题目链接方法1：递归给不太能懂递归的朋友图解一下递归的方法是，我们从头指针开始搜索，然后从尾指针开始回溯的时候返回链表的逆序序列首先这是最初状态，我们从头指针开始然后我们发现当前不是尾指针，于是先递归下去继续递归我们发现，当前指针的next是不存在的，所以这是尾指针了，开始回溯，回溯的时候记录序列即可具体代码如下时间复杂度：每个点都遍历了一遍，是O(n)空间复杂度：每个点都遍历了一遍，开了一个数组来存，是O(n) /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), n...

题目链接方法1：模拟模拟替换的过程，当我们遇到空格的时候用“%20”代替即可时间复杂度：遍历了整个字符串，为O(n)空间复杂度：一个字符串O(n) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSpace(string s) { string res = "";//这是用来储存答案的串 for (int i = 0; i < s.size(); i ++ )...

题目链接方法1：暴力枚举其实就是一个一个数查看过去，如果找到了目标数字就返回true，否则返回false设二维数组有n行，每行m个数字时间复杂度：由于我们遍历了整个数组，所以时间复杂度是O(n * m)空间复杂度：就是一个二维数组的大小，所以空间复杂度是O(n * m) class Solution { public: bool Find(int target, vector<vector<int> > array) { //暴力枚举即可 for (int i = 0; i < array.size(); i ++ ) { for (int j = 0; j &l...

序列化二叉树 题目链接方法1：层序遍历知识点：队列方法：队列所谓层序遍历，就是从上到下依次遍历节点，将每个节点的左右儿子加入到队列中，然后依次出队和入队，遍历得到的顺序就是层序遍历，我们用队列来模拟，具体可以看代码的注释，这里先给出图示例如这棵树中，我们先将根节点[1]加入到队列中，这样就是然后我们弹出队头，查看队头连接的两个子节点，发现是2，3，于是分别加入队列此时我们继续弹出队头2，查看队头连接的两个子节点，发现无子节点，就不用加入队列，类似的，继续看3，我们发现其有4，5作为子节点，于是加入队列类似的，只要依次弹出队头，查看其连接的子节点，如果有就加入到队列中，否则就查看下一个，最后弹出...

根据我的主观感受排序   H:蒟蒻wzc的填数游戏知识点：模拟暴力模拟就完事了  #include <bits/stdc++.h> using namespace std; char s[30000]; int g[10][10]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; inline void solve() { memset(g, 0, sizeof g); int n; cin >> n; unordered_map<char, int> f; f['w'] = 0, f['d'] = 1, ...

A. Three swimmers  解题方法：我们可以发现，每个运动员的周期分别是a，b，c。于是我们的任务变成了找出p所在的周期位置，然后找到右边界到p的距离，对每个运动员到p的距离取最小值即可。  #include <bits/stdc++.h> using namespace std; typedef long long LL; inline void solve() { LL p, a, b, c; cin >> p >> a >> b >> c; LL k, res; // k存周期位置，res存答案 k = (p + a...

这章最重要的两大知识点就是BFS和DFS了 首先，DFS方面要了解搜索树这一概念，知道了这个之后对于递归中的回溯操作会理解一些 BFS就是相当于边权为1的最短路，我们一般运用队列  0X21树与图的遍历  主要就是模板，其中包括了树的深度优先遍历，前序遍历，后序遍历，中序遍历。还有树的重心等知识点。还有图的广度优先遍历，拓扑排序。其中拓扑排序是重点，模板如下  void top_sort() { queue<int> q; for (int i = 1; i <= n; i ++ ) { if (d[i] == 0) q.push(i); } while(!q.empty()...

A. Wizard of Orz  这题的解法就是找规律，输出98901234567890123456789... 下面是代码  #include <bits/stdc++.h> using namespace std; void solve(int n) { if (n == 1) cout << 9; else if (n == 2) cout << 98; else if (n == 3) cout << 989; else { n -= 3; int tmp = n / 10; cout << 989; while (tmp ...

说在前面  最近快要期末了所以咕咕咕了好久，但是学早就学好了，只是一直没更新。 为了日后更好的写自己的博客，顺便学习了一点点markdown语法，希望观感会更好一点。 我是小白，如果有发现文章有不对的地方，还请指正，谢谢。 接下来的博客我打算花更多的篇幅在分析知识点（主要是自己学不太明白的）上面（毕竟书上其他博客都有题解） 接下来是正文   0X11 栈  这是其中一种基础的数据结构，我们不但要学会用STL，也要学会用数组模拟 只需要一个参数tt来表示栈顶的指针即可 根据书中，栈有以下几种应用： 1.表达式的计算： 电脑习惯计算的是后缀表达式，我们人类习惯看中缀表达式。那么假如给我们一个中缀表...

https://ac.nowcoder.com/acm/contest/9667/F 知识点：贪心 我们首先要知道这题是怎么贪心的 首先我们看得出，除了最后一个拿不到，其他的每个元素都会拿到，也就是说价值都是会加到的 而我们贪心的方法就是每次都找最大的石头堆，然后让他和隔壁的合并，所以最后最大的石头堆会用到n-1次  #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; long long ans=0,m=0,x; for(int i=0;i<n;i++){ cin>&...