主页

写在前面 一些基本关系 结点数和树高 \[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; ...

写在前面 最近力扣周赛出了很多关于数字位数的题, 顾名思义, 就是对一个大整数的每一个十进制位进行操作, 由于之前对这方面的内容不太熟悉, 真正写的时候就吃亏了. 下面写一下这方面的常用的一些技巧, 例如取出任意整数的每一位等等. 取出整数的每一位 通过对10取余或者整除, 可以从个位到最高位依次得到每一个位的值, 如下: n = 12345 ans = [] while n: ans.append(n % 10) n //= 10 print(ans) # [5, 4, 3, 2, 1] 上面的是数学方法, 速度比较快, 下面是一个基于字符串的方法, 虽然慢但是直观(我初刷lc时候钟爱这种方法) n = 12345 s = str(n) ans = [i...

写在前面 最近刷LeetCode, 发现很多双百题解中用到的都是位运算技巧, 下面来总结一下位运算的常用技巧. 一开始参考了知乎的一篇回答, 里面推荐一本书叫做算法心得, 英文原版为Hackers Delight, 听这个名字就知道是一些hack技巧, 有机会一定要研读一下. 下面的代码用C++给出. 可能出现的一些数字: 48: ‘0’ 65: ‘A’ 97: ‘a’ 预备知识 首先给出一些预备知识, 包括如何进制转换等. 任意进制到十进制 // 直观的想法 int x2dec_v1(string x, int k) { int ans{}, n = x.size(); for (int i{}; i <...

可能用到的STL算法一览 前缀和计算: partial_sum 使用方法: std::partial_sum - cppreference.com; #include <numeric> #include <vector> #include <iostream> #include <iterator> #include <functional> void t1() { std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // 或 std::vector<int>v(10, 2...