TechFlow的博客

大家好，欢迎阅读周末codeforces专题。我们今天选择的问题是contest 1419的C题，目前有接近8000的人通过了本题。今天这题的难度不大，但是真的很考验思维，一不小心就会踩中陷阱，我个人觉得非常有意思，适合周末动动脑。题目链接：https://codeforces.com/contest/1419/problem/C题意有一个叫做Killjoy的特工发明了一种新型的冠状病毒叫做Convid-2069，专门在codeforces平台上传播。这种病毒通过rating传播，只要两个人的rat

今天这篇文章给大家讲讲hashmap，这个号称是所有Java工程师都会的数据结构。为什么说是所有Java工程师都会呢，因为很简单，他们不会这个找不到工作。几乎所有面试都会问，基本上已经成了标配了。在今天的这篇文章当中我们会揭开很多谜团。比如，为什么hashmap的get和put操作的复杂度是O(1)O(1)O(1)，甚至比红黑树还要快？hashmap和hash算法究竟是什么关系？hashmap有哪些参数，这些参数分别是做什么用的？hashmap是线程安全的吗？我们怎么来维护hashmap的平衡呢？让我们

大家好，今天codeforces专题选择的是一场education比赛的C题。Education是codeforces的一种特殊赛事，它的主要作用是教育，也就是让更多的人了解codeforces的比赛机制。所以education赛事的题会相对来说容易一些，更加适合新手。我选的这道题虽然是C题，但是难度并不高非常基础。链接：https://codeforces.com/contest/1418/problem/C这题通过的人数有3600多，相比之前介绍的题算是比较少，但是题目难度其实更低一些。我们废话不

大家好，欢迎大家来到算法数据结构专题，今天我们和大家聊一个非常常用的算法，叫做LRU。LRU的英文全称是Least Recently Used，也即最不经常使用。我们看着好像挺迷糊的，其实这个含义要结合缓存一起使用。对于工程而言，缓存是非常非常重要的机制，尤其是在当下的互联网应用环境当中，起到的作用非常重要。为了便于大家更好地理解，我们从缓存的机制开始说起。缓存缓存的英文是cache，最早其实指的是用于CPU和主存数据交互的。早年这块存储被称为高速缓存，最近已经听不到这个词了，不知道是不是淘汰了。因为

大家好，欢迎阅读周末算法题专题。今天选择的算法题来源于昨天同一套题中的D题，这题全场通过的人数在2600人左右。虽然通过的人数更少了一些，但是题目的难度却并没有增加很多，但是趣味度增加了。我也是第一次遇见这样的问题。题目链接：https://codeforces.com/contest/1405/problem/D废话不多说，我们一起来看这题的题意。题意我们都知道数据结构当中的树有这样一个性质，如果树当中有n个点，那么它应该由n-1条无向边组成。并且树当中是一定没有环的，如果有环的话n-1条边就不

大家好，欢迎大家阅读周末算法题专题。今天我们选择的题目是codeforces 1405比赛的C题。题目链接：https://codeforces.com/contest/1405/problem/C这道题有6800多人通过，怎么看也不算是难题，但是我做了一上午都没能AC。最后又苦思冥想了很久，才最终做出来。做出来之后的第一感觉就是这道题太牛了，值得一说，算是那种谁都能看懂题意，都能想想办法，但是能做出来很不容易的问题。还是一如既往的codeforces赛题的风格，不严格考察算法，你做不出来大概率不

大家好，欢迎阅读算法数据结构专题，今天我们来聊聊一个新的数据结构，叫做线段树。线段树这个数据结构很多人可能会有点蒙，觉得没有听说过，但是它非常非常有名，尤其是在竞赛圈，可以说是竞赛圈的必备技能。所以如果以后遇到有人看了一点算法导论就在你面前装逼，你就可以问他：请问线段树更新的复杂度是多少？不过如果你会线段树，你也要小心一点，最好不要在面试的时候随便透露你会这个算法。否则面试官一下子就会知道你是圈里人，然后你会发现你后面的面试问题比之前好像难不少。当然也有可能遇到面试官自己不会，为了防止尴尬强行让你用非线

今天是算法数据结构专题的第36篇文章，我们一起来继续聊聊强连通分量分解的算法。在上一篇文章当中我们分享了强连通分量分解的一个经典算法Kosaraju算法，它的核心原理是通过将图翻转，以及两次递归来实现。今天介绍的算法名叫Tarjan，同样是一个很奇怪的名字，奇怪就对了，这也是以人名命名的。和Kosaraju算法比起来，它除了名字更好记之外，另外一个优点是它只需要一次递归，虽然算法的复杂度是一样的，但是常数要小一些。它的知名度也更高，在竞赛当中经常出现。先给大家提个醒，相比于Kosaraju算法，Tarj

今天是算法数据结构专题的第33篇文章，我们一起来聊聊最短路问题。最短路问题也属于图论算法之一，解决的是在一张有向图当中点与点之间的最短距离问题。最短路算法有很多，比较常用的有bellman-ford、dijkstra、floyd、spfa等等。这些算法当中主要可以分成两个分支，其中一个是bellman-ford及其衍生出来的spfa，另外一个分支是dijkstra以及其优化版本。floyd复杂度比较高，一般不太常用。我们今天的文章介绍的是bellman-ford以及它的衍生版本spfa算法。图的存储

今天是算法和数据结构专题的第32篇文章，我们来聊聊拓扑排序的问题。拓扑排序是图论当中一个非常简单也非常常用的算法，它有很多的功能。它可以用来检测有向图当中是否存在环，也可以用来解决存在依赖的调度问题。下面我们就来看看这个算法的庐山真面目吧。算法场景拓扑排序是英文音译，它的英文原文是Topological Sorting，是一个比较抽象的概念，没有很信达雅的翻译。它指的是一个DAG(Directed Acyclic Graph)即有向图所有顶点满足一定条件的线性序列。也就是说图中的这些顶点的排序之间

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是算法与数据结构专题的第31篇文章，我们一起来聊聊二分图匹配与匈牙利算法。在上一篇文章当中我们介绍了一个有趣的稳定婚姻问题，模拟了男男女女配对的婚恋场景，并且研究了一下让匹配更加稳定的Gale-Shapley算法。如果错过了这篇文章的同学可以从下方的传送门回顾一下婚姻稳定问题的具体内容。学算法还能指导找对象？是的，这就是大名鼎鼎的稳定婚姻算法在上一篇文章的末尾我们曾经提到过，婚姻匹配问题本质上来说其实是二分图匹配的问题。那么什么又是二分

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是LeetCode专题第53篇文章，我们一起来看LeetCode第86题，Partition List（链表归并）。本题的官方难度是Medium，点赞1276，反对296，通过率大约41%。总体来说，这题质量一般，通过率有点高，整体难度偏简单，算是一道链表的基础题。对链表熟悉一些的同学来说，问题不大。题意我们首先来看下题意，题意是说给定一个链表以及一个整数x，要求根据x来对链表中的元素进行归并，使得链表的前半部分的结果小于x，后半部

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是算法和数据结构专题的第28篇文章，我们一起来聊聊一个经典的字符串处理数据结构——Trie。在之前的4篇文章当中我们介绍了关于博弈论的一些算法，其中应用最广也是最重要的就是最后的SG函数。了解到这些之后，足够我们应付常见的博弈论算法问题了。博弈论本身就是一门学科，其中有这很深邃的理论基础，我们只是浅尝辄止，大家感兴趣的可以自行钻研一下，相信一定会很有收获。小故事以前读过一个大牛的文章，文章里讨论了一个问题，如果不是为了面试的话，我们

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是算法和数据结构的第21篇，我们来聊一个新的数据结构——堆(heap)。和链表、二叉树以及数组这些热门的数据结构相比，堆相对比较冷门。如果你对数据结构了解不深的话，可能很少听说。但是我们经常用到它，虽然可能你并不一定能感知到。比如说优先队列，我们就经常使用。我们需要用到这样一个数据结构，能够根据我们存入数据的优先级进行排序，将优先级高的排在前面。在和调度相关的一些系统和算法当中，优先队列是必然会用到的。但是很少有人知道，优先队列说是一个队列

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是算法和数据结构专题20篇文章，我们继续最小生成树算法，来把它说完。在上一篇文章当中，我们主要学习了最小生成树的Kruskal算法。今天我们来学习一下Prim算法，来从另一个角度来理解一下这个问题。从边到点我们简单回顾一下Kruskal算法的原理，虽然上篇文章当中用了很多篇幅，但是原理非常简单。本质上就是我们对图中所有的边按照长度进行排序，之后我们按照顺序依次把它作为树的骨干，加入到树上来。在此过程当中，我们为了避免导致产生环，而

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是机器学习的第16篇文章，我们来继续上周KD-Tree的话题。如果有没有看过上篇文章或者是最新关注的小伙伴，可以点击一下下方的传送门：【硬核】机器学习与数据结构的完美结合——KD-Tree旋转不可行分析上周我们实现了KD-Tree建树和查询的核心功能，然后我们留了一个问题，如果我们KD-Tree的数据集发生变化，应该怎么办呢...

本文始发于个人公众号：TechFlow，原创不易，求个关注今天是分布式系统的第八篇文章，核心内容是B+树的原理。今天的文章是上周B树的延伸，所以新关注的或者是有所遗忘的同学建议先从下方链接回顾之前的内容。硬核挑战——从零开始动手图解B树B+树的特性B+树和B树一样都是多路平衡树，也叫多叉树。两者的性质也基本一致，在具体来看详细内容之前，我们先来总体看下B+树的特性，先有个大概的印象。...

本文始发于个人公众号：TechFlow，原创不易，求个关注本篇原计划在上周五发布，由于太过硬核所以才拖到了这周五。我相信大家应该能从标题当中体会到这个硬核。周五的专题是大数据和分布式，我最初的打算是和大家分享一下LSM树在分布式存储引擎当中的应用。但是想要能够真正深入理解了LSM的精髓，以及它构思巧妙的点，必须要对传统的数据库的B树和B+树有所了解。所以才有了今天的文章。虽然我自己完整地将...

本文始发于个人公众号：TechFlow，原创不易，求个关注在之前介绍SkipList的文章当中，有一些同学反馈说由于对链表缺少认知以及了解，所以直接啃算法有些过于困难。加上之前的文章当中介绍过了栈，所以这次继续线性表这个话题，我们来一起讨论一下链表。链表是很多数据结构的基础，它的最大特点是支持快速的删除和插入，因此在很多数据频繁变动的场景下使用广泛。而且链表的可拓展性较强，所以它的应用非常广...

本文始发于个人公众号：TechFlow，原创不易，求个关注今天继续介绍分布式系统当中常用的数据结构，今天要介绍的数据结构非常了不起，和之前介绍的布隆过滤器一样，是一个功能强大原理简单的数据结构。并且它的缺点和短板更少，应用更加广泛，比如广泛使用的Redis就有用到它。SkipList简介SkipList是一个实现快速查找、增删数据的数据结构，可以做到O(logN)O(logN)O(lo...