这70道算法题你都会的话，可以直接去字节跳动了！

女爷i 2022-12-29 01:38 150阅读 0赞

## 前言 ##

> 知识的广度来自知识的深度，学习如果不成体系那是多可怕的一件事儿，希望我们在未来的学习道路上坚守初心，不要给自己留下遗憾，以自己喜欢的方式生活，做自己喜欢做的事，做一个独一无二的自己！

1.说一下什么是二分法？使用二分法时需要注意什么？如何用代码实现？

2.什么是斐波那契数列？用代码如何实现？

3.有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

4.什么是冒泡排序？用代码如何实现？

5.什么是选择排序？用代码如何实现？

6.什么是插入排序？用代码如何实现？

7.什么是快速排序？用代码如何实现？

8.什么是堆排序？用代码如何实现？

9.字符串循环左移

## 字符串 ##

1.字符串的全排列

2.KMP算法

3.DFA和NFA

4.KMP应用：PowerString问题

5.求字符串的最长回文子串

6.Manacher算法和BM算法

## 数组 ##

1.寻找和为定值的两个数

3.Hash函数

4.分支限界法

5.荷兰国旗问题：现有红、白、蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。  
![20201218174350725.png][]  
6.完美洗牌算法

## 树 ##

1.二叉查找树

2.二叉树的遍历

3.平衡二叉树

4.平衡二叉树

4.树和B树

5.N 叉树

6.红黑树

**常问的树面试问题：**

1.找到一个二叉树的高度

2.找到一个二叉搜索树中第 k 个最大值

3.找到距离根部“k”个距离的节点

4.找到一个二叉树中给定节点的祖先（ancestors）

**字典树**

**常见的字典树面试问题：**

1.计算字典树中的总字数

2.打印存储在字典树中的所有单词

3.使用字典树对数组的元素进行排序

4.使用字典树从字典中形成单词

5.构建一个T9字典

## 链表、栈与递归 ##

1.链表、栈与递归：链表相加

2.链表的部分翻转

3.链表划分

4.排序链表中去重

5.由LCA引出指针和递归问题

6.单链公共结点问题

7.括号匹配

8.最长括号匹配

9.逆波兰表达式RPN

10.直方图矩形面积：给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1；试找出直方图中最大的矩形面积。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3_size_16_color_FFFFFF_t_70][]另一个直方图例题：收集雨水问题：给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1。若使用这样形状的容器收集雨水，可以盛多少水量

**下面是几种类型的链表：**

1.单链表（单向）

2.双链表（双向）

**链表的基本操作：**

1.InsertAtEnd —— 在链表末尾插入指定元素

2.InsertAtHead —— 在链表头部插入指定元素

3.Delete —— 从链表中删除指定元素

4.DeleteAtHead —— 删除链表的第一个元素

5.Search —— 返回链表中的指定元素

6.isEmpty —— 如果链表为空，返回 true

**常问的链表面试问题：**

1.翻转列表

2.检测链表中的循环

3.返回链表中倒数第 n 个节点

4.移除链表中的重复值

## 图论 ##

1.图的遍历和搜索-广度优先遍历BFS

2.单词变换问题

3.图的遍历和搜索-深度优先搜索DFS

4.八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种解法  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3_size_16_color_FFFFFF_t_70 1][]  
5.LCA-Tarjan算法

6.最短路径SPF

7.Floyd算法

8.带负权的最短路径Bellman-ford算法

9.最小生成树MST

10.拓扑排序

**图的类型：**

1.无向图

2.有向图

**在编程语言中，图可以表示为两种形式：**

1.邻接矩阵

2.邻接列表

**常见的图遍历算法：**

1.广度优先搜索

2.深度优先搜索

**常问的图面试问题：**

1.实现广度优先搜索和深度优先搜索

2.检查一个图是否为树

3.计算一张图中的边的数量

4.找到两个顶点之间的最短路径

## 图像处理算法 ##

1、常用边缘检测有哪些算子，各有什么特性？

2.简述BP神经网络，AdBoost的基本原理？

3.关键字static的作用是什么？

4.简述C，C++程序编译的内存分配情况？

5.图像处理题目

## 数据结构 ##

1.交换排序

2.冒泡排序

3.快速排序

4.插入排序（Insertion Sort）

5.希尔排序（Shell Sort）

6.选择排序

7.堆排序（Heap Sort）

8.归并排序

9.线性时间非比较类排序

10.计数排序（Counting Sort）

11.桶排序（Bucket Sort）

12.基数排序（Radix Sort）

## 堆栈 ##

1.Push——在顶部插入元素

2.Pop—— 从堆栈中删除后返回顶部元素

3.isEmpty——如果堆栈为空，则返回 true

4.Top ——返回顶部元素，但不从堆栈中删除

**常见的堆栈面试问题**

1.使用堆栈计算后缀表达式

2.对堆栈中的值进行排序

3.检查表达式中的括号是否平衡

**队列的基本操作：**

1.Enqueue() —— 向队列末尾插入元素

2.Dequeue() —— 从队列头部移除元素

3.isEmpty() —— 如果队列为空，则返回 true

4.Top() —— 返回队列的第一个元素

**常问的队列面试问题：**

1.使用队列来实现堆栈

2.颠倒队列中前 k 个元素的顺序

3.使用队列生成从 1 到 n 的二进制数

## 哈希表 ##

**哈希数据结构的性能取决于以下三个因素：**

1.哈希函数

2.哈希表的大小

3.碰撞处理方法

**常问的哈希面试问题：**

1.找到数组中的对称对

2.追踪遍历的完整路径

3.查看一个数组是否为另一个数组的子集

4.检查给定数组是否不相交

## 最后 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3_size_16_color_FFFFFF_t_70 2][]  
以上就是关于数据结构的知识点，平时需要掌握的东西。弄懂这些，面试也不用愁了。在这里为大家整理了一份2020年面试（包括Java核心知识点、面试专题和20年最新的互联网真题、电子书）包含：数据结构算法，数据库，Spring全家桶系列资料，JVM、MySQL、MyBatis、Dubbo、Liunx、TomCat等多种知识点。获取方式：[点击这里获取资料文档！][Link 1]

[20201218174350725.png]: /images/20221120/d4a5f2e92d8d49f496c324eafcca1358.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3_size_16_color_FFFFFF_t_70]: /images/20221120/d86e9ce0c2ab40878fbd79988731c05e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201218173755904.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201218213133999.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4Nzk1NjA3,size_16,color_FFFFFF,t_70
[Link 1]: https://shimo.im/docs/6gXtcP8R99jtG9dX