算法与数据结构面试通关经验总结：leetCode刷题经验
Author：zhoulujun Date：
大部分开发岗位工作中都是基于现成的开发框架做事，不怎么会碰到底层数据结构和算法相关的问题，但另一个事实是，只要你想找技术相关的岗位，数据结构和算法的考察是绕不开的，因为这块知识点是公认的程序员基本功。
学算法，算法导论是不是好书？是。但对大多数人求职找工作有没有用？没啥用，性价比太低了。
什么性价比高？直接刷LeetCode。但是，到了面试时刻，题海战术对于零时抱佛脚的我，肯定挂！所以用 框架性思维去应战
如果你掌握了框架思维，现在随便给你一道题目，那你就可以按照固定的思维步骤进行思考：
这题让我们干什么？奥，让我们操作字符串。字符串本质就是个数组，所以这题考察的大概是数组相关的算法技巧。
数组有什么算法技巧？你心里有数，无非就是 二分查找、快慢指针、左右指针、滑动窗口、前缀和数组、差分数组，主要就这些。
二分查找的适用场景是什么？差分数组的适用场景是什么？你挨个想一遍，这个不行换那个，总能试出来个相对靠谱的吧？
如果你知道滑动窗口的代码框架，所以你是先把框架写出来，然后往框架里面填充代码。
扣评论区里面某些大佬的精彩解法吸引，但是我想说，在培养出自己的框架思维之前，这些方法你可以看看，但不要执迷。
算法刷题指南
以我的刷题经验，初学者最好从「树」相关的问题开始练习递归思维，然后开始系统系了解各类算法的基本原理
先学习像数组、链表这种基本数据结构的常用算法，比如单链表翻转，前缀和数组，二分搜索等。
学会常用算法之后，不要急着上来就刷回溯算法、动态规划这类笔试常考题，而应该先刷二叉树，因为二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。
至于理论方面的学习，可以看我的 “讲透学烂二叉树”
刷玩二叉树，再去做什么回溯动规分治专题，你就会发现只要涉及递归的问题，都是树的问题。
比如动态规划详解说过凑零钱问题，暴力解法就是遍历一棵 N 叉树，回溯算法就是个 N 叉树的前后序遍历问题，排列组合问题抽象成一棵多叉树结构，然后用回溯算法去暴力穷举……
数据结构是工具，算法是通过合适的工具解决特定问题的方法。
也就是说，学习算法之前，最起码得了解那些常用的数据结构，了解它们的特性和缺陷。
数据结构的存储方式
数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。
数组由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
散列表、栈、队列、堆、树、图等等各种数据结构都属于「上层建筑」，而数组和链表才是「结构基础」。
比如说「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。
用数组实现，就要处理扩容缩容的问题；
用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。
看下《再谈js数据类型与对象数据结构底层实现原理-object array map set 》与《再谈Java数据结构—分析底层实现与应用注意事项》的图：
有这些多样化的数据结构，究其源头，都是在链表或者数组上的特殊操作，API 不同而已。
「图」的两种表示方法，
邻接表就是链表：邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。
邻接矩阵就是二维数组：邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。
「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
「树」
用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；
用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。
了解 Redis 数据库的朋友可能也知道，Redis 提供列表、字符串、集合等等几种常用数据结构，但是对于每种数据结构，底层的存储方式都至少有两种，以便于根据存储数据的实际情况使用合适的存储方式。
数据结构的基本操作
对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。
数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。话说这不就是数据结构的使命么？
如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：
线性的：线性就是 for/while 迭代为代表
非线性的：非线性就是递归为代表
数组遍历框架
典型的线性迭代结构：
for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
}链表遍历框架
兼具迭代和递归结构：二叉树遍历框架，典型的非线性递归遍历结构
/* 基本的二叉树节点 */
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
var traverse = function(root) {
if (root === null) return;
traverse(root.left);
traverse(root.right);
};你看二叉树的递归遍历方式和链表的递归遍历方式，相似不？再看看二叉树结构和单链表结构，相似不？如果再多几条叉，N 叉树你会不会遍历？
二叉树框架可以扩展为 N 叉树的遍历框架：
/* 基本的 N 叉树节点 */
var TreeNode = function(val, children) {
this.val = val;
this.children = children;
};
// 遍历 N 叉树
var traverse = function(root) {
for (var i = 0; i < root.children.length; i++) {
traverse(root.children[i]);
}
};N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。
你说图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了，经典题：《岛屿算法（求岛屿数量与岛屿面积）》
算法的本质
如果要让我一句话总结，我想说算法的本质就是「穷举」。
比如，密码学算法、机器学习算法，它们的本质确实不是穷举，而是数学原理的编程实现，所以这类算法的本质是数学，不在我们所探讨的「数据结构和算法」的范畴之内。
「算法工程师」做的这个「算法」，和「数据结构与算法」中的这个「算法」完全是两码事
对前者来说，重点在数学建模和调参经验，计算机真就只是拿来做计算的工具而已；
后者的重点是计算机思维，需要你能够站在计算机的视角，抽象、化简实际问题，然后用合理的数据结构去解决问题。
不妨称算法工程师研究的算法为「数学算法」，称刷题面试的算法为「计算机算法」，我写的内容主要聚焦的是「计算机算法」。
大部分人的目标是通过算法笔试，找一份开发岗位的工作，所以你真的不需要有多少数学基础，只要学会用计算机思维解决问题就够了。
其实计算机思维也没什么高端的，你想想计算机的特点是啥？不就是快嘛，你的脑回路一秒只能转一圈，人家 CPU 转几万圈无压力。所以计算机解决问题的方式大道至简，就是穷举。
穷举有两个关键难点：无遗漏、无冗余。
遗漏，会直接导致答案出错
冗余，会拖慢算法的运行速度。
当你看到一道算法题，可以从这两个维度去思考：
如何穷举？即无遗漏地穷举所有可能解。
如何聪明地穷举？即避免所有冗余的计算，消耗尽可能少的资源求出答案。
不同类型的题目，难点是不同的，有的题目难在「如何穷举」，有的题目难在「如何聪明地穷举」。
什么算法的难点在「如何穷举」呢？一般是递归类问题，最典型的就是动态规划系列问题。
什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。
比如后文 Union Find 并查集算法详解 告诉你一种高效计算连通分量的技巧，理论上说，想判断两个节点是否连通，我用 DFS/BFS 暴力搜索（穷举）肯定可以做到，但人家 Union Find 算法硬是用数组模拟树结构，给你把连通性相关的操作复杂度给干到 O(1) 了。
比如贪心算法技巧，后文 当老司机学会贪心算法 就告诉你，所谓贪心算法就是在题目中发现一些规律（专业点叫贪心选择性质），使得你不用完整穷举所有解就可以得出答案。
比如大名鼎鼎的 KMP 算法，你写个字符串暴力匹配算法很容易，但你发明个 KMP 算法试试？KMP 算法的本质是聪明地缓存并复用一些信息，减少了冗余计算，前文 KMP 字符匹配算法 就是使用状态机的思路实现的 KMP 算法。
数组/单链表系列算法
单链表常考的技巧就是双指针，后文 单链表六大技巧 全给你总结好了
比如判断单链表是否成环，拍脑袋的暴力解是什么？就是用一个 HashSet 之类的数据结构来缓存走过的节点，遇到重复的就说明有环对吧。但我们用快慢指针可以避免使用额外的空间，这就是聪明地穷举嘛。
算法题分类
LeetCode算法按照类型分类，常见的算法类型包括：
递归和回溯
深度优先搜索（DFS）和广度优先搜索（BFS）
双指针
动态规划
贪心算法
二分搜索
排序算法
并查集
分治算法
位运算
以下是针对每种算法或概念进行的简易介绍，以及面试中可能用到的思路提示。
递归和回溯
递归是函数调用自身的过程，它可以用来解决可以分解为相似子问题的问题，比如树的遍历、汉诺塔等。递归解决问题时要注意定义清楚终止条件和递归表达式。
回溯算法是一种通过递归来遍历搜索解的算法，它试图分步去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答时，它将取消上一步甚至是上几步的计算，再通过其他可能的分步解答再次尝试寻找问题的答案。
面试思路：
明确每次递归的参数和返回值是什么，递归的终止条件是什么，以及在每一层递归中应该做什么。
对于回溯，注意如何撤销上一步的操作。
深度优先搜索（DFS）和广度优先搜索（BFS）
DFS使用栈（实际递归就是隐式栈）来实现，主要用于寻找可能的解的空间，适用于目标明确，解的结构树不宽。
BFS使用队列来实现，层层推进，逐个访问所有可能的状态，适用于最短路径问题。
面试思路：识别问题是不是搜索问题，考虑使用DFS或BFS。
DFS适用于需要访问每个节点，找所有可能解的问题。
BFS适用于找最短路径或是与距离相关的问题。
双指针
双指针主要用于对有序数组进行扫描，通过一个头指针和一个尾指针在一个循环中完成两个变量的移动，达到降低时间复杂度的目的。
面试思路：识别是否为有序数组或链表问题，考虑是否可以通过前后指针减少不必要的遍历。
动态规划
动态规划主要思想是将复杂问题分解成小问题来逐个击破，核心是找到状态转移方程。很多问题如最短路径、最长公共子序列等都可以用动态规划解决。
面试思路：寻找问题中的最优子结构，明确状态、选择以及状态转移方程。
贪心算法
贪心算法在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
面试思路：评估问题是否每一步最优选择可以得到全局最优解，注意不能回退。
二分搜索
二分搜索针对已排序的数据集合，每次通过将搜索范围缩小一半的方式来查找目标值，大大减少查找时间。
面试思路：确认数据是否有序，明确二分搜索的左右界及更新规则。
排序算法
排序算法有多种，包括快速排序、归并排序、冒泡排序等。重点理解每种排序算法的原理、时间复杂度和空间复杂度。
面试思路：根据问题的数据规模选择合适的排序算法。
并查集
并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。
面试思路：识别问题是否涉及组团、配对或网络连通性等。
分治算法
分治算法是一种处理问题的策略，通过将大问题分解为小问题逐个击破。
面试思路：识别问题是否可以分解为独立子问题，考虑如何分、如何治。
位运算
位运算包含与、或、非、异或等操作，能高效处理整数的二进制表示。
面试思路：识别问题是否涉及到整数的二进制形式，考虑是否可以通过位运算简化计算。
转载本站文章《算法与数据结构面试通关经验总结：leetCode刷题经验》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9069.html