小奏

Dynamic-Programming Fibonacci 123456789101112131415161718public class Fibonacci { public static void main(String[] args) { System.out.println(fibonacci(13)); } public static int fibonacci(int n) { int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; if (n < 2) { return dp[n]; } for (int i = 2; i <= n; i++) { dp[i] = dp[i - 2] + dp[i - 1]; } return dp[n];  ...

Greedy Algorithm 贪心例子 称之为贪心算法或贪婪算法，核心思想是 将寻找最优解的问题分为若干个步骤 每一步骤都采用贪心原则，选取当前最优解 因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。 贪心算法的应用： 背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。 活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。 编辑距离问题：给定两个字符串，求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。 网络流问题：给定一张有向图和一些起点和终点，求最大流量。 找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。 常见问题及解答： 贪心算法一定会找到最优解吗？ 答：不一定。贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题 ...

图 概念 图是由顶点（vertex）和边（edge）组成的数据结构，例如 123456graph LR A--->B A--->C B--->D C--->D 该图有四个顶点：A、B、C、D 以及四条有向边，有向图中，边是单向的 有向 vs 无向 如果是无向图，那么边是双向的，下面是一个无向图的例子 12345graph LR A---B A---C B---D C---D 度 度是指与该顶点相邻的边的数量 12345678910graph LR A((A))---B((B)) A---C((C)) B---D((D)) C---D D---E((E)) D---F((F)) E---F A & B & C & D & E & F 例如上图中 A、B、C、E、F 这几个顶点度数为 2 D 顶点度数为 4 有向图中，细分为入度和出度，参见下图 12345678910graph LR A((A))-->B((B)) ...

排序算法 概述 比较排序算法 算法 最好 最坏 平均 空间 稳定 思想 注意事项 冒泡 O(n) O(n2n^2n2) O(n2n^2n2) O(1) Y 比较 最好情况需要额外判断 选择 O(n2n^2n2) O(n2n^2n2) O(n2n^2n2) O(1) N 比较 交换次数一般少于冒泡 堆 O(nlognnlognnlogn) O(nlognnlognnlogn) O(nlognnlognnlogn) O(1) N 选择 堆排序的辅助性较强，理解前先理解堆的数据结构 插入 O(n) O(n2n^2n2) O(n2n^2n2) O(1) Y 比较 插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束 希尔 O(nlogn) O(n2n^2n2) O(nlognnlognnlogn) O(1) N 插入 gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同 归并 O(nlognnlognnlogn) O(nlognnlognnlogn) O(nlognnlognnlogn) O(n) Y 分治 需要额外的O(n)的存储空 ...

哈希表 第一版 未考虑 hash 码的生成，假定该 hash 码由我们提供 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148public class HashTable { // 节点类 static class Entry { int hash; // 哈希码 Object key; // 键 O ...

B 树 ai 问题列表 请用中文回答：B-树历史 请用中文回答：100万的数据使用 avl 树来存储，树高是多少? 20 请用中文回答：100万的数据，如果存储到B-树(最小度数是500)，那么树高大约是多少? 3 请用中文回答：B-树的特性有哪些？ 概述 历史 B树（B-Tree）结构是一种高效存储和查询数据的方法，它的历史可以追溯到1970年代早期。B树的发明人Rudolf Bayer和Edward M. McCreight分别发表了一篇论文介绍了B树。这篇论文是1972年发表于《ACM Transactions on Database Systems》中的，题目为"Organization and Maintenance of Large Ordered Indexes"。 这篇论文提出了一种能够高效地维护大型有序索引的方法，这种方法的主要思想是将每个节点扩展成多个子节点，以减少查找所需的次数。B树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。 B树结构有很多变种和升级版，例如B+树，B*树和SB树等。这些变种和升级版本都 ...

红黑树 概述 历史 红黑树是一种自平衡二叉查找树，最早由一位名叫Rudolf Bayer的德国计算机科学家于1972年发明。然而，最初的树形结构不是现在的红黑树，而是一种称为B树的结构，它是一种多叉树，可用于在磁盘上存储大量数据。 在1980年代早期，计算机科学家Leonard Adleman和Daniel Sleator推广了红黑树，并证明了它的自平衡性和高效性。从那时起，红黑树成为了最流行的自平衡二叉查找树之一，并被广泛应用于许多领域，如编译器、操作系统、数据库等。 红黑树的名字来源于红色节点和黑色节点的交替出现，它们的颜色是用来维护树的平衡性的关键。它们的颜色具有特殊的意义，黑色节点代表普通节点，而红色节点代表一个新添加的节点，它们必须满足一些特定的规则才能维持树的平衡性。 红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少 红黑树特性 所有节点都有两种颜色：红:red_circle:、黑:black_circle: 所有 null 视为黑色:black_circle: 红色:red_circle:节点不能相邻 根节点是黑色:black_circle: ...

AVL 树 概述 历史 AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。 在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。 AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。 前面介绍过，如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图 通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边 ...

历史 二叉搜索树最早是由Bernoulli兄弟在18世纪中提出的，但是真正推广和应用该数据结构的是1960年代的D.L. Gries。他的著作《The Science of Programming》中详细介绍了二叉搜索树的实现和应用。 在计算机科学的发展中，二叉搜索树成为了一种非常基础的数据结构，被广泛应用在各种领域，包括搜索、排序、数据库索引等。随着计算机算力的提升和对数据结构的深入研究，二叉搜索树也不断被优化和扩展，例如AVL树、红黑树等。 特性 二叉搜索树（也称二叉排序树）是符合下面特征的二叉树： 树节点增加 key 属性，用来比较谁大谁小，key 不可以重复 对于任意一个树节点，它的 key 比左子树的 key 都大，同时也比右子树的 key 都小，例如下图所示 轻易看出要查找 7 （从根开始）自然就可应用二分查找算法，只需三次比较 与 4 比，较之大，向右找 与 6 比，较之大，继续向右找 与 7 比，找到 查找的时间复杂度与树高相关，插入、删除也是如此。 如果这棵树长得还不赖（左右平衡）上图，那么时间复杂度均是 O(log⁡N)O(\log{N})O(log ...

查找概述 查找算法是一种在数据集中寻找特定数据项的方法。通常，数据集是在计算机程序中存储的，例如数组、链表或散列表。在编写程序时，查找算法是非常重要的，它有助于快速找到所需的数据。在本文中，我们将介绍一些基本的查找算法及其特点。 线性查找 线性查找也称为顺序查找，是一种最简单的查找算法。在这种算法中，我们从数据集的开头开始，逐个比较每个数据项，以寻找要查找的数据。如果我们找到了目标数据，查找过程就结束了。如果我们到达数据集的末尾，仍然找不到目标数据，则可以认为它不存在于数据集中。 线性查找的时间复杂度是O(n)，其中n是数据集的大小。因此，它在大型数据集中可能会很慢。然而，在小型数据集中，它仍然是一种非常有用的算法。 二分查找 二分查找也称为折半查找，是一种更快速的查找算法。但前提是，数据集必须已经排序。在二分查找中，我们取数据集的中间值，然后将目标与中间值进行比较。如果目标小于中间值，则在左侧子集中继续查找；如果目标大于中间值，则在右侧子集中继续查找。每次比较都会缩小要搜索的数据集的大小。 二分查找的时间复杂度是O(log n)，其中n是数据集的大小。这种算法在大型数据集中非常有效， ...