- 1【教程】Android系统手机 菜鸟扫盲汇总
- 2uniapp 的基础_uniapp在哪看下了什么依赖
- 3【JAVA】通过JAVA实现用户界面的登录_用户登录 java设计
- 4手把手教你搭建MongoDB分片式部署集群+实战_mongodb分片集群部署
- 5python小游戏————兔子_python小兔子代码
- 6Java基础知识解析：从入门到精通_java从入门到精通
- 7最全的 Charles 抓包工具详解
- 8BAT 批处理脚本教程_bat脚本编写教程菜鸟
- 9【自然语言处理】第3部分：识别文本中的个人身份信息_pipeline("ner", grouped_entities=true)的输出是什么
- 10ESP-12F模块使用指南
数据结构与算法题目及C++解答_c++数据结构与算法第四版答案
赞
踩
前言
题目主要按照类型进行整理，包括leetcode，nowcoder等网站，对于可以使用多种方法的题目，不重复列举。推荐书籍《数据结构与算法分析--C++语言描述》第四版。
本文中所有源代码及博客中其他文章的VS源代码均在github：https://github.com/AnkangH，根据名称检索即可。
1.排序算法 SortAlgorithm
排序算法的源码见博客内排序算法的文章。
1.1.1 颜色分类
给定一个由0,1,2 三个数字组成的无序数组，每个数字的数目未知。求其排序后的数组。
因为数字有界，因此使用桶排序，使用三个桶，桶索引对应数字，桶中的计数为对应数字的出现次数。有序从桶中取出数字，即可得到有序数组。时间复杂度O(N)，空间复杂度O(N)。
Leetcode (medium) 75. 颜色分类
1.1.2 寻找两个排序数组的中位数
题目：给定两个排序数组，求其中位数。要求时间复杂度O(log(m+n))。
解析：记数组1大小m，数组2大小n，那么中位数为合并后的排序数组的最中间两个数字nums[mid1] nums[mid2]的平均值，或者最中间的那个数字nums[mid1]。使用两个指针i,j遍历每个数组，判断其数字nums1[i]和nums2[j]大小，小的作为合并后数组的当前值，用一个变量index记录合并后数组的索引。若一个数组遍历完，则遍历剩余的数组，否则比较当前值，当index=mid1和mid2时，记录两个值。暂时实现时间复杂度O（m+n）的一趟扫描算法。O(log(m+n))留待日后解决。
Leetcode (hard) 4. 寻找两个有序数组的中位数
1.1.3 字符串归一化
给定一个小写字母的字符串序列，按照字典顺序输出每个出现的字母及其出现次数。
桶排序，使用26个桶储存每个小写字母出现的次数。取出桶的顺序按照升序，即可做到字典顺序，桶不为空则说明该字母出现过，输出其次数即可。
牛客网 2019校招真题 字符串归一化
1.1.4 字符串排序
给定一个字符串，后六位为数字，输出后六位排序后的数值。
截取后6位，使用stl的sort即可。
牛客网 2019校招真题 字符串排序
1.1.5 归并两个有序数组
给定两个有序数组，顺序输出每个数字
双指针法，遍历每个数组，判断指针所指向的数字大小。
牛客网 2019校招真题 合并数组
1.1.6 合并多个排序链表
给定多个排序链表，每个链表中的节点值升序。将多个链表合并为一个链表。
使用堆排序，将所有链表头放入小顶堆中。当前节点值较小节点在堆顶，每次取堆顶构建链表，并删除堆顶，将堆顶节点的下个节点入堆。要注意堆模板没有链表结构的比较函数，需要自定义比较函数。因为没有指定空节点的比较函数，所以要在入堆时去掉所有空节点。
struct cmp//排序函数名
{
bool operator() (ListNode* a, ListNode* b) //节点类型 ListNode*
{
return a->val>b->val;//堆的大顶小顶与比较函数相反 小顶堆使用>
}
};
priority_queue<ListNode*> s;//大顶堆 以val比较大小
priority_queue<ListNode*,vector<ListNode*>,cmp>;//小顶堆
Leetcode (hard) 23. 合并K个排序链表
1.1.7 数字前后组合的最大数
给定一个数组，将数字组合成最大的数。
对于任意两个数字a和b，比较a在b前和a在b后两个数字的大小，按较大数的组合方法放置a和b的顺序。
Leetcode (medium) 179. 最大数
1.1.8 两两配对差值最小
给定一个数组，两两配对求和，使和的最大值和最小值差值最小。
即要数组中两两求和，并且每个和的差异最小。将数组排序，双指针分别从首尾（最小值和最大值）出发求和，这样将最大值最小值结合，数组中两两求和的差异最小。
牛客网 拼多多2019校招真题 两两配对差值最小
1.1.9 缺失的第一个正数
给定一个无序数组，在时间复杂度O(n)，空间复杂度O(1)的要求下找到第一个未出现的正数。
时间复杂度O(n)要求遍历，空间复杂度O(1)要求不使用额外储存空间。因此需要in-place排序，数组的正确排序为1~n，i从0开始，若i处的数字nums[i]为i+1，或nums[i]应该在的位置nums[i]-1处的数字已经是正确的nums[i]-1+1=nums[i]，或者nums[i]不在正确范围（<=0或>n）都将当前索引i+1，跳向下一个继续交换。在未满足上述三个条件之前，i保持当前值，一直交换。否则将当前位置的数字放到正确的位置上，注意要将正确位置的数字先保存，防止覆盖，直至i>=n退出。这样数组中所有i~n的数字都在数组的正确位置，那么遍历排序后的数组，第一个与索引不对应（nums[i]!=i+1）的数字即为未出现的第一个正数，否则n+1为未出现的第一个正数。
Leetcode (medium) 41. 缺失的第一个正数 c++解答
1.1.9 牛牛找工作
给定一组工作，每个工作有难度和报酬两个属性，给定一组人，每个人有能力值属性，当这个人的能力值大于工作的难度时，即可选择这个工作并获得报酬，求每个人的最大报酬。
题目的核心问题是每个工作的难度和报酬无关，即工作难度低的报酬可能更多。对于每个人都要在工作中搜素，找到能力值大于工作难度的所有工作中，报酬最大那个。如果顺序搜素所有工作，那么时间复杂度o（n*n）会超时。因此考虑，能力低的人所能获取的最大报酬一定不大于工作能力高的人，因为能力高的人其工作选择更多。因此工作按照先报酬降序，报酬相同的能力降序，同时每个人按照能力降序。这样第一个人的能力最大，在工作中搜素到的第一个工作即为其能获取的最大报酬，将这个索引作为第二个人搜素的起点。同时需要按照每个人的输入顺序输出报酬，因此需要先保存输入顺序，并使用哈希表记录每个能力所能获取的最大报酬。
2.图论
2.1深度优先搜索DFS
搜索时先对可能的情况继续执行下一步搜索，直到不满足或者到达终点，所以叫做深度优先（类比二叉树记忆，根节点出发，直到叶节点再继续下一个搜索）。通常适用于可达性问题，如从一个起点出发，是否能够到达某个条件的终点。
递归形式的dfs是for循环的变体（可以这么认为），对于多层嵌套，且层数不定的情况，使用递归来进行函数语句复用，完成函数的编写。因为是递归，所以要设定终止条件，即可以在递归中判断，不满足时退出，也可以先判断条件，满足时再进行递归。
回溯法，即dfs+剪枝，如果要找一条路径，而在中间某个节点发现走不通，那么从这个节点开始之后的所有节点的可能组合都不可行，从而将这个节点作为根节点的所有枝都剪掉，而返回到这个节点的下一个顺序搜索节点。注意递归的传值和传址，当使用传址时，所有dfs的子函数都使用同一个变量，因此退出时，需要删除本轮添加的节点；当使用传值时，每个dfs的子函数均使用其副本，即一个独立的变量，不需要删除本轮添加的节点，但是时间复杂度不佳，因为传值使用副本，需要新建一个变量。
时间复杂度和空间复杂度优化：dfs中的所有复用变量，如数组大小，矩阵行数，列数等，使用全局变量。dfs所有参数，尽量使用传址，即使用引用。
2.1.1 矩阵中的最大连通区域
二维矩阵4连通DFS
Leetcode 695.Max Area of Island https://leetcode.com/problems/max-area-of-island/description/
C++解答：https://github.com/AnkangH/LeetCode/blob/master/DFS/695.%20Max%20Area%20of%20Island.cpp
2.1.2 矩阵中元素的连通关系
该题目有两种解答，不相交集类或者dfs搜索均可。
Leetcode 547. Friend Circles https://leetcode.com/problems/friend-circles/description/
C++解答：https://github.com/AnkangH/LeetCode/blob/master/DFS/547.%20Friend%20Circles.cpp
2.1.3 矩阵中连通区域的数目
给定一个二维矩阵，0代表海洋，1代表陆地，求所有岛屿的数目。将矩阵外设为海洋。即矩阵边界上的陆地也算作岛屿。
dfs上下左右四个方向，将所有能搜索到的1修改为0，防止下次搜索时重复。遍历矩阵，当前为1即进行dfs，增加计数。
Leetcode (medium) 200. 岛屿数量
2.1.4 二叉树的路径
DFS回溯法，返回上一层时，删除该层添加的内容。如dfs的参数不使用引用，那么不需回溯， 因为每次都是将当前节点加到路径之后。
Leetcode 257. Binary Tree Paths https://leetcode.com/problems/binary-tree-paths/description/
C++解答：https://github.com/AnkangH/LeetCode/blob/master/DFS/257.%20Binary%20Tree%20Paths.cpp
2.1.5 矩阵中的路径
如果路径上某个条件不符，说明不是该路径，搜索时该路径上所有修改的变量都应该复原。牛客网与Leetcode的题目相同，只是实现方式不同，牛客网使用一维数目保存矩阵，使用char[]保存路径，leetcode使用vector<vector<>>保存矩阵，使用string保存路径。建议都做一下，熟练运用不同的数据类型。复用变量使用全局变量，不要在dfs函数中新建变量，dfs中的参数，除了基本类型（整形）等，只要是结构类变量，如vector，string尽量使用传址，即引用。优化后Leetcode 时间36ms(<85%)，空间9.8m(<99%)。
Leetcode 79. Word Search https://leetcode.com/problems/word-search/
牛客网《剑指OFFER》65.矩阵中的路径：
C++解答：https://github.com/AnkangH/LeetCode/blob/master/DFS/079.%20Word%20Search.cpp
2.1.6 矩阵中被包围元素的修改
注意不要使用回溯法，当发现不可修改时，返回将修改的变量复原。而应该将'O'分类，先处理从边界出发dfs到的所有'O',保存为'O'"X"之外的其他字符，再将内部'O'修改为'X',再将前述修改为其他字符的字符复原为'O'即可。理由：
考虑如图所示的矩阵，搜索时若顺序是O2->O1，O2->O3，那么03发现边界上的'O'之后，无法将O2处已经修改为'X'的'O'复原，因为该递归已退出，同理不能使用vector<>保存修改过的变量，因为判断是否复原的条件是dfs(up)||dfs(down)||dfs(left)||dfs(right)，为真则复原，为假则清空，那么如果在之前发现了需要修改的O，此时队列中多出很多错误的点，无法处理，也不要使用返回值，返回值只能在相邻递归（调用和被调用之间传递），而并列的递归（顺序执行的各个条件）无法使用返回值联系起来。
Leetcode (medium) 130. 被围绕的区域
2.1.7 字符串间字符排列问题
使用字符串的索引进行递归，以当前字符串每个不同字符进行dfs。使用当前字符串的副本进入下个递归程序，则不需要回溯删除本轮添加的字符，因为传递的是本轮字符串的副本，所以每个递归程序中的变量是互异的。
Leetcode 17. Letter Combinations of a Phone Number：
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
2.1.8 有重复元素的排列问题
给定n个字符组成的字符串，字符有重复，输出所有可能的排列。对字符串输入的每个字符，标记当前已读，然后dfs剩余的字符，直到长度为要求的长度。对于重复的字符，不进行dfs搜索，因为对于重复元素，无论使用那个做为第一位进行dfs，产生的序列均是相同的。剪枝不理想，时间复杂度还是较大。
Leetcode (medium) 47. 全排列 II
2.1.9 互异元素排列问题
给定n个互异元素，求所有可能的排列结果。
Leetcode (medium) 46. 全排列
2.1.10 互异元素可重复选择的组合问题
给定n个互异正数，一个正数目标值，从数组中任意（可重复选取某个数字）选取，使和为该目标值。求所有的组合方法。根据目标值与当前值的差更新dfs目标，对数组其他数字dfs。如果当前数字对数组所有元素进行dfs，会出现组合相同但是不同排列的情况，需要将重复的组合剔除。 如果使用哈希表，还需要进行数组排序和转换字符串的过程，方法一可以完成要求，但运行耗时900+ms，是很差的方法。方法二是，当前数字对数组中当前数字之后所有数字进行dfs。这样可以避免重复组合。如arr=2，3，7；target=7。如果使用方法一，会出现2 2 3；2 3 2； 3 2 2；7共四种解决方法，然而前三种是同一种组合。
Leetcode (medium) 39. 组合总和
2.1.11 有重复元素不可重复选取的组合问题
给定n个正整数，无序，可能有重复元素，任意选取（同一索引在一种组合中不可使用多次），使和为目标值，求所有组合方法。
上个题目中，我们知道，即便是互异元素，只有dfs时不是对当前元素的之后进行检索，那么组合也会重复。因而首先确定，dfs是对当前元素之后的元素遍历。再次，相同数字做为首字母出现时，遍历也可能重复，所以排序原数组，仅对重复数字第一次出现时作为首个数字进行dfs。即便做了这些限定，结果仍不尽人意。考虑 arr=2 2 1 2 5，target=5。排序后arr=1 2 2 2 5，使用上述思路的输出为1 2 2,1 2 2,1 2 2，5。数字2作为首数字确实没有输出重复组合，但是当首数字为1时，输出了arr[0] arr[1] arr[2]，arr[0] arr[1] arr[3]和arr[0] arr[2] arr[3]。只要重复数字出现的索引是连续的，说明是第一次搜索，无论选取了多少个都可以。如果当前数字arr[cur]的索引cur和dfs时的上个数字arr[pre]的索引pre不连续，即cur-pre>=2，如arr[1]和arr[3]，arr[0]和arr[2]，说明不是首次选取，此时就要进行检查，如果arr[cur-1]==arr[cur]，那么选取pre的dfs遍历结果一定是重复的。
Leetcode (medium) 40. 组合总和 II
2.1.12 互异元素集合的子集合问题
给定一个互异元素的集合，输出所有的子集。注意空集是所有集合的子集。对于每个当前元素，dfs之后的元素即可。因为子集长度不一，所以每个当前集合都保存到最后的结果。也不需要边界条件，实际上隐含的边界条件是，当index超出数组范围后，for循环不执行，因此dfs停止。
Leetcode (medium) 78. 子集
2.1.13 有重复元素集合的子集问题
注意三个点：1.输入中第一个出现的数字再做为首元素进行dfs，即输入数组排序，当前元素与上个元素不相同再作为首元素进行dfs 2.剔除重复序列的方法是 遍历的的当前索引cur如果与下个索引next不连续 即next-cur>=2，那么判断元素arr[next]和其在数组中的上个元素arr[next-1]，若相同，则本次遍历之后的所有子集均为重复子集，需要剔除。3.子集长度不定，所以所有当前遍历的子集都保存，且注意空集是任何集合的子集。
Leetcode (medium) 90. 子集 II
2.1.14 数字连续和问题
给定一个正整数sum，求所有连续正整数序列，使得序列和为sum。序列至少包含两个元素。因为至少包含两个数字，所以最大的组合为从sum/2+sum/2+1，即dfs起始数字的范围为1-sum/2。
牛客网 剑指OFFER 和为S的连续正数序列
2.1.15 N皇后问题
题目：给定一个nxn的棋盘格，要求放置n个皇后，求所以满足条件的放置方法。放置条件为，每一个皇后的行标不同，列标不同，且任意两个皇后不在同一对角线上，即上下左右和45度角方向，不能有相邻的皇后。
解答：行标递增，对列标进行判断来dfs。使用一个数组arr保存已放置的皇后，size=arr.size()，那么（i，arr[i]）i=[0，size-1]即为已放置皇后的坐标，新放置的皇后，因为行标递增，行标为size必不会与已放置的皇后冲突，那么只判断列标[0，n-1]的合法性即可。使用一个bool数组记录列表的放置情况，从而保证不同列，再对所有已放置的皇后（i，arr[i]）i=[0,size-1]和当前要放置的皇后 （size，j） j=[0,n]，要求abs(i-size)!=abs(arr[i]-j)即可保证不在同一斜线上。
Leetcode (hard) 51. N皇后
2.1.16 N皇后问题 II
同n皇后问题，但是只求放置的方法数目，不求具体路径。将上题中保存方法的数组删除，改用一个变量res记录，当满足条件的列标数目当于n时，res++。
Leetcode (hard) 52. N皇后 II
2.1.17 第k个排列(dfs问题但不适合用dfs求解)
给定一个正整数n，求数组1,2,...,n的全排列中，顺序第k个排列。注意不能使用dfs求全排列，否则一定超时。因为数组互异，所以全排列是有序的，可以根据k的大小划分范围，来确定每一位数字，即k和每个全排列有对应关系。如1234全排列的第6个元素，可以看到：
1234 1
1243 2
1324 3
1342 4
1423 5
1432 6
即，（k-1）/(n-1)!的值可以确定第一位数字的值，即str[0]=num[(k-1)/(n-1)!]。每个数字都有n位，所以使用一个for(i=1;i<=n;i++)循环来计算每一位数字，k从k-1开始。当前index=k/(n-i)!，str+=num[k/(n-1)!]，更新k=k-index*(n-1)!。
Leetcode (medium) 60. 第k个排列
2.1.18 N个互异元素的K个组合问题
给定n个互异元素1-n，以及一个数字k ，取出其中k个作为组合，求所有互异组合。回溯问题，dfs+剪枝，index作为数字的索引，当前索引放入结果暂存，当结果中的个数=k时，放入最终结果。对所有i=[index+1,n]的i进行dfs，尾回溯，删除当前轮添加的元素。
Leetcode (medium) 77. 组合
2.1.19 括号生成
给定一个正整数n，使用n个左括号和n个右括号来生成所有满足括号匹配规则的组合。
根据当前字符串中左括号和右括号的数目，dfs规则如下： 1.当前字符串数目==n*2，保存结果 2.当前字符串中左括号数目==n，即左括号已用完，下次只能放置右括号 3.当前字符串中左括号数目>右括号数目，下次可以放置左括号也可以放置右括号 4.当前字符串中左括号数目==右括号数目，下次只可以放置左括号。 为什么当前字符串中左括号不会小于右括号？ 因为这种情况不满足括号匹配规则，起始时先放入一个左括号，再对以上四种情况dfs。
Leetcode (medium) 22. 括号生成
2.1.20 格雷编码
给定一个n代表二进制位数，求一个可能的格雷编码。格雷编码要求任意相邻的数字，二进制只有一位不同。
1.公式法 g(i)=i^(i/2) 2.回溯法。 由于待选数字为2exp(n)个，规模极大，因为构建枝时，为极大降低规模，对当前数字index，求其二进制每一位不同对应的数字，这样每一层dfs中只有最多n个枝。使用数组记录着2exp(n)个数字有没有使用，只对未使用的数字进行dfs。公式法4ms，回溯法时间复杂度一定大于公式法，12ms，虽然使用回溯法解决这个问题不是最佳，但是作为dfs的练习题来说是很好的。
Leetcode (medium) 89. 格雷编码
2.1.21 二叉树根节点到叶节点的路径和
给定一棵二叉树，求从根节点到叶节点的所有路径中，和为目标值的路径。
根据case判断二叉树的节点值有正有负，所以不能提前剪枝（当前值>sum），只要当前节点有左右子节点，就对其dfs，更新和尾sum-cur->val。如果当前节点值等于sum值，且当前节点为叶节点，则把该路径放入最终结果。注意尾回溯时，不要提前退出，要保证本轮添加的节点值都能在函数末尾回删。
Leetcode (medium) 113. 路径总和 II
2.1.22 二叉树路径之和
给定一棵二叉树，节点值为0-9，从根节点出发到达叶节点的路径上每个节点为十进制数字的一位，叶节点为个位。求二叉树所有路径的数字之和。
回溯法，可以使用副本不进行回删，也可以使用引用进行回删。每次添加当前数值时，先将已有的数字升位，再把当前数字放到个位，若到达叶节点，将当前和放入总的和中即可。
Leetcode (medium) 129. 求根到叶子节点数字之和
2.1.23 组合总数III
给定1-9的数字，一个目标值n和数字个数k，要求从1-9中选取不重复的k个数字，和为n。且组合不能重复。
回溯法，对1-9作为第一个数字i开始进行dfs，dfs的范围是[i+1,9]，更新当前和sum-=i，剪枝方法是对列举的所有可能，当i>sum时，不进行dfs。尾回溯，函数尾删除本轮添加的元素。使下次开始时，组合暂存变量temp的值复原。
Leetcode (medium) 216. 组合总和 III
2.1.24 最少货物装箱问题
给定一个箱子大小n，有三种货物体积分别为3,5,7,每种货物的数目无限，若箱子能被装满，输出装满箱子使用的最少货物数目，否则输出-1。注意装箱问题不一定可以使用dfs。考虑1,5,6三种货物和体积为10的箱子，dfs优先找到61111的方案，但是最优方案为5 5。
回溯法，优先级7>5>3，并且需要提前退出，否则搜索的规模太庞大。使用全局bool变量flag，在dfs的枝中加入&&flag，因为搜索的优先级是7>5>3，所以如果箱子能被装满，那么第一个组合一定是使用箱子数目最少的，之后flag=false，这样右侧的所有还未搜索的枝就被全部剪掉了。并且剪的是根节点，而不是每一个到叶结点的路径，所以时间复杂度会大大提高。
牛客网 2019校招真题 最少数量货物的装箱问题
2.1.25 分割回文串
给定一个字符串s，将其分割为k个子串，其中每个子串均为回文串，输出所有可能的分割方案。
1.使用dp方法判断每个子串是否为回文串2.回溯法根据dp分割回文串
Leetcode (medium) 131. 分割回文串
2.1.26 根据词典拆分单词
给定一个字符串s和词典dict，如果字符串可以由词典中的单词拆分，输出所有的拆分结果。
不要直接dfs，通过res是否为空来判断是否可以拆分，而应该先使用dp方法判断能否拆分，若能拆分，再根据子串是否在词典中进行回溯拆分，否则一些不能拆分的测试用例dfs的规模太大会直接超时。
Leetcode (hard) 140. 单词拆分 II
2.1.27 扁平化列表迭代器
给定一个列表，列表中的元素可以为数字或者另一个列表，实现迭代器，返回顺序访问的每一个数字。
使用一个数组，保存顺序访问的每一个数字，如果是数字，放入数组，否则对这个列表继续访问直至数字。使用一个指针记录当前位置，使用一个变量记录总的数字个数。
Leetcode (medium) 341. 扁平化嵌套列表迭代器
2.1.28 9宫格数字键盘的字母组合
给定一个手机9宫格键盘，根据输入数字输出所有可能的字母组合。
列举当前数字代表的所有字母放入组合暂存，对下个数字代表的所有字母进行dfs。注意回溯要有两层，即删除当前添加的，删除上一层循环添加的。
Leetcode (medium) 17. 电话号码的字母组合
2.1.29 矩阵中的最长递增路径
给定一个mxn矩阵，求矩阵中的最长递增路径的长度，可以上下左右移动。
使用带备忘录的dfs，仅对满足递增和索引合法的上下左右点进行dfs。如果从某点i，j开始的最长递增路径已经求取，那么直接返回备忘录中的数值，否则对上下左右四个点进行判断，符合要求就进行dfs返回最大路径。
Leetcode (hard) 329. 矩阵中的最长递增路径 c++解答
2.1.30 分割等和子集
给定一个无序数组，判断能否将数组分为和相等的两个子集。
本题是一个典型的01背包问题，因此可以使用动态规划来解决。动态规划的时间复杂度是O(n*target)，因此时间复杂度太高。而使用dfs的时间复杂度较低。注意特殊case 100,1，1,1,1,1这种，因为1太多往往导致dfs超时。但是这种情况，数组最大元素大于sum/2，此时数组一定不能分为两个和相等的子集。
Leetcode (medium) 416. 分割等和子集 c++解答
2.2 广度优先搜索BFS
搜索时，根据节点离起点的远近划分层次，优先搜索离得近的节点，当所有离得近的节点搜索完时，再搜索下一层。可以对比二叉树的层序遍历来记忆。通常适用于最优性问题，如图论问题中，无权无向图的最小路径等。搜索问题均可通过dfs和bfs来解决，并且dfs和bfs能解决的问题同样多，但是对于可达性问题，如果使用bfs，那么会增加很多不必要的工作，同样对于最优性问题，使用dfs会增加很多不必要的工作。
最小生成树：有权无向连通图中，路径的总权重最小的生成树，使用Prim算法。
最小高度树：无权无向连通图中，某个顶点作为根节点出发，高度最小的树，使用BFS。
2.2.1 二叉树的最小深度
层序遍历，第一个发现的叶节点的深度即为最小深度。
Leetcode 111. Minimum Depth of Binary Tree
2.2.2 单词接龙的最短变换次数
单词间是无权无向图，求指定起点到终点的最小路径。
使用哈希表构造邻接表，使用辅助队列来BFS，入队列的单词都标记已读，防止重复访问。
Leetcode (medium) 127. 单词接龙
2.2.3 单词接龙最短变换路径
同2.2.2但是要求给出最短变换的每个路径。
分3步。1.预处理与构建词典的哈希表，便于查表。2.修改词典单词及起始单词的每一位构建邻接表 3.层序遍历 查找最短路径。
步骤3的注意点：1.当前层的单词c和b，如果c的子节点有b，那么跳过，因为a->c->b的路径一定大于a->b的路径。2.当前处理的单词置为已读，同时使用一个哈希表记录当前层的每个单词，一层一层的处理。只有当当前单词的邻接单词不在当前层且不在上面的层中，才可以放入队列。3.使用哈希表记录每个以当前单词结尾的路径，之前单词的路径可以不删除，因为删除之前的路径需要额外的时间。
Leetcode (hard) 126. 单词接龙 II
2.2.4 最小高度树
给定一个无权无向连通图，以任意顶点出发，求最小高度树的高度。
常规方法是以每个顶点出发，BFS构造最小高度树，记录最小高度树的深度。但是时间复杂度太高，超时。采用第二种方法，从叶节点出发，删除叶节点cur和它的枝cur->next，那么倒数第二层的节点nxt会变成叶节点，继续这个逻辑，直到最后的一个或两个节点即为最小高度树的根节点。层序从下向上遍历，因为删除了上层节点向下的枝，所以不需要记录每个节点是否已经访问过。
Leetcode (medium) 310. 最小高度树
2.2.5 课程表
给定一组课程的优先关系，如[a,b]意味着学习课程a之前需要先学习课程b。求是否存在学完所有课程的学习路线。
有向图的拓扑排序，若a->b那么a在b之前。选当前入度为0的顶点a入队列，删除a的所有边，若删除边后，b的入度为0且未读，那么b入队列。最后检查所有顶点是否均已读即可。因为顶点唯一访问，所以只需要将入度数目-1，而不需要在数组中删除该边，也不需要使用数组标记该顶点已访问。
Leetcode (medium) 207. 课程表
