图算法系列之计算图中最短路径在前面两篇中我们通过深度优先搜索可以从图中找出一条通过顶点v到顶点w的路径,但是深度优先搜索与顶点的输入有很大的关系,找出来的路径也不一定是最短的,通常情况下我们很多时候需要找出图中的最短路径,比如:地图功能。这里我们就需要使用到广度优先搜索算法

图算法系列之深度优先搜索(一)在开始实现算法之前,我们依然先来定义搜索的API1. 构造方法提供了一个图对象,以及一个起点s,需要找到与s连通的所有顶点2. marked判断顶点s与v是否相邻3. count返回与顶点s相连的总顶点数

基于拉链式和线性探测式散列表实现Map## 散列函数实现散列表的第一步就是需要考虑如何把一个键转换为数组的下标,这时候就需要使用到散列函数,先把键值转换成一个整数然后在使用**除留余数法**计算出数组的下标。**每种类型的键我们都需要一个不同的散列函数。**

硬核图解红黑树并手写实现 性质1. 结点是红色或黑色。(why:为什么节点要区分颜色,红色节点的作用是什么?)* 性质2. 根结点是黑色。(why:为什么根节点必须是黑色)* 性质3. 所有叶子都是黑色。(why)* 性质4. 从每个叶子到根的所有路径上不

基于二叉树实现Map 使用二叉树实现的Map运行的效率取决于树的形状,而树的形状取决于数据输入的顺序;最好的情况下二叉树是平衡的,那么get、put的时间复杂度都是log(N); 但是如果插入的数据是有序的,那么二叉树就会演变成链表,那么get、put的性能将会大大减低;

基于数组或链表实现Map 虽然JAVA中已经提供了很多Map的实现,为了学习并掌握常用的数据结构,本篇主要是通过数组和链表两种方式实现,之后提供二叉树,红黑树,散列表的版本实现。通过自己手写各个版本的Map实现,掌握每种数据结构的优缺点,可以在实际的工作中根据需要选择适合的Map

快速排序算法实现及优化快速排序可以说是使用最广的排序算法了,主要的特点是基于原地排序(不需要使用辅助数组,节省空间);其实对于长度为N的数组使用快速排序时间复杂度为 NlogN;在前几篇也一起讨论了其他的排序算法,都没能够把这两个特点结合起来。

死磕归并排序算法要将一个数组排序,可以先将数组分为两个数组分别排序,然后再将结果归并在一起,重复递归这个过程,直到数组整体有序,这就是归并排序的算法思路。归并排序的优点是它能够保证任意长度为N的数组排序所需的时间与 NlogN 成正比,这个优点是初级排序无法达到的。

常见的初级排序算法,这次全搞懂 相信所有的程序员刚开始接触到的算法都会是排序算法,因为排序在对数据处理和计算有这重要的地位,排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。在开始之前我们先定义一个排序算法通用的模板,在后面的排序算法都会实现这个模板