7 传说中的靖哥哥

尚未进行身份认证

我要认证

小小程序员一枚

等级
TA的排名 5w+

骑士周游(马踏棋盘)问题

1,马踏棋盘算法介绍马踏棋盘问题也被称为骑士周游问题将马随机放在国际象棋的8*8的棋盘中的某个格子里,马按照走棋规则(日子)进行移动。要求每个方格只进入一次,走遍64个方格2,马踏棋盘算法思路分析马踏棋盘算法是对图的深度遍历优先(DFS)的使用,通过递归加回溯实现对问题的解决,同时可使用贪心算法对最终算法进行优化从一点出发,对该点标记为已访问,并寻找该点通过日子走法,下一步可能访问的点坐标的集合如果存在对应的点坐标集合,并且存在点未访问,则按顺序对集合中的未访问坐标点进行递归访问,即重复

2020-07-18 22:28:06

弗洛伊德(Floyd)算(F算法)— 最短寻径问题

1,应用场景—最短寻径问题弗洛伊德算法与迪杰斯特拉算法解决问题完全一致,这是解题思路不同2,弗洛伊德算法介绍和迪杰斯特拉(Dijkstra)算法一样,弗洛伊德(Floyd)算法也是一种用于寻找加权图中顶点间最短路径的算法,该算法创始人为1978年图灵奖获得者罗比特 · 弗洛伊德与迪杰斯塔拉算法不同的是:迪杰斯特拉算法基于一个给定的出发顶点,求出该顶点到其他顶点的最短距离;弗洛伊德算法将每一个顶点作为出发顶点,所以需要求出每一个顶点到其他顶点的最短路径;迪杰斯特拉算法最后给出的结果是一个一维

2020-07-18 22:25:24

迪杰斯特拉(Dijkstra)算法(D算法):最短寻径问题

1,应用场景—最短寻径问题如图,存在7个村庄['A', 'B', C', 'D', 'E', 'F', 'G'],现在有6个邮差,从G点出发,需要分别赶往['A', 'B', C', 'D', 'E', 'F']六个村庄各个村庄的距离通过边的权值表示,如A <-> B = 5问:如何计算G村庄到其他村庄的最短距离注意:之前两篇说的普里姆算法和克鲁斯卡尔算法,都是求图内连接各个节点的最短路径;该问题是从一点出发,到各个顶点的最短路径。注意,此处是到各个顶点,不是总和的最短路径2,迪

2020-07-18 22:15:54

克鲁斯卡尔(Kruskal)算法(K算法):公交站问题

1,应用场景—公交站问题某城市从新增的7个站点(A,B,C,D,E,F,G),现在需要把7个站点联通各个站点的距离用边权表示,比如A-B为12公里如何修路保证各个站点都能走通,并距离最短从图和问题可以看出,克鲁斯卡尔算法与普里姆算法解决的问题完成一致,只是解决问题的方式不同2,克鲁斯卡尔算法介绍克鲁斯卡尔算法,是用来求加权连通图的最小生成树的算法基本算法思想:按照边权值大小从小到大的顺序选取n - 1条边,并保证这n - 1条边不构成回路回路的判断标准是连接边的两个顶点的终点重合

2020-07-18 22:10:21

普里姆(Prim)算法(P算法):修路问题

1,应用场景—修路问题如图,此时有7个村庄['A', 'B', 'C', 'D', 'E', 'F', 'G'],现在需要把这7个村庄连通村庄之间的连接线表示可能修路的图示,权值表示举例此时,如果想要把7个村庄连通,怎么才能让连接的路程最短?此时应该尽可能的寻找少的线路,保证每条线路最短,最终达到整体线路最短(该部分有点类似贪心,但是贪心的最终结果不一定是最优解)2,最小生成树问题修路问题本身就是最小生成树(Minimum Cost Spanning Tree)问题,简称MST:给定一个

2020-07-18 22:07:10

贪心(Greed)算法:电台覆盖问题

1,应用场景—集合覆盖问题假设存在下面需要付费的广播电台,以及广播电台可以覆盖的地区。如何选择最少的电台,能实现区域的全覆盖2,贪心算法介绍贪心算法(贪婪算法)是指在对问题进行求解时,在每一步的选择中都选择最优解,从而期望能够导致结果是最优解的算法贪心算法所得到的结果不一定是最优解,但是一定是相对近似最优解的结果3,贪心算法最佳应用演示—集合覆盖问题已知存在多少电台,及电台对应的覆盖城市集合;并且各个电台所覆盖城市存在部分重复,需要最少几部电台可实现全覆盖首先汇总需要覆盖的城市,取

2020-07-18 22:04:42

KMP算法:字符串匹配问题

1,暴力匹配算法1.1,基本介绍暴力匹配算法是对字符串及匹配子串的字符进行一一匹配,完全匹配后则说明字符串匹配假设存在字符串str和子串childStr,需要进行字符串的暴力匹配,才从头开始匹配此时取字符串str的索引位置i = 0,子串childStr的索引位置j = 0,用str[0]和childStr[0]进行比较,如果匹配,则进行i++, j++,并依次进行下一个字符匹配此时如果不匹配,说明i = 0处起始匹配是匹配不到的,则进行回溯,重新从i = 1处开始重复以上逻辑进行匹配但是此时

2020-07-18 22:03:00

动态规划算法:背包问题

1,应用场景:背包问题问题描述:有一个容量为4磅的背包,需要装入如列表下的物品,在装入物品可重复和不可重复两种场景下,怎样才能使装入机制最大化商品名称商品重量商品价格吉他11500音响43000电脑320002,动态规划算法描述动态规划算法(Dynamic Programming)核心的思想是:将大问题划分为小问题进行解决,从而 一步步 获得最优解的处理算法(这个一步步是重点,等会就发现真是一步步)动态规范算法和分治算法类似,基本思想都是将待

2020-07-18 21:54:42

分治算法:汉诺塔问题

1,基本介绍分治算法是一种重要的算法。基本思想就是“分而治之”,将一个复杂的问题分为多个相似的子问题,然后再把子问题分为更小的子问题,直到最后子问题可以以一种最简单的方式直接求解,原问题的解即为子问题解的合并。分治算法的一些经典算法如:二分搜索,棋盘模型,合并排序,快速排序,汉诺塔等,以下将用汉诺塔举例2,基本步骤分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题解决:如果子问题规模较小,则直接求解;如果规模较大,则递归求解合并:将各个子问题的解合并为主问题的解3,汉

2020-07-18 21:49:26

图:深度优先遍历&广度优先遍历

1,图的基本概念1.1,图的基本介绍线性表局限于一个直接前驱和一个直接后继的关系树也只能有一个直接前驱也就是父节点当需要多对多的关系的时候,就应该用到图1.2,图的常用概念顶点(Vertex)边(Edge)路径无向图有向图带权图1.3,图的表达方式图的表示方式有两张:二维数组表示(邻接矩阵),链表表示(邻接表)邻接矩阵:是表示图形中顶点之间相邻关系的矩阵,对于N个顶点的图而言,矩阵的row和column分别表示n个点邻接表邻接矩阵需要为每个顶点分配n个边的空

2020-07-18 21:43:15

多路查找树

1,二叉树问题分析二叉树添加到内存中后,如果二叉树的节点少,那没有什么问题。但是如果二叉树的节点很多,在构建二叉树时就需要进行多次I/O操作,同时也会造成二叉树的高度很大,降低操作速度2,B树(2-3树,2-3-4树)2.1,B树基本介绍B树通过重新组织节点,降低树的高度,从而提高操作效率文件系统及数据库系统的设计者利用磁盘预读原理,将一个节点的大小设置为页的倍数(4K的倍数,MySQL一个节点为4页),这样每一个节点只需要一次I/O就可以完全载入将树的度M设置为1024,600E元素最多

2020-07-18 21:36:54

树:红黑树

1,红黑树引入红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1,超过后需要进行左旋或者右旋操作再次对树进行平衡,虽然这样能够解决二叉树退化为链表的缺点,将查询的时间复杂度控制在O(logN),但却不是最佳的;因为AVL树对高度差的控制太严,在需要频繁进行插入/删除的场景中,AVL需要频繁进行树平衡调整,影响整体性能,为了解决这个问题,引入红黑树2,红黑树性质性质1:每个节点要么是黑色,要么是红色性质2:根节点是黑色性质3:每个叶子节点(NIL)是黑色,NIL表示虚拟节点性质4

2020-07-18 21:30:23

树:平衡二叉树

1,二叉排序树问题对于一个有序数组{1, 2, 3, 4, 5},其生成的二叉排序树如下;由图可见,最终形成一个类似单链表形式的二叉树,对插入速度没有影响,但是对于查询速度明显减低,不能通过BST进行查询,时间复杂度为O(n);需要对二叉排序树这种现象进行优化,则引入平衡二叉树(AVL)2,平衡二叉树基本介绍平衡二叉树也叫平衡二叉搜索树(self-balancing binary search tree),又被称为AVL树,可以保证较高的二分查找效率平衡二叉树特点:是一颗空树或者左右子树的高

2020-07-18 21:09:50

树:赫夫曼树&赫夫曼编码

1,赫夫曼树1.1,赫夫曼树基本介绍及相关概念给定n个权值作为n个叶子节点,构造一颗二叉树,若该树的**带权路径长度(WPL)**达到最小,称这样的的二叉树为最优二叉树,也称为赫夫曼树,或者哈夫曼树、霍夫曼树赫夫曼树是带权路径长度最短的数,权值较大的节点离根较近路径和路径长度:在一棵树中,从一个节点往下可以达到的孩子和孙子节点之间的通路,称为路径;通路中分支的数量称为路径长度;若规定根节点的层数为1,则从根节点到第L层节点的路径长度为L - 1节点的权及带权路径长度:若将树中的节点赋给一个有意义

2020-07-18 21:03:24

树:线索化二叉树

1,线索化二叉树基本介绍线索化二叉树是对普通二叉树的扩展,对于普通二叉树而言,一个节点会包含一个数据域以及指向左右子节点的位置索引;但是对于叶子节点来讲,左右子节点的位置索引并没有被利用到,线索二叉树充分利用该部分节点,普通二叉树如下:在n个节点的二叉树中总共含有n - 1(类似5指向2表示一个位置指向)个位置指向,即2n(每一个节点有左右两个指针域)个指针域,这样对于一个二叉树来讲,共有2n - (n - 1) = n + 1个空指针域。利用二叉树的空指针域,根据前/中/后序不同遍历方式存储前驱节

2020-07-18 20:50:53

树:顺序存储二叉树

1,线索化二叉树基本介绍顺序存储二叉树是堆排序的基本思想从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换为树,树也可以转换为数组,如下图所示顺序存储二叉树只考虑完全二叉树,并且元素间存在函数对应关系第n个元素的左子节点为:index = 2 * n + 1第n个元素的右子节点为:index = 2 * n + 2第n个元素的父节点为:index = (n - 1)/ 2其中n表示在完全二叉树中的第几个元素,同时也表示数组中的索引下标,从0开始2,代码实现p

2020-07-18 20:41:52

树:二叉排序树

1,二叉树基本概念树分为很多种,其中每一个节点最多有两个节点的树形式称之为二叉树二叉树的子节点分为左节点和父节点;对于一个父节点来说,可以单独存在左子节点或者右子节点,也可以同时存在左右子节点如果二叉树的所有叶子节点都在最后一层,并且节点总数 = 2 ^ n - 1,n为最大层数,则该二叉树可以称之为满二叉树如果二叉树的所有叶子节点都在最后一层或者倒数第二层,且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,则称之为完全二叉树2,二叉树遍历2.1,前序遍历先输出当前节

2020-07-18 20:40:10

哈希表(散列)

1,哈希表基本介绍散列表(HashTable,也叫哈希表),是根据关键码值(Key Value)而进行访问的数据结构。也就是说,通过关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数叫散列函数,存放记录的数组叫做散列表基本数据结构为 数组 + 链表;通过键值获取到数组索引位置,存储到数组中,数组中该索引位置如果已经存在数据,则在该索引位置上构造链表。2,哈希表示意图3,哈希表代码实现package com.self.datastructure.hash;import

2020-07-18 20:28:24

查找算法:斐波拉契查找

1,斐波拉契查找基本介绍黄金分割点:是把一条线段分为两部分,使得一部分与全程之比等于另一部分跟这部分之比,比例近似于0.618,称为黄金分割点斐波那契数列{1, 1, 2, 3, 5, 8 ... n, m, m + n}发现两个相邻数的比例,无限接近于0.618斐波那契查找,依旧基于数组是有序数组,并使数组长度与斐波那契数组元素相匹配,之后类似于二分查找方式,以斐波那契数组的数组特性f[k] = f[k - 1] + f[k - 2],对目标数组取中值middle = low+ f[k - 1]

2020-07-18 20:25:17

数据查找算法:插值查找

1,插值查找基本介绍插值查找的前提条件是目标数组为有序数组插值查找类似于二分查找,不同的是插值查找每次从自适应middle索引开始查找插值查找其实就是对二分查找middle索引求值的优化,求值公式为:int middle = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left])二分查找到插值查找的公式演进如下:举例说明:如果存在一个长度为20, 值为1-20的顺序一维数组,需要查找到1所在的索引

2020-07-18 20:21:38

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。