B站（IT速成之JAVA速成班 300分钟算法面试）跟做笔记

跟做的视频B站

常用数据结构 链表： 快慢指针例题：

一般用在要返回新链表的题目上。

---

栈

---

队列 双端队列应用

特点：先进先出

实现：双链表

对头：查看、添加数据

队尾：查看删除数据

实现场景：广度优先搜索

例题

---

树

遍历：前 中 后

前序遍历： 应用场景：创建一棵新树

中序遍历： 应用场景：二叉搜索树（左孩子<根节点<右节点）

后序遍历： 应用场景：

---

高级数据结构 1.优先队列

• 本质：二叉堆

例题：

2.图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sdcIykGh-1651391280102)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

3.前缀树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oYVyfjf1-1651391280103)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2OYVCc1j-1651391280106)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

4.线段树

没听懂

5.树状数组

---

---

常用算法 1.递归和回溯

递归：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tL9diIIt-1651391280109)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0966oFs5-1651391280110)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DOy3DQHC-1651391280111)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AJz6SeGY-1651391280112)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

回溯：

2.排序

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tY2yeByV-1651391280114)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

1.冒泡 o(n2) o(1)稳定

2.插入排序o(n2) o(1)稳定

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FlRU5L8S-1651391280115)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

3.归并o(nlogn) o(n)稳定

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UCHsyw2M-1651391280116)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

4.快排 o(nlogn) o(logn)稳定

5.拓扑排序

---

3.DFS\BFS

​ DFS利用栈实现

• BFS利用队列实现

4.动态规划

面试题

1. 技巧一： 定义哈希集合

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jhZ57u1R-1651391280121)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uEEfiQe2-1651391280123)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

---

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BrrpYdN7-1651391280124)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HXHGn2bx-1651391280125)(http://www.kaotop.com/file/tupian/20220505/favicon.ico)]

技巧：

素数：只需判断到根号X

链表反转：迭代法（可能三个指针）