这篇主要总结通过 leetcode 平台产品学习数据结构和算法，帮助各个阶段学习者通过leetcode平台提升数据结构算法实践应用能力，内容会定期补充更新。有任何意见建议请留言。
开篇先从实践、工程、面试、工作角度，简明扼要说明一些名词概念和范围，有别理论名词概念。并罗列学习中不同阶段常见问题。清晰使用哪些有效工具和学习方向更适合自己。
动手画一画图表，可以让抽象问题逻辑层次更清晰，这个也就是计算机是一门实践性学科的原因。如果你从小很喜欢跟着爸爸家人动手做手工、整理收拾，你会发现生活中很多事务是可以对应计算机数据结构的。
名词概念
- 数据结构：接口和封装，两个函数之间的接口，或由联合数据结构组成的存储内容的访问方法封装。正确的数据结构选择可以提高算法的效率，经验显示程序设计的困难程度与最终成果的质量与表现，取决于是否选择了最适合的数据结构。
- 算法：有限步骤或次序。包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来；
- 编程语言：用来描述或执行具体数据结构和算法在计算机上；
- 方法函数：实现某种操作具体数据结构的某个或全部功能的程序函数；
- 堆栈（Stack）：又称为栈或堆叠。只允许在有序的线性资料集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。常与另一种有序的线性资料集合队列相提并论。堆栈常用一维数组或链表来实现。
- 浅拷贝：只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。
- 深拷贝：创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象；
最常用数据结构
常用数据结构名词中英对照表，建议先以英语名词为主，在翻译对应中文。避免中文后面概念近似的混淆。有些英文的名词有多种对应中文名词翻译。
- Array（数组）：几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存结构。优点存取便利，大小固定，起点或中间插入成本很高；
- 栈（Stack）：推入（压栈，将资料放入堆栈顶端，push）和弹出（弹栈，将栈顶端资料移除，pop）。常见应用内存中保存变量、方法调用。想象生活中一摞书或盘子；
- Queue（队列）：遵循先进先出（FIFO，先来先服务），前端添加，后端移除。例如生活中排队；
- Deque, double ended queue （双端队列）：允许同时从前端和后端添加和移除元素的特殊队列。常见应用存储一系列撤销操作，同时遵守了先进先出和后进先出原则，结合了队列和栈的一种数据结构；
- Linked List（链表）：链表存储有序集合，但链表元素在内存中不是连续放置的，添加或移除元素不需要移动元素，链表需要使用指针；
- Set （集合）：无序且唯一的项组成。算法包含数学中常见的集合运算；
- Map （字典、映射）：集合关注值本身，字典或映射Map用[键]=[值]存取数据。Map每个键只能有一个值。Map可以称作字典、映射、符号表或关联数据；我们经常使用字典保存对象（内存数据集合）的引用地址，例如Chrome开发者工具中的内存、快照等功能，一个字典更像生活中的地址簿；
- Hash（散列）：散列算法的作用是尽可能快地在数据结构中找到一个值；
- Hash table（散列表）：散列表是字典的一种实现，所以可以用作关联数组，也可以对数据库进行索引；
- Tree（树）：递归可以让树和图数据结构操作变得更简单。树是一种分层、非顺序数据结构，对于存储需要快速查找的数据非常有用。现实生活中最常见的例子是家谱、公司组织架构；有很多变种树的算法，需要结合应用场景学习；
- Graph（图）：图是一种非线性数据结构，图是网络结构的抽象模型，图是一组由边连接的节点或定点，学习图是重要的，因为任何二元关系都可以用图来表示；
- Heap（堆）：一种特别的完全二叉树。
- 二叉堆：非常著名的堆数据结构，它能高效、快速地找出最大值和最小值，常应用于优先队列；
- Tulpe (元组)：和 list 相似，本质也是一个数组；
- Pair：两个数据合成一个数据；
总结，对基本数据结构深刻的理解和区分，可以在后续算法学习中对应不同问题场景选用合适的数据结构解决问题；
常用数据结构拓展
- Array (fixed size)：固定长度数组
- Dynamic array：动态长度数组
- Linked list：链表
- TreeSet / TreeMap (ordered)：有序树
- HashSet / HashMap (unordered)：无序树
- Heap / Priority queue
- Deque / Queue / Stack
- Pair / Tuple
- Customize data structure
算法基本要素-设计模式
- 分治法：把一个问题分割成互相独立的多个部分分别求解的思路。
- 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
- 贪心算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
- 线性规划法：特指目标函数和约束条件皆为线性的最优化问题。
- 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
算法基本要素-实用方法
- 迭代方法与递归方法：迭代是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果，与“重复”同义。递归函数自己调用自己，递归是迭代的一个例子。
- 顺序计算、并行计算和分布式计算：顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。
- 确定性算法和非确定性算法
- 精确求解和近似求解
算法效率
教科书上的代数式可能很枯燥，那么如何看懂算法效率公式和应用？
衡量算法优劣的两个维度空间和时间。
- 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
- 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。
因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。但在工程实战中，两个很难兼得，面试要体现你的算法设计思路。例如写入功能需要IO效率性能足够好，读取需要缓存读取空间效率比较好。
时间复杂度
我们经常简单一个程序或者sql语句执行时间，这个是线性的，弊端就是在不同机器执行的时间消耗不同，数据规模、算法覆盖度都会影响执行时间结果。
因此，另一种更为科学的表示方法就出来了：「 大O符号表示法 」，即 T(n) = O(f(n)) ，这个公式的全称是：算法的渐进时间复杂度。
常见的时间复杂度量级有：
- 常数阶O(1)：无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)；
- 对数阶O(logN)：在while(i<n)循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了，因此这个代码的时间复杂度为：O(logn)。
- 线性阶O(n)：如for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度；
- 线性对数阶O(nlogN)：线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
- 平方阶O(n²)：平方阶O(n²) 就好理解，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。for循环下还有一个for循环。
- 立方阶O(n³)：参考上面的O(n²) 理解，O(n³)相当于三层n循环，其它的类似。
- K次方阶O(n^k)
- 指数阶(2^n)
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
空间复杂的
一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。
和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示，例如O(1)、O(n)、O(n²)等；其中n用来表示输入的长度，该值可以影响算法的空间复杂度。
常见问题
-
Q: 国内com、国外cn的leetcode平台产品如何选择？
A: leetcode.com是国际英文版主站，题库信息是最全的。注册leetcode.com国际主站，可以使用国际账号登录leetcode-cn.com。这样数据可以同步，同时可以接触国际最全题库，也可以了解国内中文环境信息。如果后面要出国工作，建议使用leetcode.com。 -
Q:求职北美科技公司，为什么面试要考算法题？
A:面试造火箭，工作拧螺丝钉。软件工程开发这类工作，工作没有重复性，问题没有现成的解决方案，无论工作年限多久，都需要现学，所以只能考察数据结构和算法、逻辑辩证；只要刷题刷的好，剩下的都是熟练度，所以入职工作基本没问题，减小人力招聘成本； -
Q:如何快速在 Leetcode.com 上刷题？
A:按类型(相同解法)刷题，不要按序号；先容易在难，逻辑思维渐进提高；思考5分钟没有思路，直接看答案不要花太多时间创造算法，面试主要用已有的数据结构和算法解决问题。 -
Q:使用什么语言刷题在leetcode上？
A:优先自己常用的语言，把专门语言学精通。优先数据结构丰富的编程语言，学习数据结构和使用编程语言类库提高工程实践能力。一般可以由简单到难。可以参考西面最常用数据结构在不同编程语言中比较学习。 -
Q:非计算机专业转编程，如何在LeetCode刷题。
A:首先在实际工作中，非计算机专业的程序员占比50%。不要担心转专业，而是需要动手实践，计算机是一门实践性学科。第一步选择一门自己喜欢的编程语言，第二步学习泛读数据结构，至少要知道常用几个数据结构是什么，什么场景会用这种数据结构，例如hashMap、Queue、Stack。这些基础的数据结构几乎存在所有的现代计算机软硬件中，可以结合计算机或操作系统原理学，以后也是面试的内容或谈资。第三步就是算法，排序算法、回溯算法、动态规划这些实用常见算法思想是解题或解决问题的关键。
编程语言权威语法手册参考
- Mozilla JavaScript
–TypeScript：开源的、渐进式包含类型的JavaScript超集。为JavaScript变量提供静态类型检查。 - "Can I use" provides up-to-date browser support tables for support of front-end web technologies on desktop and mobile web browsers.
- PHP Document
最常用数据结构在不同编程语言中比较学习
数据结构是解算法的基础或者思路，一般人使用学习前人已经设计好的数据结构在特定应用场景中解决问题。经验丰富的人可以创造数据结构。
这里罗列不同的语言和对应数据结构的函数或者实现方法，帮助对比记忆加深印象。
如果你是前端工程师方向，初期可以选择Javascript，ES6会支持更多数据结构类库。如果你是服务端可以选择php、golang、Java。如果你是数据工程师可以选择Python、Java。如果你是底层工具追求高性能，那么可以选择C++。如果你是全栈工程师，我想可以一起对比学习，通常会考虑团队开发快速独立交付产品的技术栈。如果你担心找不到工作，就选Java。
总之要看自己的兴趣、职业规划、项目用途。先学精一门编程语言，一通则百通。
通过下面这张表，纵轴是数据结构类型，横轴是编程语言语法描述，由简单到难边学边做自己的学习笔记，有助理解记忆和复习。可以成为后面自己刷题的小抄(Cheat sheet)。好脑不如烂笔头，工欲善事必先善其器。
| Type | C++ | Java | Python |
|---|---|---|---|
| Show Type | typeid() | getType | type(a) |
| Array | T dirs[5] | T[] dirs = new T[5] | [0]*5 |
| Dynamic Array | vector |
ArrayList |
[] |
| List | list |
LinkedList |
N/A |
| OrderedSet | set map<T1,T2> |
TreeSet TreeMap <T1, T2> |
N/A |
| OrderedMap | set map<T1,T2> |
TreeSet TreeMap <T1, T2> |
N/A |
| HashSet | unordered_set |
HashSet |
set() dict() |
| HashMap | unordered_set |
HashSet |
set() dict() |
| Heap | priority_queue |
PriorityQueue |
[] via heapq APIs |
| Queue | queue |
Queue |
collections.deque() |
| Deque | queue |
Queue |
collections.deque() |
| Stack | stack |
Stack |
[] |
| Pair | pair<T1,T2> | N/A | (x,y) |
| tuple | tuple<T1,T2,T3> | N/A | (x,y,z) |
| customized | struct/class/long | class | class/tuple |
| Array 1D | array<int,3> a{1,2,3}; vector |
int[] a=new int[]{1,2,3} | a=[1,2,3] |
| Array 1D init to x | vector vector |
int[] a=new int[n]; Array.fill(a,x); |
a=[x]*n |
| Array 2D init to x | vector<vector |
int[][] a = new int[m][n]; for(int[] row:a) Arrays.fill(row,x) |
a=[[x]*n for _ in range(m)] |
| Array 3D init to x | vector<vector<vector |
int[][][] a = new int[k][m][n]; for (int[][] mat : a) for (int[] row : mat) Arrays.fill(row,x); |
a=[[[x] *n for in range(m)] for in range(k)] |
| Dynamic Array add | vector a.push_back(x); |
List a.Add(x); |
a = [] a.append(x) |
| Dynamic Array remove last | a.pop_back(); | a.remove(a.size()-1) | del a[-1] a[:-1] # made a copy |
| Dynamic Array access | a[index]; a.back(); |
a.get(index); a.get(a.size()-1); |
a[index] a[-1] |
| Hash Table create | unordered_map<int,int> m; | Map<Integer,Integer> m=new HashMap<>(); | a=dict() |
| Hash Table instert | m[key] = value; | m.put(key,value); | a[key] = value |
| Hash Table get | value = m.at(key) value = m[key] |
value = m.get(key); value = m.getOrDefault(key,v); |
value = a[key]; |
| Hash Table contain | |||
| Hash Table iterate | |||
| Priority queue / Heap create | priority_queue priority_queue<int,vector |
Queue |
q = [] |
| Priority queue / Heap create from array | vector priority_queue q(begin(a),end(a)); |
List Queue |
q = [5,2,3,4,6] heapq.heapify(q) |
| Priority queue / Heap insert | q.push(x); | q.offer(x); | heapq.heappush(q.x) |
| Priority queue / Heap Peek | int x = q.top(); | int x = q.peek(); | x = q[0] |
| Priority queue / Heap Pop | q.pop(); | int x = q.poll(); | x = heapq.heappop(q) |
自学总结建议
选择选择一本计算机数据结构与算法，无论是什么语言实现的。按照大纲在左侧罗列数据结构对应的语言表达方式，方便你在刷题的时候参考。你还可以新增列，例如数据结构原理背景、应用场景、备注补充按照你喜欢的方式归纳总结。
希望这篇文章可以让你从计划到动手，能够理清思路，明确步骤。找到适合自己的学习方式，能清晰准确的表达自己解决计算机算法应用场景思路和方法。
相关文章
