全排序类题目
1. 46. 全排列:给定一个 没有重复 数字的序列,返回其所有可能的全排列。
2. 47. 全排列 II:给定一个 有重复 数字的序列, 按任意顺序 返回所有不重复的全排列。
3. 面试题 08.07. 无重复字符串的排列组合:计算某字符串的所有排列组合,字符串每个字符 均不相同。
4. 面试题 08.08. 有重复字符串的排列组合:计算 有重复 字符串的所有排列组合,输出结果中不能有重复的字符串。
5. 剑指 Offer 38. 字符串的排列:虽然题干不太一样,但是代码可以直接 用上一题的。
6. 60. 排列序列:原名为第k个排序,难度较大,笔试更可能遇到。此题可以使用dfs+剪枝,推荐@liweiwei1419的题解:深度优先遍历 + 剪枝、有序数组模拟
7. 784. 字母大小写全排列:给定一个字符串S,通过将字符串S中的每个字母转变大小写获得一个新的字符串,返回所有可能得到的字符串集合。
提升:可以在本地编译环境试试将所有输出结果按 字典序排列 或者 逆字典序排列。
组合类题目
1. 17. 电话号码的字母组合:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
2. 77. 组合:给定两个整数 n 和 k,返回 1 … n 中所有可能的k个数的组合。
3. 39. 组合总和:给定一个 无重复元素 的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以 无限制重复被选取 。
4. 40. 组合总和 II:给定一个数组 candidates ( 数组中的数字可能重复)和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中 只能使用一次。
5. 216. 组合总和 III:找出所有相加之和为n的k个数的组合。组合中只允许含有1-9的正整数,并且每种组合中不存在重复的数字。
6. 377. 组合总和 Ⅳ:给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。PS:这题不用DFS,而是用动态规划,放在此处只是因为题目名字相似。
子集类题目
1. 78. 子集:给定一组 不含重复元素 的整数数组nums,返回该数组所有可能的子集(幂集)。
2. 90. 子集 II:给定一个 可能包含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。
3. 面试题 08.04. 幂集:跟上一题除了函数名不一样以外,其余代码可以一模一样。
提升:可以在本地编程环境试试将整数数组改成字符数组,并且最后的结果按任意、字典序或者逆字典序顺序排列。
单词搜索类题目
1. 79. 单词搜索:给定一个二维网格和一个单词,找出该单词是否存在于网格中。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
2. 剑指 Offer 12. 矩阵中的路径:别看此题题干好多字的样子,实际上代码和上一题一模一样,连函数名都没变。
3. 212. 单词搜索 II:个人觉得难度不适合普通面试者的面试,但是笔试时候很有可能考到。(本人遇到2-3次与此题类似的笔试题)
结束语
DFS是面试的常考题之一,大家遇到的面试官不太一样,有些面试官会提出一些创新性要求(也就是和力扣原题略有差异),所以在学有余力之余可以多试试看上述建议的提升方法,帮助自己更快掌握这个方法。
最后说一下哈,出这个系列的目的是为了帮助一些马上要面试的同学快速掌握相关知识点的。任何事物的学习都是学无止境的,有时候就算你把上述都刷了,你也可能一题都遇不到,但是这个知识点就是常考且常用的。希望大家即使不爱,也不要伤害。
本文为原创文章,转载请注明出处!