四大超常用Java算法模板，七分理解，三分记忆，唯快不破

前言

整理了一些，常见算法的通用模板写法，针对不同的数据结构， 都可以针对性的选择使用。

BFS （Breadth-First-Search）广度优先 代码模版

其实他属于一种盲目搜索方法，也是很基础的一种搜索方式，主要目的是系统地彻底的展开（暴力）并检查结构中的所有节点。比如：树中，可以理解为层序的遍历的方式。图中先找到第一节点，再找到第一个节点的所有相连节点，按次序再找到每个节点的所有相连节点，逐步扩散，很明显，他需要依赖队列的结构，保证先进先出。 模板代码如下：

public void bfs(Node graph){ Queue<Node> queue = new LinkedList<Node>(); queue.add(graph.first); //第一个访问的节点 first是示意 Set<Node> visited = new HashSet<>(); //记录已经访问的节点 while(!queue.isEmpty()){ Node node = queue.poll(); visited.add(node); process(node); //处理一些访问的事情 nodes = getRelateNextNodes(node); //获取跟它相关的所有节点 //这里也可以按照相关的访问顺序依次放入队列，根据实际情况定 for(Node nod : nodes){ //针对没有访问过的节点加入队列 if(!visited.contains(node)){ queue.add(node); } } } }

DFS（Depth-First-Search）深度优先代码模版

简单的形容一下，就是从一个结构的首节点开始，一直访问到这个节点链路的最底层（当然，首节点如果有abcde5个节点，5个节点也是要按次数访问的，比如先访问a，然后再访问a的孩子，在访问a的孩子的孩子…直到这个链路终点），让后再依次回退访问其他节点。 一般来讲，什么样的适合用深度优先呢？ 能枚举全部状态的问题：比如 图的遍历，排列/组合方案等

递归代码模板：

//记录已经访问的节点 Set<Node> visited = new HashSet<>(); public void dfs(Node curr,Set<Node> visited){ visited.add(curr); process(curr); nodes = getRelateNextNodes(node); //获取与他直接相关的节点（树中，就是子节点） for(Node next : nodes){ if(!visited.contains(next)){ dfs(next,visited); //递归遍历 } } }

非递归代码模板

public void dfs(Node graph){ Set<Node> visited = new HashSet<>();//记录已经访问的节点 Stack<Node> stack = new Stack<>(); stack.push(graph.first);//第一个访问的节点 first是示意 while(!stack.empty()){ Node cur = stack.pop(); visited.add(cur); process(cur); List<Node> nodes = getRelateNextNodes(cur);//获取与他直接相关的节点（树中，就是子节点） for(Node next : nodes){ if(!visited.contains(next)){ stack.push(next); } } } }

注意之前有朋友经常搞混树的中序遍历 和 深度优先，这里说明一下他俩不是一个遍历！

DP 动态规划

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说求最长递增子序列呀，最小编辑距离呀等等，这些第一时间就需要考虑动态规划。

动态规划问题的关键分三步“ 1. 状态的定义：比如 opt[n], dp[n], fib[n] 2. 状态转移方程：dp[n] = best(dp[n-1], dp[n-2], ...) 3.根据状态寻找最佳子序列

二分查找

又称折半查找，比较简单不做过多介绍，它仅仅适用于线性结构而且要求：

单调递增或递减存在上下界能够通过索引访问

看模板：

public void binaryQuery(int[] array,int target){ int left = 0; int right = array.length -1; while(left <= right){ int mid = left + (right - left) /2; //防止溢出 if(array[mid] == target){ return; // find }else if(array[mid] < target){ left = mid + 1; }else{ right = mid -1; } } }

总结

这里想跟大家沟通的是算法的学习，绝对不是知识性的学习，是技能性的学习，需要持续的刻意练习，才能一通百通。