「置顶」本博客导航!

若您的网页显示mathjax公式出现问题,导致无法阅读,请在任意Mathjax公式上点击右键,Math settings->Math renderer->更改为HTML-CSS即可解决。

因博主水平有限,不足之处请直接在评论区指出,博主将感激不尽!

欢迎您光顾本博客!

本博客 包括LeetCode刷题记录和经验,机器学习,以及硕士专业研究课题方面。

本人硕士研究课题是 纠删码去重在Ceph分布式存储集群上的应用。对此研究方向感兴趣的道友欢迎一起交流。


👌LeetCode刷题记录

A. 动态规划

动态规划是将问题分解为更易解决的子问题的一类方法,本blog由浅入深介绍动态规划的常见题型,dp是笔试最常考的问题之一。

  • 做一只可爱的小🐖背包 Cover「背包九讲」 >>传送门<<

背包问题是很经典的一类dp问题。本blog介绍9种类型的背包问题。面试者若能举一反三,必将事半功倍。

B. 树类问题

如果你还不知道什么是树,没有关系!我们将从零开始介绍,1. 二叉树的表示 2.二叉树的遍历 3. 二叉树序列化以及反序列化 4. 树形dp 5.线索二叉树 等。使得你对树类问题有基本认识。

树状数组和线段树都是用于维护数列信息的数据结构,支持单点/区间修改,单点/区间询问信息。以增加权值与询问区间权值和为例,其余的信息需要维护也都类似。时间复杂度均为$O(logn)$。

前缀树又名Tries树字典树、单词查找树等,常用于快速检索,大量字符串的排序和统计等。Trie相比于哈希表存储多个具有相同前缀的键时所用空间较少。因此前缀树只需要$O(m)$的空间,m为键长度。在字符串问题中很常见。

红黑树的结点增删改查效率非常优良,都为$log(n) $, 应用方面:1. Linux内核进程调度由红黑树管理进程控制块。 2. Epoll用红黑树管理事件块。 3. nginx服务器用红黑树管理定时器。 4. C++ STL中的map和set的底层实现为红黑树。 5. Java中的TreeMap和TreeSet由红黑树实现。 6. Java8开始,HashMap中,当一个桶的链表长度超过8,则会改用红黑树。红黑树在面试中会出现,笔试中可不会出现哦。

AVL树是严格平衡的二叉树,红黑树是弱平衡的二叉树。和红黑树相比,AVL树是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此相同节点数的前提下,AVL树的高度往往低于红黑树。同样,在笔试中不会出现,面试时可能会问概念。有兴趣的读者可以自己实现。

C. 模拟问题

很多时候多指针(双指针,三指针,快慢指针)能极大的帮助我们降低时间复杂度和空间复杂度,比如从$O(n^2)$降低到$O(n)$。例如求链表到数第N个节点,以及判断链表中是否有环,神奇的Floyd判圈法。

包括冒泡排序,选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序,计数排序,桶排序,基数排序。研究它们算法,以及最好最坏平均时间复杂度和空间复杂度,是否为就地替换以及稳定性。

如果输出有非常的项(比如求子集,全排列),要确保结果完整且不重复,有多种策略:1. 递归,2. 回溯,3. 字典, 4. 数学, 5. 状态压缩, 6. 剪枝技巧

在滑动窗口中有两个指针,一个指针静止,而另一个指针保持移动。我们在s上滑动窗口,如果能够包含整个T(注意,T可能有重复字符),如果能收缩,我们就收缩窗口直到得到最小窗口。

单调栈内元素保持非递减顺序,在特定的应用背景下,比如一维参量在一个连续范围变化,温度在一段时间变化,股价的增减,柱状图。请考虑单调栈。

  • 数组和字符串的🆒skr操作——前缀和 >>传送门<<

前缀和的本质是一维或二维差分数组,对区间的查询和修改,比树状数组和线段树相比,不需要特定的数据结构,更加容易使用。

  • 一句话能打败 99.99999%的程序员的位操作代码 >>传送门<<

位操作是计算机最基本的操作之一,它可以与很多问题进行结合,从而优化解法空间复杂度,比如在状态压缩中利用左移,数组low_bit以及Brian kernighan算法.

D. 贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

E. 数学

数论,求质因数,最大公因数(GCD),最小公倍数(LCM), 快速幂算法, Gauss消元法, 几何,排列组会问题等

F. 字符串

KMP算法是用于字符串匹配,十分巧妙,也极难理解。

回文指正反读都一样的字符串,Manacher算法专门用于解决回文问题。当然,Rabin-Karp编码在一定条件下也是不错的解决问题的方法。

G. 图论

本博客介绍了四种图的表示方法,包括 邻接矩阵表示法,关联矩阵表示法,邻接表表示法,弧表示法,星形表示法。以及图的典型算法,包括Dijkstra, Floyd, Bellman-Ford以及SPFA算法。

二叉树里面的三种遍历既可以用DFS(递归写法),也可以用BFS(迭代+栈),而层序遍历对应的就是BFS。

在图和树类型题目,以及部分数组题目,都可以时不时看到两种算法同时出现。递归注意1. 触发条件 2. 终止条件 3. 剪枝问题。

最小生成树($Minimal Spanning Tree,MST$):有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。比较常用的有两种算法:$Kruskal$算法和$Prim$算法。

并查集被许多$OIers$认为是简洁而高雅的数据结构之一,主要用于解决一些元素分组的问题,它管理一系列不相交的集合,并支持两种操作。即查询合并。在求联通/合并问题能大显身手。

给定一个 n 个点 m 条边的图,要求从指定的顶点出发,经过所有的边恰好一次(可以理解为给定起点的「一笔画」问题),使得路径的字典序最小。常见算法有$Hierholzer$算法。

回溯法,通常以dfs或bfs为载体,在特定的问题下,通过试错,得到所有可能状态,当然有些状态是多余的,因此剪枝显得极为重要。

目前的路由器都在运行的算法,你一定不想不知道!

H. 综合应用

这类问题涉及很多知识,可能包括dp,单调栈,有限状态自动机等。

在零和博弈中,让自己最优和让对手最差其实是相同的目标!原因还是那句话,两人的总得分不会变化,自己多了,对手必然减少。没有人是傻子,但是赢者通常会利用游戏规则!

G. 其它

确定有限状态自动机(以下简称「自动机」)是一类计算模型。它包含一系列状态,这些状态中:有一个特殊的状态,被称作「初始状态」。还有一系列状态被称为「接受状态」,它们组成了一个特殊的集合。其中,一个状态可能既是「初始状态」,也是「接受状态」。

包括C++,Java, Python代码中很容易遇见的坑,类似于错别字和陷阱,一定要注意。

Leetcode 上典型设计问题的赏析。举一反三,触类旁通。

在分布式存储系统Redis中一个非常优秀的算法,跳表,LC上也有对应的题目。

刷题之暇,整点好活!

🤖机器学习系列

以周志华老师《机器学习》为基准,力争从算法角度解释机器学习的所有问题。

🚀大数据与分布式存储系列

以云存储和大数据为研究背景。辐射包括Ceph,Hadoop,纠删码研究等方方面面。

其中「入门部署」表示初始部署集群,「高级部署」表示有一定挑战性的部署,比如手动部署,「参考」表示一些非核心的帮助理解的内容,「核心」表示深入理解原理,并且熟练操作。「综述」表示一些学术性总结内容。「研究向」表示需要很多时间和兴趣来研究的内容,面试一般不会考到,但很经典。

入门

包括手动部署,存储集群配置以及源码编译等。

ceph的基本原理,供读者有一个大致了解。

  • 「入门部署」ceph-ansible部署踩坑日记——>>传送门<<

ceph-ansible是目前用的最广的ceph部署工具,功能远超ceph-deploy。建议采用此方式。

完整的ceph-deploy部署流程。

  • 「综述」纠删码在存储系统的应用——>>传送门<<

最最最最最最新的纠删码综述,包括RS码,包括RS码,MSR,LRC等。不断更新,引领前沿。

经典的Jerasure库,源码分析,经典必看!

Blaum-Roth\Liberation\Liber8tion介绍和理论。

进阶

  • 「核心」Ceph三部曲之一:浅析CRUSH算法———>>传送门<<

介绍Ceph核心算法,CRUSH算法。以及相关实践。

  • 「核心」Ceph三部曲之二:ceph纠删码部署——>>传送门<<

ceph中纠删码部署。从原理到五种库源码,笔者研究重点,因为目前Ceph纠删码还有很多待完善的地方。

  • 「核心」Ceph三部曲之三:迁移之美——PG读写流程与状态迁移详解 ———>>传送门<<

ceph最难理解也最有趣的概念,PG。深入学习必看!

  • 「核心」Ceph三部曲之四:下一代对象存储引擎BlueStore ———>>传送门<<

目前的存储介质已经由传统的机械硬盘hdd升级到SSD和NVME,这为下一代对象存储BlueStore提供了基础,相比于目前FileStore,BlueStore拥有无与伦比的优势。

  • 「核心」Ceph学习三部曲之五:控制先行——Ceph的QoS策略>>传送门<<

详细介绍Ceph QoS策略,讲解dmClock等算法实现和操作。

  • 「核心」Ceph学习三部曲之六:分布式块存储RBD>>传送门<<

介绍Ceph分布式块存储,包括快照克隆等功能的理解。

  • 「核心」Ceph学习三部曲之七:对象存储网关RGW>>传送门<<

Ceph对象存储使用Ceph对象网关守护进程(radosgw),它是一个用于与Ceph存储群集进行交互的HTTP服务器。由于它提供与OpenStack Swift和Amazon S3兼容的接口,因此Ceph对象网关具有自己的用户管理。

  • 「核心」Ceph学习三部曲之八:分布式文件系统CephFS

Ceph文件系统或CephFS是在Ceph的分布式对象存储RADOS之上构建的POSIX兼容文件系统。CephFS致力于为各种应用程序提供最新,多用途,高可用性和高性能的文件存储,包括传统用例(如共享主目录,HPC暂存空间和分布式工作流共享存储)。

Ceph的池是理解PG,OSD的桥梁,可以直接操作的对象!

ceph文件配置参考。

对Ceph的管理者Monitor进行理解。监视器们维护着集群运行图的“主副本”,就是说客户端连到一个监视器并获取当前运行图就能确定所有监视器、 OSD 和元数据服务器的位置。

应用实战!

大师

🍜文化

看看就好,笔者的一些随笔和感想。涵盖方面及其广泛。

看知乎,学炒股。

笔者对日语文化有浓厚兴趣,立志考过N1,いしょうに頑張ってなあ!


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!