如何在 LeetCode 竞赛中 Rank 达到 2000 分

首先自我介绍一下,本科非计算机专业,非 985/211。从 2018 年 8 月份开始正式接触算法,从 LeetCode 入的门。当时的 LeetCode 还是只有美服版本,记得国服是在 2018 年底才开始运营起来的。当时的算法水平可谓小白,基本上是零基础。当时,就硬性地按频率顺序刷。频率只有会员才能看到,所以当时花了 800 左右的 RMB 买了美服的会员。磕磕绊绊刷到 2020 年初,也刷了 500 道题目吧。当时的竞赛水平很差,只有在极少数的情况下能够在规定的 1 个半小时内 AC 四道题目。2020 年我开始讲究了一些方法和策略,开始系统性地学习算法。同时,在刷题之后,进行深入的思考。在经过不断地可以练习之后,LeetCode 的竞赛题目可以在不是很难的情况下 AC 四道题目,而且还能剩下一些时间提前完成。胡小旭 LeetCode Ran下面是我 LeetCode 的 rank... Read More

The advantages of Consistent Hashing

It's one specific hash method. For Linear Hashing, it has to almostly rehash all the keys when triggered rehash. Howerver, the Consistent Hashing would just change the K / n keys. K is for the amount of keys, n is for the amount of slots.Therefore, there are some advantages of consistent hashingStorage BalanceLoad BalanceOversmootReferenc[1]. Consistent Hashing. https://en.wikipedia.org/wiki/C... Read More

Got “our configuration does not allow connections to ” while using composer install

Got this message while using the composer install command[Composer\Downloader\TransportExceptionYour configuration does not allow connections to http://xxx.com:80/path/to/repo/repo-name-0.0.0.tar.gz. See https://getcomposer.org/doc/06-config.md#secure-http for details.Just run this commandcomposer config -g secure-http falsThen, go aheadReferrenc[1]. Latest Composer version not pulling Larav... Read More

数据结构与算法,我到底为什么而学?

今天,我想聊聊在数据结构与算法学习路上的一些小感想。2018 年 8 月左右,开始有计划、有目的性地学习这门知识。当然,这期间也会有怠慢的时候。不过,在这断断续续的 21 个月里,对于学习数据结构与算法这件事儿有了一个更新层次的认识与思考。下面,从两个方面聊聊:学到了什么?为什么而学?学到了什么?数据结构与算法。不不不,这只是问题在字面意识上的答案。我想讲的是,通过数据结构与算法这门课程,到底学到了什么,或者说我学会了什么?在之前,买过那些正规传统的教科书似的书籍,比如严蔚敏的《数据结构》。当然,像《算法导论》这样的神书是不会错过的。作为一个初学者来说,这两本书在学习上带来了很大的帮助。不管怎么说,这个阶段是一直在学习那些经典的、成熟的数据结构与算法。然后,会到 LeetCode 上做一些算法题目。我们知道,LeetCode 上的题目是那种面向面试的问题,可以说几乎每个题目都是用一些非常明... Read More

C++ memset 的使用

在竞赛时使用 memset 发现初始化的默认值无法生效,后来发现我对 memset 的参数的理解有误。void * memset ( void * ptr, int value, size_t num );将指针 ptr 所指向的内存块中前 num 个字节,用 value 替换。注意,这里面的 value 是一个字节的值。下面谈及两个场景,初始化为 0。memset(a,0,sizeof(a));初始化“最大值”,之所以加上引号,是因为并不是真正的最大值。但是能够带来最大值的效果的同时,还能带来一些好处。memset(a,0x3f,sizeof(0x3f));0x3f3f3f3f 代表的十进制数值是 1061109567 是 10^9,和 32 位的有符号整型的最大值是一个量级。而往往,数据在一般情况下都是小于 10^9 的。所以,可以达到替换最大值的效果0x3f3f3f3f + 0x3f... Read More

60分钟搞定Tarjan算法求解无向图的割点与桥

本人在学习 Tarjan 算法求解无向图的割点与桥的问题时,很快发现了一篇简洁易懂的文章。很顺利地了解算法的思路,并写出了“高效”的代码,此时内心飘过 —— So Easy。然而,当我翻开《算法竞赛进阶指南》这本书的有关篇章时,我发现其中经过精简优化的代码有几条语句让我不得其所。以至于,花了较多心思和时间来思考🤔这段真正高效的 Tarjan 算法的工作原理以及代码的编写。关于 Tarjan 算法,我将会写若干篇系列文章,来完整系统地介绍 Tarjan 算法的原理以及其主要解决的问题。而在本章我主要讲一个问题 —— 如何使用 Tarjan 算法求解无向图的割点与桥。在讲述问题之前,我们先来简单地了解下什么是 Tarjan 算法?Tarjan 算法Tarjan 算法是基于深度优先搜索的算法,用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥,进一步地可以求解无向图的... Read More

递归

递归递归是什么?递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法 。维基百科简单说,就是自身调用自身。为什么使用递归?往往面对一类问题时,如果它的规模足够小或者说达到既定的边界条件时,我们可以直接获取答案。但是,当这类问题的规模比较大时,却往往无法直接获取答案。那么,这个时候就可以通过“自身调用自身”的方式,来不断地减小问题的规模,直到问题的规模被缩减到足够小时,直接将答案返回上层的调用者,最终获取到原问题的解。如果将求解的过程逆过来,那么就是所谓的递推。通过这种方式,我们可以写出“优雅”的代码去解决规模比较大的问题。进而,避免了通过递推的方式,在每一次递推时产生的复杂的条件判断的问题。上文中提到经过递归调用,会不断地减小问题的规模,有些作者认为这是一种减治法。递归的特性自身调用自身在上文中,已经提到了这个特性,而且也非常好理解,不再赘述。... Read More

到底该如何刷LeetCode?

引言本人非计算机专业出身,本科期间一直觉得数据结构与算法是一项非常基础也重要的知识,但是由于自己可有可无的欲望和糟糕的自律能力,并没有深入地学习这项知识技能。但是,随着时间的流逝,无论在工作中、网络中还是朋友圈中,发现数据结构与算法是无比的重要,以至于任何一位牛人都无不逆天地掌握这项最基本的本领。所以,在2018年8月份,我下定决心通过刷LeetCode来锻炼这一本领——数据结构与算法。从那时起,几乎是从0起步,很多知识都不了解,基本上每刷几道题都会卡到一个完全没有遇到过的知识点,尽管到现在也会时不时地发生。但是,我一直都在坚持,并且从未放弃,累计现在已经刷了421道题目(其实不止)。你也许会问这是为什么,当然,我会在文中的后面讲到。不过,在此之前,我不得不提我是怎么计划并走过这次还未完成的刷题之旅的——到底该如何刷LeetCode?步骤频率优先 —— 因人而异的刷题顺序最开始的前两个月,... Read More

后缀数组(Suffix Array)

本文介绍后缀数组的定义与构建的过程。首先,文章介绍什么是后缀数组,随后讲解了最自然的朴素算法。为了引出更高效的算法,文章提及了倍增思想与基数排序的背景基础知识。接着,通过模拟演练的方式一步一步地演示如何创建后缀数组。将构建的抽象过程形象地展示出来,使读者更易理解。定义给定字符串,其所有后缀有。(6为字符串的长度)。如下所示S = "banana"s1 = "banana"s2 = "anana"s3 = "nana"s4 = "ana"s5 = "na"s6 = "a"后缀数组即为由构成的有序的(字典序升序排列的)字符串数组。vector<string> sa{"a", "ana", "anana", "banana", "na", "nana"};构建后缀数组的动态过程演示动画: https://visualgo.net/zh/suffixarra思路如何构建后缀数组?若字符串的长... Read More

树状数组(Binary Indexed Tree)

树状数组或二叉索引树(英语:Binary Indexed Tree),又以其发明者命名为Fenwick树。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和, 区间和。它可以以的时间得到任意前缀和,并同时支持在时间内支持动态单点值的修改。空间复杂度。摘自维基百科文章先介绍低位运算(lowbit)的基本知识,再提及如何将一个整数划分为个区间的运算过程,进而延展到如何将线性序列以树行结构进行存取,接着介绍了高级数据结构——树状数组的两个基本操作——查询前缀和与单点增加,最后介绍了树状数组的一个应用——求解逆序对数。lowbit(低位)运算定义为非负整数在二进制表示下“最低位的1及其后边所有的0”构成的数值。比如:,其二进制表示为 ,则其低位。公式如何计算一个整数中二进制表示下所有位是1的数值?比如,则其二进制表示下所有位是1的数值有:,。... Read More

《Redis深度历险》Chapter 1 Learn Note

1.7 布隆过滤器其数据结构包含一个大型的位数组和若干个不一样的无偏hash函数。所谓无偏即能够把元素的hash值计算得比较均匀,让元素被映射到位数组中的位置比较随记。输入预计元素数量:n错误率:输出位数组长度 lhash函数的最佳数量 k = 0.7 * (l / nf = 0.6185 ^ (l / n空间占用估计http://krisives.github.io/bloom-calculator误判率f = (1 - 0.5^t) * k # k 是 hash函数的最佳数量应用爬虫重复URL过滤NoSQL数据库领域,降低磁盘IO垃圾邮箱过滤1.9 漏斗限流维护漏斗属性:漏斗容量、漏嘴流水速率、漏斗剩余容量与上一次漏水时间。每次灌水(请求)前,进行计算给漏斗腾出空间。能够腾出多少空间根据时间过去了多久(上一次漏水时间)以及流水速率有关。然后,判断当前请求是否具有足够空间。如果... Read More

《DATA STRUCTRUES A Psuedocode Approach with C++》Chaper 3. Linked List Learn Note

3-1 LINEAR LIST CONCEPTLinear lists can be divided into two categories: general and restricted.In a general list, data can be inserted and deleted anywhere and there are no restrictions on the operations that can be used to process the list. Such as the random list, ordered list.In a restricted list, data can only be added or deleted at the ends of the structure and processing is restricted to op... Read More