从入门到入土

二叉树与多叉树二叉树存在的问题二叉树提供了高效的插入删除查找等操作，但是也存在一定的问题： 当数据量较小时，普通二叉树不存在什么问题 当数据量特别大时，会导致二叉树的深度过深，使用搜索算法自上向下搜索时经过的节点就会相当多。这些节点存储在外存储器时，每访问一个节点就相当于进行了一次 I/O，随着树深度的增加，开销会越来越大，进而降低操作速度！ 多叉树如果每个节点可以有更多的数据项和更多的节点，就是多叉树。 多叉树通过重新组织节点，降低树的高度，并且减少 I/O 读写次数来提升效率。 2-3树2-3树是最简单的b树结构，具有以下特点： 2-3树的所有叶子节点在同一层 二节点（有两个子节点的节点）要么没有子节点，要么有两个子节点 三节点（有三个子节点的节点）要么没有子节点，要么有三个子节点 2-3树是由二节点和三节点构成的树 B树、B+树、B*树B树B树（Balanced Tree），前面介绍的2-3树，还有2-3-4树都是b树 MySQL中的索引就是基于B树或B+树的 B树的阶：节点最多的节点的子节点个数（2-3树的阶是3） B树的搜索： 从根节 ...

二叉排序树介绍二叉排序树（Binary Sort/Search Tree）：对于二叉排序树的任意一个非叶子节点，左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。 ==如果值相同，该节点可以放在左子节点或右子节点== 示例： 复杂度： 不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要**O(logn)**的时间。 二叉排序树的实现1. 二叉排序树的创建 构建(就是普通的二叉树) 123456789101112public class BinarySearchTree { private TreeNode root; public TreeNode getRoot() { return root; } public void setRoot(TreeNode root) { this.root = root; }} 1234567public class Tr ...

基本介绍 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 分类动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等； 区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等； 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等； 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等。 应用实例： ​ 最短路径问题 ，项目管理，网络流优化…… 实践：背包问题问题描述有一个背包， ...

简介 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。 比如说，把大象装到冰箱里我们就可以分三步完成：打开冰箱门、把大象推进器、关闭冰箱门（狗头） 经典问题 二分搜索 大整数乘法 棋牌覆盖 归并排序 快速排序 线性时间选择 最接近点对问题 循坏赛日程表 汉诺塔 基本步骤 分解：将原问题分解成一系列子问题。 解决：递归地求解各个子问题，若子问题足够小，则直接求解。 合并：将子问题的结果合并成原问题。 汉诺塔简介 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个 ...

简介二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 顾名思义，二分查找就是从中间开始查找，如果中间的值比目标值大，则结果要么在左边，要么不存在，反之则结果要么在右边，要么不存在，以此类推进行下一步查找…… 二分查找的运行时间为对数时间：$$O(log_2n)$$假设从 [0,99] 中查找目标位置最多只需要查找 7 次（2^6 < 100 < 2^7） 递归实现12345678910111213141516171819202122232425262728293031323334353637public class BinarySearch { /** * 重载二分查找 * * @param arr 需要查找的目标数组 * @param target 需要查找的值 * @return 返回查找的值在数组中的索引，如果不存在，则返回0 */ public int binarySearch(int ...

应用场景字符串匹配问题： 有一个字符串 BBC ABCDAB ABABCDABD ，另一个字符串为 ABCDABD 现在要判断 str1 中是否含有 str2，如果有就返回 str1 中首个匹配字母的索引，如果没有，则返回 1 暴力匹配算法思路遍历两个字符串： 若 str1[i] == str2[j]，则 i++、j++，继续匹配下一个字符 若 str1[i] != str2[j]，则 i = i - j + 1、j = 0，继续进行匹配 如此循环直至 i > str1.length && j > str2.length 图解 红色代表匹配失败 绿色代表匹配成功 。。。表示以此类推 代码实现12345678910111213141516171819202122232425 public int violenceMatch(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toChar ...

图的基本介绍为什么要有图我们之前学习的所有数据结构（线性表、树……）不能表示多对多的关系，这时候就需要引入图了！ 图的定义及一些概念 图是一种数据结构，其中节点可以有零个或多个相邻元素。两个节点之间的连接称为边，节点也可以成为顶点。 图的一些概念 顶点 边 路径 无向图 有向图 带权图 简单实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061public class Graph { //存储顶点集合 private ArrayList<String> vertexList; //存储图对应的邻结矩阵 private int[][] edges; //边的数目 private int numOfEdges; //定义一个数组，记录某个节点是否被访问 private boolean[] isVisited; ...

[TOC] 1. 矩阵中的路径 解题思路本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。 DFS 解析： f 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。 终止条件： 返回 false ： (1) 行或列索引越界 ​ (2) 当前矩阵元素与目标字符不同 ​ (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。 递推工作： 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 ‘\0’ ，代表此元素已访问过，防止之后搜索时重复访问 ...

正常实现123Input : [1,2,3,4,5]key : 3return the index : 2 1234567891011121314public int binarySearch(int[] nums, int key) { int l = 0, h = nums.length - 1; while (l <= h) { int m = l + (h - l) / 2; if (nums[m] == key) { return m; } else if (nums[m] > key) { h = m - 1; } else { l = m + 1; } } return -1;} 时间复杂度 二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。 m 计算 有 ...