【备战秋招冲击大厂】Java 面试题系列，你还没弄明白存储键值对

12. }

14. KMP 算法

建立部分匹配表

移动位数 = 已匹配的字符数 – 对应的部分匹配值

1. public static int[] KmpMatchTable(String str) {

2. }

KMP 搜索

1. public static int KMPMatch(String str1， String str2) {

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

         j = matchTable[j-1]；

8. }

15. 贪心算法

16. 普利姆算法（prim）

• 求最小生成树

• 普里姆算法介绍

• 普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图

• 普利姆的算法如下:

(1) 设 G=(V,E)是连通网，T=(U,D)是最小生成树，V,U 是顶点集合，E,D 是边的集合

(2) 若从顶点 u 开始构造最小生成树，则从集合 V 中取出顶点 u 放入集合 U 中，标记顶点 v 的 visited[u]=1

(3) 若集合 U 中顶点 ui 与集合 V-U 中的顶点 vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点 vj 加入集合 U 中，将边（ui,vj）加入集合 D 中，标记 visited[vj]=1

(4) 重复步骤②，直到 U 与 V 相等，即所有顶点都被标记为访问过，此时 D 中有 n-1 条边

(5) 提示：单独看步骤很难理解，我们通过代码来讲解，比较好理解.

17. 二叉树的中序遍历

1. List<Integer> list = new ArrayList<>()；

2. }

18. 二叉树层序遍历

1. public List<List<Integer>> levelOrder(TreeNode root) {

2. }

19. 二叉树之字形打印

1. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

20. 判断 A 是否是 B 的子树

1. public class Solution {

2. }

21. 最小硬币数

• 动态规划算法题：给定不同面额的硬币数组 coins 和总额 amounts，求能够组成总额的最小硬币数。如 coins=[1，2，5]，amounts=11，那么最少硬币数为 5+5+1=3.

1. public static int CoinsChange(int[] coins， int amount， int coinSize) {