算法|刷了三个月leetcode算法，顺利拿下百度、阿里等大厂的offer

文章图片

文章图片

前言随着互联网寒潮的到来越来越多的互联网公司提高了面试的难度，其中之一就是加大了面试当中手撕算法题的比例。这里说的算法题不是深度学习，机器学习这类的算法，而是排序，广度优先，动态规划这类既考核数据结构也考核编程能力的题目。刷题的网址非常的多，其中以leetcode是最为出名的。
在刷题上，我花了大量的时间，蹚了许多的坑，总结了一下，主要有这三个问题:

刷过的题老是忘，第二次刷的时候还是不会做
刷题的速度很慢，即使花一天时间，也常常只能刷五六道
坚持不下来，老是刷到一半就停滞下来了，当我第二次再来刷的时候，前面刷过的题都又忘的差不多

说出来都是泪，感觉刷题这个路是真的难走，花了很多时间，但是感觉没有什么收获。所以最近我一直在反思自己刷题的方法，希望能够提高刷题的效率和速度。当我总结了以下方法以后，我很明显的感受到自己的刷题速度从以前周末的一天五六道提升到周末一天刷十五六道以上，速度相比以前提升的非常明显。
本文采用Java语言来进行描述，帮大家好好梳理一下数据结构与算法，在工作和面试中用的上。亦即总结常见的的数据结构，以及在Java中相应的实现方法，务求理论与实践一步总结到位。
常用数据结构

数组
数组是相同数据类型的元素按一定顺序排列的集合，是一块连续的内存空间。数组的优点是：get和set操作时间上都是O(1)的；缺点是：add和remove操作时间上都是O(N)的。
Java中， Array就是数组，此外， ArrayList使用了数组Array作为其实现基础它和一般的Array相比，最大的好处是，我们在添加元素时不必考虑越界，元素超出数组容量时，它会自动扩张保证容量。
Vector和ArrayList相比，主要差别就在于多了一个线程安全性，但是效率比较低下。如今java.util.concurrent包提供了许多线程安全的集合类（比如 LinkedBlockingQueue），所以不必再使用Vector了。
链表
链表是一种非连续、非顺序的结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，链表由一系列结点组成。链表的优点是：add和remove操作时间上都是O(1)的；缺点是：get和set操作时间上都是O(N)的，而且需要额外的空间存储指向其他数据地址的项。
查找操作对于未排序的数组和链表时间上都是O(N) 。
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，亦即所谓的先进先出（FIFO）。
Java中， LinkedList实现了Deque ，可以做为双向队列（自然也可以用作单向队列）。另外PriorityQueue实现了带优先级的队列，亦即队列的每一个元素都有优先级，且元素按照优先级排序。
栈
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。它体现了后进先出（LIFO）的特点。
Java中， Stack实现了这种特性，但是Stack也继承了Vector ，所以具有线程安全线和效率低下两个特性，最新的JDK8中，推荐用Deque来实现栈。