2020届秋招基本上结束，2021届的同学已经开始进入实习/秋招备战状态。之前按照模块给大家分享过 20 多篇关于后端开发的文章：

来啦！2020届秋招精选文章合集！

今天主要给大家分享一些我在整个秋招过程中总结的面试中常考的算法题。这些题目都是我看剑指Offer、LeetCode、左神算法、面试、笔试、面经时总结下来的。

说明（个人见解）

一、标注说明

黑色加粗字体题目：必须掌握，熟练写出 code；

橘黄色字体题目：一般此类都是算法不容易实现，但是需要掌握思想，面试加分。

二、刷题顺序

1、了解基本的数据结构与算法的知识：

常用的数据结构：数组、链表、栈、队列、哈希表、树、图等的基本概念和实现；

常用的算法：DFS / BFS、最短路径算法（Dijkstra）、贪心算法、动态规划、蓄水池算法、Manacher 算法等；

常用的编程技巧：递归：递归非常重要，要认真理解递归的过程；

2、剑指Offer：

《剑指Offer》非常重要，可以看各大公司的面经，很多手撕代码都出自于《剑指Offer》，所以多刷几遍，每一题都务必能快速的手写出来。

3、LeetCode：

《剑指Offer》刷完了，可以先刷 LeetCode 的 Top100，当然你也可以根据自身的情况，刷自己薄弱的专题。大部分公司的笔试题都是出自于 LeetCode，原题或者改编，重要性就不用多说了。

4、左神算法班：

这个因人而异了，如果你对算法题比较敏感，这个阶段是可以跳过的。但是如果对算法不是很有信心或者准备的比较晚，还是比较推荐左神的算法班，分为初级和高级，会串讲基本的数据结构和对应的题目。

5、最后：

算法的重要性：得算法者得 Offer。大公司非常看重算法，即便内推，但是面试环节几乎都会手撕代码，如果这个环节出了问题，会大打折扣。

刷题指南

说明：本文一共列出了 125 道经典的面试手写算法题目，为了文章篇幅不过长，题目链接和具体代码就没有贴出，直接百度题目，肯定可以搜到。这些题目的代码详解都记录在了我的博客里：

https://blog.csdn.net/pcwl1206/article/details/97390314

1. 数组

  1. 找出数组中出现次数大于数组长度一半和 N / K 的数
  2. 数组的奇偶位置问题：给定一个整型数组，请在原地调整这个数组，保证要么偶数位置上都是偶数，或者奇数位置上都是奇数
  3. 调整数组顺序使奇数位于偶数前面
  4. 数组的度
  5. 求一个数组中的第 k 小 / 大的数
  6. 将一个整数数组划分为 K 个相等的子集问题
  7. 旋转数组中的最小数字
  8. 在二维数组中查找一个数
  9. 找出数组中重复的数字
  10. 找出数组中只出现一次的那个数，其他都出现两次

11-15 题都是子数组问题：在条件下，每一个位置的元素都会作为子数组的开头或者结尾元素，那么遍历完整个数组，结果一定在其中：

  1. 子数组最大累乘积：给定一个 double 类型的数组 arr，其中的元素可正、可负、可 0，返回子数组累乘的最大乘积
  2. 需要排序的最短子数组长度
  3. 最长的可整合子数组的长度
  4. 最短无序连续子数组
  5. 连续子数组的最大和

2. 字符串

  1. 字符串的排列与组合
  2. 最长回文子串
  3. 正则表达式匹配：实现一个函数用来匹配包括'.'和'*'的正则表达式
  4. 替换空格
  5. 字符串的翻转和旋转及其应用
  6. 字符串解码
  7. 无重复字符的最长子串
  8. 字符串的最长公共子串和最长公共子序列
  9. 请实现一个函数用来判断字符串是否表示数值
  10. 判断一个字符串是否是一个合法的 IPV4

3. 哈希表

  1. 手写一个简单的 HashMap
  2. 和为 K 的子数组：给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数
  3. 一种接收消息并按顺序打印的结构设计：单链表 + 两个HashMap
  4. 哈希表增加 setAll 功能

4. 栈

  1. 用固定大小的数组实现栈
  2. 如何仅用队列实现栈
  3. 最小值栈：能够返回栈中最小元素的栈
  4. 栈的压入、弹出序列：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序

5-8题是单调栈结构问题：

  1. 单调栈结构的实现
  2. 直方图中的最大矩形面积
  3. 求最大子矩阵的大小
  4. 可见山峰问题

5. 队列

  1. 用固定大小的数组实现队列
  2. 如何仅用栈结构实现队列

6. 链表

  1. 反转单向链表
  2. 反转双向链表
  3. K 个一组翻转链表
  4. 合并两个排序的链表
  5. 链表中倒数第 K 个节点
  6. O(1) 时间内删除一个节点
  7. 删除链表中重复的节点
  8. 从尾到头打印链表
  9. 判断一个链表是否为回文结构
  10. 给出两个有序链表的头结点，打印出两个链表中相同的元素
  11. 将单向链表按某值划分成左边小、中间相等、右边大的形式
  12. 复制含有随机指针节点的链表
  13. 两个单链表相交的一系列问题
  14. 链表中环的入口节点
  15. 复杂链表的复制

7. 树

1-5 是二叉树的遍历：

  1. 二叉树的前序、中序、后序遍历的递归实现
  2. 二叉树的前序、中序、后序遍历的非递归实现
  3. 二叉树的层序遍历
  4. Morris 遍历二叉树：前序、中序、后序【二叉树的最优遍历：时间复杂度 O(N)、额外空间复杂度 O(1)】
  5. 输入一个数组，判断是不是二叉搜索树的后序遍历序列

6-7题 是二叉树的序列化与反序列化：

  1. 二叉树的序列化：前序、层序
  2. 反序列化：怎么序列化的就怎么反序列化
  3. 在二叉树中找一个节点的后继节点
  4. 判断一棵树是否是完全二叉树
  5. 判断一棵树是否是搜索二叉树
  6. 判断一棵树是否是平衡二叉树
  7. 判断一棵树是否是对称的二叉树
  8. 二叉树的镜像
  9. 树的子结构：输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构
  10. 合并二叉树
  11. 二叉树中和为某一值的路径
  12. 重建二叉树：输入某二叉树的前序遍历和中序遍历的结果，请重新构造出该二叉树
  13. 求一棵完全二叉树的节点个数，时间复杂度低于O(N)
  14. 找二叉树左下角的值
  15. 把二叉搜索树转换为累加树

21-24题是二叉树信息收集问题：

  1. 舞会的最大活跃度
  2. 求一棵二叉树中最大二叉搜索子树的节点个数
  3. 求一个二叉树的最远距离
  4. 二叉树的最大路径和

8. 图

  1. 深度优先搜索
  2. 广度优先搜索
  3. 拓扑排序

9. 数字与位运算

  1. 两数之和、三数之和
  2. 大数问题：大数相加和大数相乘问题 + Karatsuba 算法
  3. 打印从 1 到最大的 n 位数
  4. 数值的整数次方
  5. 二进制中 1 的个数

10. 排序的应用

  • 快排的应用：

  1. 求一个数组中的第 K 小 / 大的数
  2. 最小的 K 个数

  • 归并排序的应用：

  1. 求一个数组中的逆序对数问题
  2. 小和问题：把数组中每一个数左边比当前数小的累加起来，叫着这个数组的小和

11. 矩阵问题

  1. 顺时针打印矩阵
  2. 将一个正方形旋转 90 度
  3. 之字型打印矩阵
  4. 在一个行和列都有序的 m 行 n 列的矩阵中查找一个数是否存在

12. 递归

  1. 求 n! 的结果
  2. 汉诺塔问题
  3. 打印一个字符串的全部子序列，包括空字符串
  4. 打印一个字符串的全排列
  5. 母牛问题：母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求 N 年后，母牛的数量
  6. 机器人走路问题
  7. 给定一个数字组成的字符串，返回有多少种合法的 IPV4 组合

13. 动态规划

  1. 机器人走路问题
  2. 给定一个数字组成的字符串，返回有多少种合法的 IPV4 组合
  3. 矩阵最小路径问题：二维数组从左上角走到右下角的最短距离
  4. 剪绳子：剪成 m 段，最大乘积问题
  5. 数组中任意数累加得到目标值

14. 贪心算法

  1. 按最低字典序拼接字符串
  2. 切分金条总代价最小
  3. 最多做 K 个项目的最大利润
  4. 安排最多的宣讲场次

15. 回溯算法

  1. 机器人的运动范围

16. 经典结构

  1. 单调栈结构[见上文]

2-4 题是滑动窗口结构:

  1. 滑动窗口结构的实现
  2. 生成窗口最大值数组
  3. 求一个数组中最大值减去最小值小于或等于 num 的子数组数量（要求O(N)）

17.经典算法

  1. 蓄水池算法：解决等概率问题
  2. Manacher 算法：解决回文串问题
  3. KMP 算法：解决字符串匹配问题：时间复杂度为：O(N + M)，空间复杂度为：O(M)
  4. BRPRT 算法：解决第 k 大数问题：选择中位数组的中位数作为 partition 的基准，时间复杂度 O(N)
  5. 单例模式：懒汉+恶汉+静态内部类+双重校验锁
  6. 生产者消费者模式：wait/notify 、BlockingQueue 实现
  7. 多个线程交替打印：锁、信号量 Semaphore 实现

18. 剑指 Offer

《剑指Offer》中不容易分类的题目，在这里单独列出：

第36题：二叉搜索树与双向链表：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

第41题：数据流中的中位数：两个堆实现：最大堆和最小堆

19. LeetCode

LeetCode 的 Top100 必须好好刷一刷，主要用于笔试。后续文章会给大家推荐一些 LeetCode 的刷题指南。 


个人简介：
浙江大学研三在读，2020届秋招拿到腾讯、百度、字节跳动、拼多多等公司后端开发岗offer，在牛客上新开了个博客，主要分享我的秋招复习笔记、面经、面试心得等等。
 
个人文章主要发布在以下几个平台：
1、牛客网博客（震哥聊校招）：https://blog.nowcoder.net/xiaozhao
2、CSDN：https://blog.csdn.net/pcwl1206
3、知乎：https://www.zhihu.com/people/ma-nong-qiu-zhi-xiao-zhu-shou
4、掘金：https://juejin.im/user/5e01814e6fb9a0160a313fec
5、公众号：码农求职小助手
6、个人微信：pcwl_Java

觉得对你有用，点个赞吧~