剑指offer（专项突破版）15.4 并查集并查集是一种树形的数据结构，用来表示不相交集合的数据。并查集中的每个子集是一棵树，每个元素是某棵树中的一个节点。树中的每个节点有一个指向父节点的指针，树的根节点的指针指向它自己。并查集支持两种操作，即合并和查找。合并操作将两个子集合并成一个集合，只需要将一个子集对应的树的根节点的指针指向另一个子集对应的树的根节点。另一种操作是查找，即确定某个元素v处于哪

剑指offer（专项突破版）15.3 拓扑排序LCR113.课程排序分析将课程看成图中的节点，如果两门课程存在先修顺序那么它们在图中对应的节点之间存在一条从先修课程到后修课程的边，因此这是一个有向图。 对有向图进行拓扑排序的算法是每次找出一个入度为0的节点添加到序列中，然后删除该节点及所有以该节点为起点的边。重复这个过程，直到图为空或图中不存在入度为0的节点。 123456789101112131

剑指offer（专项突破版）15.2 图的搜索LCR105.岛屿的最大面积可以逐一扫描矩阵中的每个格子，如果遇到一个值为1的格子并且它不在之前已知的岛屿上，那么就到达了一个新的岛屿，于是搜索这个岛屿并计算它的面积。在比较所有岛屿的面积之后就可以知道最大的岛屿的面积。 广度优先广度优先搜索通常需要一个队列。先将起始节点添加到队列中。接下来每步从队列中取出一个节点进行访问。 1234567891011

剑指offer（专项突破版）14.5 背包问题LCR101.分割等和子集分析如果能够将数组中的数字分成和相等的两部分，那么数组中所有数字的和（记为sum）应该是一个偶数。也可以换一个角度来描述这个问题：能否从数组中选出若干数字，使它们的和等于sum/2（将sum/2记为t）。如果将数组中的每个数字看成物品的重量，也可以这样描述这个问题：能否选择若干物品，使它们刚好放满一个容量为

剑指offer（专项突破版）14.4 矩阵路径问题LCR098.不同路径分析可以用函数f（i，j）表示从格子的左上角坐标为（0，0）的位置出发到达坐标为（i，j）的位置的路径的数目。如果格子的大小为m×n，那么f（m-1，n-1）就是问题的解。 当i等于0时，机器人位于格子最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。因此，f（0，j）等于1，即机器人只有一种方法可以到

剑指offer（专项突破版）14.3 双序列问题LCR095.最长公共子序列分析由于输入有两个字符串，因此状态转移方程有两个参数。用函数f（i，j）表示第1个字符串中下标从0到i的子字符串（记为s1[0..i]）和第2个字符串中下标从0到j的子字符串（记为s2[0..j]）的最长公共子序列的长度。如果第1个字符串的长度是m，第2个字符串的长度是n，那么f（m-1，n-1）就是整个问题的解。 如果第

剑指offer（专项突破版）14.2 单序列问题LCR089.打家劫舍分析小偷一次只能进入一幢房屋内盗窃，因此到街道上所有房屋中盗窃需要多个步骤，每一步到一幢房屋内盗窃。由于这条街道有报警系统，因此他每到一幢房屋前都面临一个选择，考虑是不是能进去偷东西。完成一件事情需要多个步骤，并且每一步都面临多个选择，这看起来是一个适合运用回溯法的问题。但由于这个问题并没有要求列举出小偷所有满足条件的偷盗的方法

剑指offer（专项突破版）14.1 动态规划的基础知识和适合运用回溯法的问题类似，适用动态规划的问题都存在若干步骤，并且每个步骤都面临若干选择。如果题目要求列举出所有的解，那么很有可能需要用回溯法解决。如果题目是求一个问题的最优解（通常是求最大值或最小值），或者求问题的解的数目（或判断问题是否存在解），那么这个题目有可能适合运用动态规划。 分治法也是采用递归思路把大问题分解成小问题。例如，快速排

剑指offer（专项突破版）13.3 使用回溯法解决其他类型的问题LCR085.括号生成分析如果输入n，那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步，每一步生成一个括号。每一步都面临两个选项，既可能生成左括号也可能生成右括号。由此来看，这个问题很适合采用回溯法解决。 在生成括号组合时需要注意每一步都要满足限制条件。第1个限制条件是左括号或右括号的数目不能超过n个。第2

这是摘要，会在输入密码前显示