分享｜2021秋招算法总结1-DFS篇

鲂

60820

2020.12.14

2021.08.09

发布于未知归属地

数据结构与算法 DFS 面经我要上推荐技术交流

置顶科普

年份是毕业年份，2021是指2021年毕业，不是2021年面试

鲂的2021秋招算法总结目录（已完结）

1. 分享｜2021秋招算法总结1-DFS篇
2. 分享｜2021秋招算法总结2-BFS篇
3. 分享｜2021秋招算法总结3-链表篇
4. 分享｜2021秋招算法总结4-二叉树篇
5. 分享｜2021秋招算法总结5-排序算法篇
6. 分享｜2021秋招算法总结6-字符串篇

鲂的2021秋招经验总结（不定时更新）

1. 分享｜2021届毕业生秋招经验总结1-岗位类别介绍
2. 分享｜2021届毕业生秋招经验总结2-如何选择offer

鲂的面经整理目录（已完结）

1. 美团金融｜安卓客户端｜面经｜offer｜2021届秋招｜
2. 拼多多｜客户端开发｜面经｜offer｜2021届秋招｜
3. 网易云音乐｜安卓客户端｜面经｜offer｜2021届秋招｜
4. 阿里巴巴｜客户端开发｜面经｜2021届秋招｜
5. 花旗银行｜软件工程师｜面经｜offer｜2021届秋招｜
6. 字节跳动｜客户端开发｜面经｜2021届秋招｜
7. 叠纸游戏｜客户端开发｜面经｜2021届秋招｜
8. 腾讯｜客户端开发｜面经｜2021届秋招｜
9. 360｜安卓客户端｜面经｜offer｜2021届秋招｜
10. 作业帮｜IOS客户端｜面经｜2021届秋招｜
11. 滴滴｜安卓客户端｜面经｜2021届秋招｜
12. 百度｜IOS客户端｜面经｜2021届秋招｜
13. 快手｜客户端开发｜面经｜2021届秋招｜
14. 顺丰科技｜安卓客户端｜面经｜offer｜2021届秋招｜

鲂的内推

1. 内推+校招秋招｜美团金融服务平台｜多项岗位｜北京+上海

前言

本系列总结目的性较强，针对面试的成分居多，其中 年份2021是毕业时间。如果想深入学习不同的算法，可能还需要其他努力。看此系列总结前，需要各位读者明确自己的刷题目的是否与以下情况相匹配。
1. 此前从未系统刷过算法题目，只为了找个好工作才准备开始刷题。
2. 此前刷过部分题目，但是刷了就忘，想看一些别人总结的题目。
3. 看过我整理的算法笔记【鲂的算法笔记0918版本】，因为笔记太多不知道哪些是重点。笔记中涉及题解截图的部分均放上了原题解的链接。

面试遇到的算法题因人而异，有些比较卷的岗位需要面试者掌握大部分简单中等和少部分困难的题目。普通岗位会根据面试者的情况来出题，如果面试者简历上没有算法竞赛的相关经验，刚开始出的题目会以简单和中等为主，如果这个人能力比较强（较快写出代码），面试官会多出几题，但是面试遇到的题目都会 以简单和中等为主，就算有难题也是 高频的难题。如果有算法竞赛相关经验，面试题要看面试官的心情了，不过这种大佬应该不需要看这个系列的文章。

本系列的所有题目均来源于 个人2020年参加秋招以来刷过的题目，其中的 提升和变型 可能是本人及其朋友遇到并探讨过的话题，不保证每个人刷完本系列题目以后可以遇到一模一样的题目，毕竟我又不是出企业题库的人。

关于整理顺序纯粹是看我每周的心情和时间，大家可以先从排序、链表和树开始刷，某些大厂超爱考这三个呢。

本系列文章或许牵涉到某些人的利益而导致某些人不敢评论只敢点踩本系列文章。

本人统一申明：其实点赞或者踩多少并不妨碍我的利益，我还是会把我的笔记整理完给大家 免费观看，我也不会将我秋招写的所有内容出版（不要再来找我了）。我这个系列文章都是一些刷题链接和个人感悟，你觉得你有需要你就看下去，没需要就不用看。

本篇概要

本篇主要讲述一些可以利用DFS（深度优先搜素）算法的常见面试题目及其提升方法（提升就是面试有可能出的变型）。刷题方法：同类题目一起刷，学习每种题目的解题思路。做题的策略是因人而异的，以下分几种情况给予对应的建议。

如果你看到下分的题目类型都很茫然，那么先挑前面的题目进行训练，如果超过十分钟没有自己的思路，可以直接去看题解。此处的题解 推荐官方题解 或者 高赞高阅读量 的题解（特别是标注为精选的题解）。如果编程语言是用java，建议看@liweiwei1419的题解中的基础解释和思维导图。其他语言的可以使用力扣中 按语言搜索 的功能。如果比较小众的编程语言，可以先看大众编程语言的思路，再尝试自己翻译（ 评论区 可能有翻译成其他语言的代码，大家可以多留意下）
如果你已经练习了列表中的某些题目，可以尝试开启一个新的题目，先揣摩题目意思，对比本题和之前的题目有什么区别，再尝试自己写代码。如果不成功的话，再 用上一点的方法 找 高质量原创 题解进行学习，如有任何问题也可以先看看评论区有没类似问题，没有的话可以在评论区中直接给原作者留言（可能会收获原作者或者路过的码友的关怀）。
如果都做过以下的题目，并且对分类有自己的看法，可以在本篇的评论区说出自己的看法。分类这个东西都是 因人而异 的， 以下仅代表个人观点 ，大家可以多交流下不同看法，但是 希望不要纯杠 。

全排序类题目

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是面试的常考题之一，大家遇到的面试官不太一样，有些面试官会提出一些创新性要求（也就是和力扣原题略有差异），所以在学有余力之余可以多试试看上述建议的提升方法，帮助自己更快掌握这个方法。
最后说一下哈，出这个系列的目的是为了帮助一些马上要面试的同学快速掌握相关知识点的。任何事物的学习都是学无止境的，有时候就算你把上述都刷了，你也可能一题都遇不到，但是这个知识点就是常考且常用的。希望大家即使不爱，也不要伤害。