LeetCode 哈希表专题

很多时候,我们都需要一个数据结构,可以快速存储一个数据,快速找回这个数据。很多时候,我们的最佳选择是哈希表。哈希表是一种很复杂的动态存储结构,在最佳情况下,它的存取,查找都是O(1)时间。根据实现不同在最差情况下则有一些不同的表现。这个专题我们不讨论哈希表的具体实现,只讨论用系统内建哈希表就可以高效解答的一些LeetCode题目。

之前的段落也曾经讲过,有些字符类的题目,256个元素的数组,可以跟哈希表起到完全类似的作用,而且效率更高,所以在这些题目里,也有可能有用数组解题的情况。但是这种情况仅仅针对字符类题目,更普适的情况下,哈希表更合适。

题目列表:

LeetCode 第71题 Simplify Path【堆栈】Java

原题地址:https://leetcode.com/problems/simplify-path

以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径

请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

继续阅读

LeetCode专题 堆栈和队列

堆栈和队列都是动态数据结构,支持删除操作。在堆栈里,删除的是最新加入的元素,最后加入的,先出去,所以叫做后进先出原则(LIFO, last in, first out)。叫做堆栈的原因就是,堆栈数据机构就像是堆叠的文件,或者一堆货品,你不把上面的,也就是后放进去的东西挪走,你就没办法去挪走下面的,也就是先放进来的东西。堆栈在显示生活中很常见,你桌子堆的一堆文件,就像是一个堆栈。

而队列的删除原则是先删除最早加入的元素,先加入的,先出去,所以叫做先进先出原则(FIFO, first in, first out)。现实生活中的种种排队其实就是队列,先到先得。

继续阅读