主页

写在前面 C++中的静态绑定和动态绑定;

写在前面 最近看很多的面试题都有常见算法的迭代(非递归)写法这一类, 下面总结下这类问题的一些一般方法(我自己的心得体会, 如有不对欢迎大家批评指正). 在常见算法中, 涉及到二叉树等树型数据结构这样的基本上都有对应的递归写法, 但是由于递归调用的过程中会出现程序栈空间的开辟, 造成内存空间的浪费(尾递归不会), 并且每一次调用的栈帧都会保存很多并不会在之后调用中用到的参数,变量等, 这就进一步加大了内存的浪费, 所以递归算法虽然直观, 也应该去想一下对应的迭代方法, 这也算是程序优化的一种主要思路. 除了数据结构, 一些排序算法也用到了递归, 例如快速排序, 归并排序和堆排序, 这些排序算法用递归写直观不少, 但是掌握其迭代写法也很有必要. 下面给出我对于转换递归为迭代的一些...

写在前面 总结一下经典的差分数组方法, (华为机试刚考了), 思路很简单, 但是没遇到的话想写出来还是有点难度的. 参考了 labuladong 的博客, 里面的代码是 Java 实现的, 这里用 C++重写一下. 小而美的算法技巧：差分数组. 思路 差分数组是一种支持频繁对数组的某一区间进行增减, 以及查询的数据结构. 基本思想就是: (高中学的数列) 设数列为 ${a_i},\ i\in[0,\ n]$, 那么做一新数列${b_j},\ j\in[0, n]$, 且满足 \[\begin{cases} b_0 = a_0\\ b_j = a_i - a_{i-1}, \ j\in[1,\ n] \end{cases}\] 这样的数列(数组) $b_j$ 其...

写在前面 一些基本关系 结点数和树高 \[hh\] 完全二叉树节点范围 节点定义 取自 LeetCode. 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(...

写在前面 写一下有向无环图(DAG, Directed Acyclic Graph)上的拓扑排序, 废话不多说了, 介绍部分大家可以参考算法导论或者 oi-wiki. https://oi-wiki.org/graph/topo/; 我写的完整代码: Topological-Sort 我们可以拿大学选课的例子来描述这个过程，比如学习大学课程中有：单变量微积分，线性代数，离散数学概述，概率论与统计学概述，语言基础，算法导论，机器学习。当我们想要学习 算法导论 的时候，就必须先学会 离散数学概述 和 概率论与统计学概述，不然在课堂就会听的一脸懵逼。当然还有一个更加前的课程 单变量微积分。这些课程就相当于几个顶点 , 顶点之间的有向边 就相当于学习课程的顺序。...

C++ snippets ostream& operator<<(ostream& os, const vector<int>& v) { for (auto i : v) os << i << " "; return os << endl; } ostream& operator<<(ostream& os, const vector<vector<int>>& v) { for (auto i : v) os << i; return os; } 入门 ...

二分-STL算法库 下面是二分查找相关的一些STL算法函数, 方便之后使用, 手写二分熟悉之后用STL刷题会更加快速. 计数: count和count_if 一般查找: find和find_if 基本二分查找: binary_search 寻找下边界: lower_bound 寻找上边界: upper_bound 寻找边界: equal_range 二分查找模板(基础版) 左闭右闭区间(常用) class Solution { public: int search(vector<int>& nums, int target) { int l{}, r = nums.size() - 1; while (l ...

找路径问题 模板题 剑指 Offer 35. 复杂链表的复制; 感觉跟下一个题很类似, 就放在这里了, 哈希记录遍历情况, 然后递归创建新节点即可(当然还有纯链表做法) class Solution { unordered_map<Node*, Node*> used; public: Node* copyRandomList(Node* head) { if (!head) return head; if (!used.count(head)) { auto node = new Node(head->val); used[head] = node; ...